joseph0528 코딩 블로그

이 문제는 수영장이나 우물 관련 문제와 비슷한 스타일인 물을 담을 수 있는 영역의 크기를 구하는 문제이다. 다른 문제들과는 다르게 N과 M의 범위가 크지 않기 때문에 다양한 풀이가 나올 수 있는데 이 글에선 Union Find를 이용하여 풀이를 작성하였다. Union Find 를 어떻게 이용할 수 있을까?Union Find(줄여서 유파)를 이용하기 전에 입력으로 주어진 환경에서 물이 어떻게 채워지는지 생각해 보자.전체 영역에 물을 넣는다고 하면 가장 아래쪽에 공간이 있는 쪽부터 채워지며, 바깥쪽과 접촉하게 되기 직전까지 채워지게 된다. 입력 예제로 생각해 보면, 맨 처음에는 보이지는 않지만 안쪽 공간에 물이 채워지고, 다음에는 위 그림과 같이 물이 채워진다. 그 이후부터는 바깥쪽으로 흘러내려 채울 수 없..

문제가 일본어로 되어 있어서 난감할 수 있지만 문제를 요약해 보면,A[i] 의 위치에 B[i] 번의 목수의 작업이 필요할 때 1의 위치에서 K명의 목수가 이동할 때 몇 번 만에 작업을 모두 끝낼 수 있는지를 출력하는 문제다. 여기서 목수는 순차대로 작업을 하는 것이 아니라 임의의 작업 지점에 갈 수 있다. 한번 이동할 때마다 1의 시간이 지나가며, 작업은 모든 목수가 동시에 진행한다. 이러한 문제는 전형적인 이분탐색을 이용하는 문제다.최소 시간 이후로는 항상 조건을 성립하고, 최소 시간 이전에는 성립하지 않기 때문에 이분탐색으로 이 최소 시간을 찾아주면 된다.그러면 이분탐색의 mid 가 주어졌을 때 mid 가 만족하는지 여부는 어떻게 찾을 수 있을까? 주어진 A,B 에 대해 mid 안에 해결해야 되기 때..

이 문제는 초기 문자열과 만들어야하는 문자열이 주어질 때, 각 위치의 스티커를 떼고 붙이고, 구매 등의 방법을 사용해 만들어야하는 문자열이 초기 문자열의 부분 문자열이 되도록 하는 최소값을 구하는 문제이다. 문제 설명만 봤을 때는 어려워 보일 수도 있지만 문자열의 길이가 500이 안되기 때문에 모든 경우를 탐색하면서 최소값을 계산해주면 된다. 부분 문자열을 만들 수 없는 경우 -1을 출력하라고 되어있는데, 이는 구매할 수 있는 스티커 중에 부분 문자열에 필요한 스티커가 없을 때 -1을 출력해주면 된다. 부분 문자열을 만들기 위해서 부분 문자열에 해당될 부분 중, 바꿔야 될 부분의 스티커를 모두 떼준다. 그후 뗀 스티커와 다른 범위에 있는 스티커까지 고려해서 어느걸 고르는 것이 최소값이 되는지 판단해주면 ..

이 문제를 요약하면 N개의 수를 나열하고, 연속된 수들로 모둠을 여러 개 만든다. (1개에서 N까지 다양하게) 그때, 각 모둠끼리는 모두 직접 연결되어 있어야 하는데 그렇지 않을 경우, 부족한 개수만큼 점수가 오른다. 또 자신의 모둠이 아닌 다른 모둠과 연결되어 있을 때에도 개수만큼 점수가 오른다. 이때 점수의 최솟값을 찾는 문제이다. 이 그림으로 예를 들면, 이 그림에는 모둠이 2개가 존재하는데, 왼쪽에 있는 모둠은 내부에서 부족한 간선의 수는 3개가 되고, 오른쪽에 있는 모둠은 1개, 두 모둠을 잇는 간선 1개로, 이 그림은 5점을 가진다. 이 문제의 N의 범위는 2000 이하 이기 때문에 완전탐색은 통하지 않는다. 그럼 어떻게 풀 수 있을까? 누적 합과 dp 를 사용하면 풀 수 있다. dp [i]를..

문제를 요약하면 동그라미, 세모, 네모를 같은 모양이 연속으로 나열되도록 최소 횟수로 바꾸는 문제이다. 이문제에서 입력이 1,2,3 즉 동그라미, 세모, 네모만 존재하기 때문에 이 3개의 도형을 배치할 수 있는 경우의 수 6개를 반복문으로 탐색하면서 최소 개수를 구해주는 방식을 떠올릴 수 있다. 그다음은 어떻게 최소 개수를 구하냐 인데, 일단 두 도형을 바꿨을 때, 두 도형이 모두 최종적으로 있어야 하는 구간에 들어간다면 이 방법이 두 도형의 최소 변경 횟수가 될 것이다. 예를 들어보자. 1 3 3 2 1 1 3 2 라는 입력이 들어오고, 3 2 1 순서로 나타난다고 해보자. 그러면 최종적으로 3 3 3 2 2 1 1 1 을 만들어야 한다. 초기 입력을 숫자의 개수에 따른 구간을 나눠 보면 1 3 3 |..

