티스토리 뷰


ICC

$N$개의 정점으로 이루어진 그래프가 있다. 그래프의 초기 상태에는 간선이 하나만 존재한다. 두 정점 집합 사이에 간선이 있는지 묻는 질문을 통해 간선이 무엇인지 알아낸다. 알아낸 이후에 새로운 간선이 또 추가된다. 항상 싸이클이 생기지 않도록 간선이 주어지며, 이 작업을 총 $N-1$번 수행하고 질문을 가능한 적게해야하는 문제다.


처음 상황, 즉, $N$개의 정점이 있고 그들 사이에 간선이 하나만 있는 상황에서 생각해보자. 우선 간선을 가지고 있는 임의의 두 정점 집합을 최대한 적은 질문안에 찾아야한다. 이는 최대 $\lceil\lg N\rceil - 1$번 질문만에 찾을 수 있다. 바로 각 정점 번호를 0번부터 N-1번까지 나타낼 때, 각 비트에 대해 비트값이 0인 집합과 비트값이 1인 집합 사이에 간선이 있는지 질문하면 항상 집합 사이에 간선이 있는 두 서로소 집합이 나온다. 이 때 비트 수 만큼 질문하지 않고, 한 번의 질문을 아낄 수 있다. LSB부터 MSB까지 각 비트에 대해 질문하다가 MSB까지 사이에 간선이 있는 두 집합이 안나오면 MSB에서 나누어지는 두 집합 사이에 항상 간선이 있기 때문이다.


위에서 구한 두 정점 집합을 $G_1$, $G_2$라 하자. 이제 $G_1$에 있는 어떤 정점과 $G_2$에 있는 어떤 정점 사이에 간선이 있다. 간선이 잇는 두 정점은 약 $\lg |G_1| + \lg |G_2|$번의 질문을 통해 찾을 수 있는데 한 번의 질문을 통해 두 정점 집합 중 한 집합의 크기를 절반으로 만들 수 있기 때문이다.


첫 간선을 찾은 이후 그 간선이 잇는 두 정점을 하나의 정점으로 보고 위 알고리즘을 총 $N-1$번 반복해주면 된다. 이 때, 최대로 걸리는 경우를 계산해보면 1625번 안에 나온다.


코드 보기


Kangaroo

N개의 칸으로 이루어진 공간에서 시작점과 도착점이 주어졌을 때, 왼쪽-오른쪽-... 아니면 오른쪽-왼쪽-... 번갈아가면서 여행하는 경우의 수를 구하는 문제다.


5개의 칸이 있고 3번 칸에서 시작해서 5번 칸으로 이동하는 수열 [3, 1, 4, 2, 5] 를 그림으로 그려보면 아래와 같이 위 아래로 지그재그함을 알 수 있다.


위와 같은 꼴의 모양 중 맨 왼쪽 점이 시작점이고, 맨 오른쪽이 도착점인 경우의 수를 구하는 문제로 바꿀 수 있다. 경우의 수는 동적계획법으로 해결할 수 있으며, 다이나믹 배열 정의는 아래와 같다.


D[i][j] = 1번부터 i번까지 점을 추가했고 지그재그한 그룹의 개수가 j일 때 경우의 수



위 그림에서 세 개의 네모 영역은 각각 그룹을 나타낸다. 시작점과 도착점을 포함한 그룹을 제외하면 위 그림처럼 그룹 안의 양 끝 점은 아래로 내려가있다. 만약 i번 점이 지그재그의 윗 점이 되는 경우 위 그림처럼 인접한 두 그룹을 합치는 꼴이고, i번 점이 지그재그의 아래 점이 되는 경우 새로운 그룹을 만드는 꼴이다. i번 점이 시작점이거나 도착점인 경우는 조금 다르게 점화식을 세워야한다.


1) i가 시작점, 도착점이 아닌 경우: D[i][j] = D[i-1][j+1] * j + D[i-1][j-1] * (j - 시작점이나 도착점을 포함한 그룹 개수)

2) i가 시작점이거나 도착점인 경우: D[i][j] = D[i-1][j] + D[i-1][j-1]


이처럼 동적계획법을 통해 문제를 $O(N^2)$ 시간안에 해결할 수 있다.


코드 보기


Match

길이가 N인 알파벳 소문자로만 이루어진 문자열이 주어진다. 이 문자열을 괄호문자열로 바꿀 수 있는데, 바꿀 수 있는 괄호문자열 중 사전순으로 제일 앞선 괄호문자열을 구하는 문제다.


현재 문자열의 가장 왼쪽 글자를 $l$이라 하자. 같은 두 글자를 괄호문자열에서 짝이 되는 올바른 괄호문자열이 존재한다는 것을 매칭된다고 표현하자. $[s, e]$는 문자열의 부분문자열을 나타낸다.


Lemma 1) $l$과 매칭되는 가장 오른쪽 글자를 $r$이라 하자. $r$과 $l$을 매칭시켜주는 것이 사전순으로 가장 앞선 괄호문자열을 만든다.


이제 작은 두 문제로 전체 문제를 분할할 수 있다. $[l+1, r-1]$에서 사전순으로 가장 빠른 괄호문자열을 구하고, $[r+1, L]$에서 가장 빠른 괄호문자열을 구하면 전체 문제가 해결된다. $r$을 $O(N)$에 구하면 전체 시간복잡도가 $O(N^2)$이 된다.


전체 문자열에서 첫 번째 글자부터 $i$번째 글자까지 그리디 알고리즘을 돌렸을 때, 스택의 상태를 문자열로 나타내고 이를 $K[i]$라 하자.


Lemma 2) $[s, e]$가 올바른 괄호 문자열을 만들기 위한 필요충분조건은 $K[s-1] = K[e]$이다.


Lemma 3) $l$과 $r$이 매칭되기 위한 필요충분조건은 $l$과 $r$이 같은 알파벳이면서 $[l+1, r-1]$이 올바른 괄호문자열을 만든다는 것이다.


위 두 명제를 통해 $r$을 Trie와 이분탐색을 통해 $O(\lg N)$ 시간안에 구할 수 있다.


코드 보기


저작자 표시
신고
댓글
댓글쓰기 폼