3176번: 도로 네트워크 - LCA 간선에 가중치가 있는 트리가 주어질 때 정점 u에서 정점 v까지의 경로의 간선들 중가장 작은 가중치, 가장 큰 가중치를 출력하는 문제이다. 100,000개의 쿼리를 처리해야하기에 효율적인 방법이 필요한데경로가 유일하다는 것을 이용하여 LCA를 이용해보자u, v의 경로는 u - LCA(u,v) - v 로 이루어져 있기 때문이다.그렇다면 LCA를 구하면서 가장 작은 가중치, 가장 큰 가중치를 구할 수 있을까?LCA에서는 정점의 2^k번째 부모를 저장해놓는다.즉 한 정점의 2^(k+1)번째 부모는 그 정점의 2^k번째 부모의 2^k번째 부모와 같다를 이용하였다.이와 비슷하게 한 정점의 2^(k+1)번째 부모까지의 가장 작은 가중치는min(그 정점의 2^k번째 부모까지의 가..
3015번: 오아시스 재결합 N개의 수들이 주어질 때, 이 중 두 개의 수(한 개의 쌍)를 고른다.이 때 이 두 수 사이에 이 두 개의 수보다 크지 않은 수들로만 구성되는 쌍의 개수를 묻는 문제이다. N개의 수들이 담겨져 있는 배열을 A라 할 때앞에서부터 차례대로 A[i]를 추가함에 따라 생기는 쌍의 개수를 생각해보자.만약에 A[i-1]이 A[i]보다 작다고 생각하자.그럴 경우에는 앞으로 A[j](i < j)를 확인 할 때 A[i-1]과 A[j]이 쌍을 이룰 일은 절대 없다.이 두 수 사이에 A[i-1]보다 큰 A[i]가 존재하기 때문이다.즉 내가 A[i]를 추가하였을 때 이전의 A[i]보다 작은 수는 앞으로의 결과에 영향을 못끼친다는 것이다.그러므로 매 상황마다 이전의 자신보다 작은 수를 제거하면서 답..
14577번: 일기 예보 - 구간트리 (세그먼트 트리) kks227님 블로그의 오프라인 쿼리를 읽고 인상 깊어 작성하게 되었다.이 문제에서는 4개의 쿼리가 있다.1. 하나의 값에 X를 더한다.2. 하나의 값에 Y를 뺀다.3. 값이 L ~ R 사이인 원소의 개수를 구한다.4. K번째로 큰 값을 구한다.이러한 쿼리들을 10^5개를 처리해주면 되는 문제이다. 1번과 2번은 구간트리에서 많이 접해본 적이 있다.어떤 idx에 대하여 X를 더하는, Y를 더하는 과정은 O(lgN)에 구할 수 있다. 3번 쿼리는 값이 L ~ R 사이인 원소들의 개수를 구하는 쿼리이다.이 쿼리를 어떻게 처리해야할까?나라들의 현재 값이 들어있는 배열을 A라 할 때 A = {1, 2, 10, 2, 4} 가 된다고 하자.구간트리에 이 값이 ..
12995번: 트리나라 - DP kks227님 블로그의 동적 계획법 5를 읽고 인상 깊어 작성하게 되었다.트리에서 DP를 사용하는 문제 유형에 대하여 설명하는데 그 중노드 u를 루트로 하는 서브트리 안에서 모든 자식 노드에 분배를 해야하는 문제를 어떤 식으로 접근할까?에 대한 유형이다. 이 문제는 트리가 주어질 때 크기가 K인 트리를 만들기 위한 경우의 수를 묻는 문제이다.이런 문제를 풀 때 기본적인 아이디어는 u의 자식 노드를 v1, v2, ... vm이라 하면u와 v1을 루트로 하는 서브트리랑만 연결 될 때,u와 v1, v2를 루트로 하는 서브트리랑만 연결 될 때,...u와 v1, v2, ... vm을 루트로 하는 서브트리랑만 연결 될 때 순으로 구하게 된다.약간 플로이드 와샬에서 i 정점에서 j 정..
15678번: 연세워터파크 - DP kks227님 블로그의 동적계획법 4를 읽고 인상 깊어 작성하게 되었다.이 문제는 임의의 시작점에서 번호가 증가하는 방향으로 징검다리를 건너게 되는데한번에 D개 이하의 징검다리를 뛰어넘을 수 있을 때 점수의 최댓값을 구하는 문제이다.풀이는 간단하다.어떤 도착점 k의 관하여 dp(k)를 도착점 k에 도착했을 때 얻을 수 있는 최대 점수라 하면,dp(k)는 max(0, k-D) ~ k까지의 dp값 중 최댓값이 된다.이후 모든 i에 대하여 dp(i)의 최댓값이 답이다. 이 때 구간에 대하여 최댓값을 구하는 과정을 반복하여야 한다.구간이기에 구간 트리를 이용하여 O(lgN)만에 최댓값을 찾을 수 있고이는 시간복잡도가 O(NlgN)만에 문제를 해결할 수 있다. 이 때 kks22..
1787번: 문자열의 주기 예측 - KMP, DP 문자열이 주어질 때 이 문자열의 모든 접두사에 대하여 추정할 수 있는 주기 중 가장 긴 것의 길이의 합을 출력하는 문제이다.KMP에서 다뤘던 광고문제나 Slot Machines문제에서 비슷한 유형을 다뤄본 적이 있다.문자열에서 주기를 구하는 방법은 S - pi[S-1]로 계산하였다.그러나 이 때의 답은 S-pi[S-1]값이 작을 때였고, 우리가 구해야할 답은 S-pi[S-1]의 값이 클 때가 되어야한다.즉 pi는 접미사도 되고 접두사도 되는 최대 길이이기에 최소 길이를 구하여야 한다는 것을 알 수 있다. ababa의 pi[S-1]은 3이다. S[:3], S[2:]이 모두 aba로 같기 때문이라는 것을 알 수 있다.이 때 aba의 pi값은 1이 되는데,S[..
1017번: 소수 쌍 - 이분 매칭 짝수 개의 수 리스트가 주어질 때, 2개씩 짝지었을 때의 합이 모두 소수가 되는 경우의첫 번째 수와 연결 되어 있는 수를 오름차순으로 출력하는 문제이다. 입력에 주어지는 수들은 중복되지 않으므로 1이 두 번 주어질 수는 없다.소수는 2보다 클 경우 모두 홀수이므로 합이 홀수가 될 때의 경우를 생각해보자.홀수는 짝수와 홀수가 더해질 때만이 홀수가 되므로 2개의 그룹으로 나눠지고이들을 짝지어 이어주는, 즉 이분매칭 문제가 되게 된다.짝수 그룹, 홀수 그룹으로 나누고 이들을 잇는 간선들은 합이 소수가 될 경우 이어준다.이 그래프의 최대 매칭이 N/2일 경우에 답으로 가능할 경우인 것을 알 수 있다. 약간의 함정이 숨어있는 문제다. 출력해야할 부분은 첫 번째 수와 연결되어 있..
14961번: Untangling Chain 원점에서 시작하여 N번 동안 L의 거리를 이동한 뒤 왼쪽 또는 오른쪽으로 회전을 반복한다.회전하는 방향이 고정되어 있을 때 교차하지 않도록 이동거리를 정해주는 문제이다. 접근 방법은 다음과 같다.현재 이동하고 있는 방향이 오른쪽일 때 다음에는 위쪽, 또는 아래쪽으로 이동하여야한다.위쪽과 아래쪽으로 갈 때 방해 받지 않으려면 지금까지 이전에 진행했던 경로 중 가장 오른쪽에 있는 좌표보다 1 더 간다면 이동하는데에 문제가 없을 것이다.위 또는 아래로 이동한 뒤에도 오른쪽 또는 왼쪽으로 이동하는 것이 방해받지 않으려면위로 간다면 지금까지 이전에 진행했던 경로 중 가장 위에 있는 좌표보다 1 더,아래로 간다면 아래에 있는 좌표보다 1 더 간다면 문제가 없을 것이다.이..
14959번: Slot Machines - KMP N개의 수들이 주어질 때, 이 수열은 처음 K개의 원소를 제외하고 주기 P를 갖는다.이 때, K+P가 최소가 되는, 같다면 P가 최소가 되는 K와 P를 출력하는 문제이다. 주기를 찾는 문제는 KMP에서 광고문제로 설명한 적이 있다.문자열을 이루고 있는 최소의 주기를 구하는 방법은 문자열의 길이가 S일 때, S - pi[S-1]이다.이를 이용하려면 먼저 pi배열을 구하여야 한다.pi[i] = N[...i]의 접미사도 되고 접두사도 되는 문자열의 최대 길이로주기가 시작되는 부분을 알 수 없으므로 모든 N에 대하여 확인해봐야하므로 시간복잡도가 O(N^2)이다.그러나 여기서 N개의 수를 뒤집어서 생각한다면 주기의 시작부분은 처음부터가 되게 되며단 한번의 pi배열..
14955번: How Many to Be Happy? - 최소 컷 N개의 정점과 M개의 간선으로 이루어진 그래프에서 각 간선이 MST가 포함되기 위해제거해야하는 간선의 최소 개수의 합을 구하는 문제이다. 접근 방법은 다음과 같다.u와 v를 잇는 가중치가 c인 간선이 있을 때 이 때 이 간선이 MST가 아니라는 것은가중치가 c미만인 간선들로 u와 v가 이어져 있다는 것이다.이제 이 간선을 MST에 포함되게 하려면 가중치가 c미만인 간선들로 u와 v가 이어져있지 않게 해야한다는 뜻이 되며이는 각각의 간선을 용량이 1인 간선으로 보았을 때가장 작은 유량으로 u와 v가 각각 다른 집합에 속하도록 나누는, 즉 최소 컷을 구하는 문제가 된다. 매 간선을 보며 그 간선의 비용보다 작은 간선으로만 용량이 1인 간선으로..