본문 바로가기
반응형

전체 글313

[프로그래머스/C++] 카카오프렌즈 컬러링북 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 DFS나 BFS로 연결된 영역을 탐색하고, 그 크기를 계산하면 쉽게 풀 수 있는 문제다. 문제에서 구해야하는 값이 영역의 개수, 그리고 영역 중 가장 크기가 큰 영역이다. 그렇기 때문에 영역을 만나면 그 영역의 수를 세고 방문했다는 표시를 한다.(다시 탐색을 하지 않도록 표시를 해야한다) 연결된 부분 즉, 모든 영역을 탐색했다면 영역의 개수를 1 추가하고 최대영역의 크기와 비교한다. 만약 이번에 탐색한 영역의 크기가 이전에 저장된 가장 큰 영역의 크기보다 크다면 값을 갱신하면 된다. 마지막으로 구한 영역의 수.. 2024. 4. 28.
[프로그래머스/C++] 단체사진 찍기 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 풀기 위해서는 시간복잡도를 빨리 눈치채는게 중요했다.처음에 문제를 보고 어떻게 규칙을 찾아서 빠르게 계산을 할 수 있을까? 고민을 했다. 예를 들어 서로 연관된 규칙이 있는 경우에는 하나의 집합으로 포함시켜서 Combination을 계산하면 빠르게 조건을 탐색할 수 있지 않을까 생각했다. 하지만 아무리 생각해도 그 과정을 구현하기에는 힘들 것 같아서 다른 방법을 생각했다. 그러던 와중 8명을 배치하는 경우의 수가 8! 이고, 조건이 100개라는 걸 보고 둘을 곱하면 약 4,000,000 이므로 모든 경우를 직.. 2024. 4. 25.
[프로그래머스/C++] 가짜 해밀토니안 (월간 코드 챌린지 시즌1) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 가짜 해밀토니안 경로를 만들 때, 어떻게 경로가 형성되는지 잘 파악해야 풀 수 있는 문제다. 문제에서 알려주는 가짜 해밀토니안 경로를 한번 분석해보자위 그림에서 같은 그래프지만 2번 노드에서 어디로 가는지에 따라 만들 수 있는 가짜 해밀토니안 경로가 달라진다. 4번으로 가게 되면, 더 이상 2번 경로로는 돌아오지 못한다.대신 2번 분기점에서 다른 곳으로 빠지지 않고 다시 1번까지 돌아가면 4번 5번을 거쳐 해밀토니안 경로를 만들 수 있다. 만들어진 해밀토니안 경로를 보면 특정 노드와 연결된 노드는 최대 3개가.. 2024. 4. 24.
[백준/C++] 운동 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 도시에서 시작해 다시 돌아오는 사이클이 있는지 확인하고 있다면, 그 중 가장 비용이 적은 사이클을 출력하는 문제다. 사이클을 찾기 위해서는 결국 st 에서 st로 돌아오는 최소비용을 구해야 한다. 문제는 시작점이 하나만 주어진게 아니라 모든 도시가 시작점이 될 수 있다는 점이다. 그러므로 결국 모든 도시에 대해서 시작점으로 돌아오는지 탐색을 해야한다. 처음에는 priority queue를 사용한 다익스트라 알고리즘으로 풀려고 했으나, N개의 점에 대해 다익스트라 연산을 하면 시간복잡도가 O(V*Elog(V))가 된다. [(E < V*2) 이므로 log(V)로 표현 가능] 그러면 O(V^3log(V.. 2024. 4. 23.
[백준/C++] 플로이드 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 정점에서 다른 정점으로 갈 수 있는 최단거리를 구하는 문제다. 모든 정점의 경우를 구해야하기 때문에 플로이드 워셜 알고리즘으로 문제를 풀면 O(N^3)의 시간복잡도로 문제를 해결할 수 있다. 문제를 풀기전에 플로이드 워셜 알고리즘을 간단하게 정리하면, 정점 i에서 j로 가는 비용과 정점 i -> k -> j로 가는 비용을 비교해 최단 거리를 갱신하는 과정이다. 위의 과정을 3중 for문을 이용하면 모든 정점에서 다른 정점으로 가는 최소비용을 구할 수 있다. 여기서 중요한 점은 경유지 k가 for문의 가장 상위에 있어야 한다. 왜 가장 상위에 있어야 하는지 설명하기 전에, 지나갈 수 있는 경유지의 .. 2024. 4. 21.
[백준/C++] 램프 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 열의 램프들을 반전 시키는 방법을 K번 실시했을 때, 모든 행의 램프가 켜진 경우가 가장 많은 수를 구해야 한다. 이 문제에서는 램프가 가장 많이 켜진 경우를 찾기 위해 모든 경우를 탐색해봐야 하는데 이때, 모든 경우를 찾기 위한 기준을 잘 정해야 한다. 특정 열의 램프들을 끄거나 키는 것을 기준으로 잡게 되면 2^n의 시간복잡도가 나타나고 중복이 발생하게 된다. 잘 생각해보면 반대로 특정 행의 램프들을 전부 키도록 한 다음 그때, 몇 행의 램프가 켜져있는지 비교하는 방법으로 쉽게 문제를 풀 수 있다. (왜냐하면 같은 열에 있는 램프들은 전부 불이 반전되는 것에 연결되어 있다. 그렇기 때문에 한 .. 2024. 4. 21.
[프로그래머스/C++] 유사 칸토어 비트열 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제에서 나오는 수열은 프랙탈 구조처럼 일정한 규칙을 갖고있는 수열이다. 만약 이 문제에서 1의 개수를 직접 count한다면 최대 개수가 5^20 이기 때문에 시간복잡도에서 문제가 생길 수 있다. 그러므로 규칙을 이용해 1의 개수를 직접 세지 않고, 범위를 이용해 빠르게 풀었다. 일단 l ~ r까지 1의 개수를 구하기 위해 생각해 볼 것은 n = i 인 경우의 모든 1의 개수와 n = i -1 인 경우의 모든 1의 개수는 총 4배 차이가 난다. 왜냐하면 이전 배열의 1이 11011로 바뀌고 0은 00000으로 바뀐다. 그러므로 1의 개수는 이전의 1의 개수에만 영향을 받아 4배씩 증가하는 것이다. 그리고 [l.. 2024. 4. 20.
[백준/C++] Pho Restaurant HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 두 가지 요리만 하는 식당에 n개의 테이블이 있고, n개의 테이블당 i명의 사람이 요리를 시킨다. 이때, 같은 테이블은 같은 요리를 주문하도록 만드려면 사람을 몇 번 이동해야하는지 계산하는 문제다. 문제 자체는 크게 어렵지 않다. 테이블 당 1번 메뉴와 2번 메뉴를 주문한 사람의 수를 파악하고, 그 중에서 메뉴의 수가 더 적은 사람을 다른 테이블로 이동시키면 된다. 여기서 하나의 예외 상황이 발생하는데, 만약 모든 테이블이 1번 메뉴를 많이 시키고 2번 메뉴를 적게 시키는 경우다. (또는 모든 테이블이 2번 메뉴를 많이 시키고 1번 메뉴를 적게 시키는 경우) 이 경우 최소값인 수만 다른 테이블로 이동하.. 2024. 4. 19.
[백준/C++] 타임머신 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 음의 간선이 있기 때문에, Dijikstra알고리즘으로 문제를 풀 수 없다. 음의 사이클이 존재하는지 찾는 알고리즘에는 벨만 포드 알고리즘이 있기 때문에 벨만 포드 알고리즘을 이용해 문제를 풀었다. 벨만 포드 알고리즘에서 음의 사이클이 존재하는지 판단하는 방법은 다음과 같다. N개의 정점이 있을 때, 임의의 정점 A에 도달하기 위해 거쳐야되는 정점의 개수는 총 N-1개다. 그렇기 때문에 음의 사이클이 없다면 임의의 정점에서 다른 정점으로 도달하는 최소비용을 구하는 과정을 N-1번 하면 출발 정점에서 모든 정점에 도달하는 최단경로가 계산이 된다. 이 때, 음의 사이클이 있다면 한번 더 최단경로를 계산했을.. 2024. 4. 18.
[프로그래머스/C++] 두 큐 합 같게 만들기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 여러 방법으로 풀 수 있는 문제다. 누적합을 이용해 푸는 방법, 문제 그대로 Queue를 이용해 푸는 방법, index를 이용해 Queue가 pop되는 것 처럼 푸는 방법 등 다양한 방법이 존재한다. 이 중에서 나는 Index를 이용해 풀었다. 먼저 이 문제에서 중요한 점은 Queue에서 뺀 원소는 다른 Queue에 들어간다는 것이다. 즉, 그림으로 생각하면 아래와 같이 Queue를 표현할 수 있다. 여기서 Queue2의 원소가 Queue1으로 삽입된다면, 위 그림과 같이 파란 색 부분의 합이 Queue1에 들어가게 된다. 이렇게 연속적인 수들의 합이 되기 때문에 누적합이나, 단순히 Index를 이용해.. 2024. 4. 18.
[백준/C++] 미확인 도착지 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 시작점 st에서 도착점 ed로 가는 최단 경로에 임의의 두 점 (m, n)을 잇는 경로가 포함되어 있는지 계산하는 문제다. 문제를 해결하는 방법은 여러 방법이 있다. 1. Dijikstra 알고리즘으로 두 점 m, n을 잇는 경로를 포함하는지 체크한다. 2. Dijikstra 알고리즘으로 최단경로와 [st -> m -> n -> ed, st -> n -> m -> ed]의 최단 경로의 길이가 같은지 비교하는 방법이 있다. 이 중에서 1번 방법으로 코드를 구현해 문제를 풀었다. Dijikstra 알고리즘과 동일하게 코드를 구현하지만 m, n을 잇는 경로를 포함하는지 체크할 배열을 하나 만든다. 이후.. 2024. 4. 17.
[백준/C++] 특정한 최단 경로 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 중간에 반드시 두 정점을 거쳐서 가는 최단경로를 찾는 문제다. 결국 최단경로를 찾는 문제기 때문에 Dijikstra 알고리즘으로 쉽게 풀 수 있다. 제한사항을 보면 V의 개수가 최대 800이기 때문에 O(N^2)의 시간복잡도로 문제를 풀어도 빠르게 풀 수 있는 문제다. 이 문제의 특징은 양방향 간선이기 때문에 a -> b의 최단거리는 b -> a의 최단거리와 같다. 그러므로 이를 이용하면 최단거리를 구하기 위해서는 두 개의 값만 비교하면 된다. 1. 1 -> a -> b -> V로 도착하는 경우 2. 1 -> b -> a -> V로 도착하는 경우 위의 두 경우를 비교하면 되는데, a -> b의 최단거리.. 2024. 4. 16.
[프로그래머스/C++] 당구 연습 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 당구의 원쿠션 규칙에 따라 공을 맞췄을 때, 공의 이동거리를 구하는 문제다. 여기서 시작하는 X좌표나 Y좌표가 같은 경우만 주의하면 쉽게 풀 수 있는 문제다. 아래 그림을 보며 기본적인 문제 풀이 방법을 생각해보자 벽에 부딪혀 반사된 공의 이동거리는 위 그림의 d와 같다. 즉, 맞추려는 공을 종이접기 하듯이 펼친 후 직선거리를 구하면 그 값이 공의 이동거리가 된다. 위 그림의 경우 위쪽 벽에 맞고 공을 맞출 때 이동거리를 구하면 아래와 같다. $$ (distance)^2 = (x_i-x_s)^2 + (n-y_s+n-y_i)^2 $$ 이렇게 4방향의 벽에 튀었을 때, 이동거리의 최소 값을 구하면 된다. .. 2024. 4. 16.
[백준/C++]최단경로 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 시작점에서 다른 정점에 도착하는 최단 경로를 구하는 문제다. 최단 경로를 구하는 알고리즘에는 다익스트라(Dijikstra) 알고리즘이 있다. 다익스트라 알고리즘은 아래 순서로 진행된다. 1. 방문하지 않은 정점 중에서 가장 비용이 적은 방문할 수 있는 정점을 선택한다. 2. 선택한 정점에서 이동할 수 있는 정점들을 방문할 수 있는 정점에 추가하고, 이동했을 때 드는 비용을 갱신한다. 3. 선택한 정점을 방문처리하고, 다시 1번 과정을 반복한다. 이 과정에서 가장 비용이 적은 방문할 수 있는 정점을 선택하는 방법에 따라 시간복잡도가 달라진다. 만약 V개의 노드를 전부 탐색할 경우 O(V^2)의 시간.. 2024. 4. 15.
[백준/C++] 이분 그래프 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 정점들의 집합을 두 개로 분류했을 때, 집합 내에 속한 정점들이 서로 인접하지 않게 할 수 있는지 판단하는 문제다. 어떻게 하면 문제를 풀 수 있을지 한번 그림으로 생각해보자 먼저 위의 왼쪽 그림의 경우를 살펴보자 하나의 정점이 속할 집합이 정해지면, 인접한 정점은 다른 집합에 속해야 한다. 그러므로 이를 이용해 하나의 정점이 0번 집합에 속했다면, 인접한 정점은 전부 1번 집합에 넣는다. 마찬가지로 하나의 정점이 1번 집합에 속했다면, 인접한 정점은 전부 0번 집합에 넣으면 된다. 이렇게 정점들의 집합을 두개로 나눠서 채워 넣으면 한 집합에 속해있는 정점들은 서로 인접하지 않도록 만들 수 있다. 그런.. 2024. 4. 14.
반응형

티스토리툴바