요약하면 그래프가 주어지고, Q개의 쿼리에서 X, Y 가 주어지면 X, Y에서 시작하는 스패닝 트리의 최솟값을 구하라는 문제이다. 기존 스패닝 트리와는 다르게 두 점 X, Y에서 스패닝 트리가 시작할 수 있는데 이는 즉, 한 그래프 안에서 스패닝 트리가 2개가 나올 수도 있다는 소리가 된다. 그럼 이를 어떻게 해결할 수 있을까? 그 방법은 스패닝 트리의 특징을 생각해보면 알 수 있다. 스패닝 트리는 N개의 점에 대해 N-1 개의 간선을 가진다. 또 문제에선 X,Y 에서 시작하는 최소 스패닝 트리를 요구하기 때문에 N-1 간선에서 최대 1개의 간선을 제거할 수 있다. 간선을 2개 이상 제거 할 경우, 어떠한 점을 연결할 수 없게 된다. 그러므로 최대 선 1개만 지울 수 있다, 음수 가중치가 없기 때문에 선..

요약하면 i 번째 탑이 있으면 그 탑의 왼쪽에 있는 탑 중에서 i번째 탑의 높이보다 크거나 같은 높이를 가진 탑의 위치를 출력하고 없다면 0으로 출력하는 문제이다. 이 문제는 스택을 쓰면 되는 간단한 문제이다. 왼쪽부터 차례로 돌면서 스택에 있는 값들중 자신보다 작은 값들을 지워준다. 어차피 i+1 이후의 탑들 중 i번째 탑에 막힌다면 그전 탑에는 절대 도달할 수 없고, i 번째 탑보다 커도 그전 탑들은 i 번째 탑보다도 작기 때문에 쓸모가 없다. 그러므로 매 반복마다 i 번째의 탑보다 작은 높이의 탑들을 스택에서 빼주고 남은 스택의 첫 번째 탑의 위치를 구해주면 된다. 만약 스택에 들어있는 값이 없다면 0을 출력해 주면 된다. import sys from collections import deque i..

문제에 쓰여있는 그대로 R를 루트노드라고 하고 LCA(U, V)를 구해주면 끝인 문제이다. 이 문제를 처음 봤을 때 LCA의 sparse table를 입력마다 갱신하는 방법이 바로 떠오르겠지만 그럴 경우 코드를 작성하지 않아도 안된다는 것을 알 수 있다. 그럼 어떻게 해야 할까 이 그림은 위 문제의 테스트케이스를 그래프로 나타낸 것이다. 이때 (U, V)에 대해 R의 위치는 1. R 이 LCA(U, V) 보다 위에 있을 때, 2. R 이 V -> LCA(U, V) 사이에 있는 노드와 연결되어 있을 때, 3. R 이 U -> LCA(U,V) 사이에 있는 노드와 연결되어있을 때, 4. R이 루트 노드를 거쳐 U, V를 가야 할 때 이렇게 총 4개가 나오게 된다. 그럼 처음부터 따져보자. 위 그림은 1번 경우..

이 문제는 여러 가지 풀이 방법이 있지만 이 글에선 유니온 파인드(줄여서 유파)를 이용한 풀이를 사용하겠다. 이 문제를 간단히 요약하면 사용할 수 있는 정점이 주어지면 한 정점에서 다른 정점으로 갈 수 있는 모든 경우의 수를 구하라는 문제이다. 이때 n개의 정점들이 이어져있다고 해보자. n개의 정점들은 자신을 제외한 모든 정점에게 갈수 있다고 할 때 이 그룹에서 나올 수 있는 경우의 수는 n*(n-1)/2 개가 된다. 이 글에선 이걸 이용할 것이다. 일단 처음에 한 정점을 기준으로 번호를 다시 부여해준다.(이 글에선 1번 정점을 기준으로 했다.) 번호를 부여할때 자신의 부모 노드의 번호를 같이 저장한 뒤 입력을 받을 때 새로 부여된 자신의 번호와 부모의 번호를 함께 저장한다. 그 뒤 자신에게 부여된 번호..

문제를 간단하게 요약하면 처음부터 i를 증가하며 카운팅을 하는데 i번째 값이 i 라면 그 값을 지우고 카운팅을 1부터 다시 한다. 이렇게 계속 반복해서 값을 계속 지우는데 지워지는 값이 1부터 차례대로 지워지게 하는 크기가 K이 배열에서 n개의 인덱스가 주어지면 그 위치의 값을 출력하는 문제이다. K=5 일 때 [1, 3, 2, 5, 4] 이렇게 배열을 만들면 차례로 값을 지울 수 있다. 처음에는 i가 1이고 값도 1이므로 1을 지우고 3부터 다시 i=1을 시작해서 카운팅 해 나가면 2가 지워지고 계속 반복하게 되면 1, 2, 3, 4, 5 순서대로 지워지게 된다. 여기서 한가지 알 수 있는 사실은 i 번째 값이 지워졌다면 다음 값은 i+(i+1) = 2i+1 위치에 있어야 한다. 그러므로 1부터 K까지..