알고리즘 문제를 해결하는 것이 목표인 대회들이 있습니다. 대표적으로는 국제정보올림피아드(IOI)가 있으며 여기에 참여할 국가대표를 뽑기 위한 한국정보올림피아드(KOI), 그 외에도 ACM-ICPC, Topcoder, Codechef 등 여러 오프라인 및 온라인 대회들이 있습니다. 오늘 진행된 구글 코드잼 같은 대회는 성적에 따라서 구글에서 채용하기도 할 정도지요
제가 풀어본 문제들 중 몇가지를 올리고 제가 어떻게 풀었는지 한번 경험을 공유해보고자 합니다.
시간제한: 12초
테스트 케이스당 시간 제한 : 5초
메모리 사용량 제한 : 65536KB
여기 배열이 하나 있습니다. 이 배열의 크기는 n으로 10^6을 넘지 않습니다. 그리고 이 배열의 왼쪽 끝에서 오른쪽 끝으로 움직이고 있는 슬라이딩 윈도우가 있습니다. 이 윈도우의 길이는 k입니다. 여러분은 윈도우 안에 보이는 k개의 수만을 볼 수 있습니다. 윈도우는 한 번에 한 칸씩 오른쪽으로 움직입니다. 다음은 예제입니다.
예제는 원문 출처로 가서 보시기 바랍니다.
문제 출처 : http://poj.org/problem?id=2823
슬라이딩 윈도우가 각 위치에 있을 때 보이는 최대값과 최소값이 무엇인지 구하는 것이 여러분에게 주어진 문제입니다.
입력
입력은 두 개의 줄로 이루어져 있습니다. 첫 번째 줄은 배열의 길이와 슬라이딩 윈도우의 길이를 나타내는 두 개의 정수n과 k를 담고 있습니다. 다음 줄에 배열의 내용을 나타내는 n개의 정수가 담겨 있습니다.
출력
출력은 두 개의 줄을 담고 있어야 합니다. 첫 번째 줄은 윈도우가 왼쪽에서 오른쪽으로 움직일 때마다 윈도우에 보이는 최소값을 나타냅니다. 두번째 줄은 최대값입니다.
주의 : 지금부터는 이 문제의 풀이입니다. 직접 문제를 풀어보고 싶으신
분들은 읽지 말아주세요. 스포일러 방지 기능이 있으면 좋을텐데 없군요.
Naïve Solution
가장 간단한 풀이는 각 위치에 대해서 슬라이딩 윈도를 직접 대어 보고 최대값과 최소값이 무엇인지 찾는 것입니다. 2중 for문을 통해서 구현하면 되겠죠. O(NK)입니다
소스 코드 : http://ideone.com/c0bBrQ
하지만 이 풀이는 너무나 느립니다. N의 크기가 1000000까지 될 수 있고 K도 마찬가지이므로 이런 경우에는 아무리 코드를 최적화한다 하더라도 시간내에 답이 나오지 않습니다.
Min-max Heap
Heap이라는 자료구조가 있습니다. 이 자료구조의 한 변형인 Min-max Heap은 현재 Heap 안에 들어있는 원소들 중 최소값과 최대값이 무엇인지 상수 시간에 알 수 있으며, 하나의 원소가 삽입되고 제거될 때마다 O(lg N)만큼의 연산이 소요됩니다. (Deap이라는 변형에서도 가능합니다) 그런데 이때 최대값과 최소값 이외의 모든 값에 대해서 어느 위치에 있는지를 하나하나 추적하게끔 구현할 수 있습니다. N의 최대값은 백만인데, 백만개 정도 정수배열을 하나 더 잡는다고 해서 메모리 경계를 초과하지는 않습니다.
그러므로 Min-max heap이나 Deap을 사용해서 슬라이딩 윈도우가 오른쪽으로 이동할 때마다 추가되는 수를 자료구조에 집어넣고, 빠져나가는 수를 자료구조에서 빼는 식으로 구현할 수 있습니다. 이렇게 한 경우 시간복잡도는 O(N lg N)입니다. 충분히 시간 내에 나올 수 있지요. 그런데 일반적으로 구현된 라이브러리에는 min, max를 제외한 다른 원소를 추적하는 기능이 없습니다. 어쩔 수 없죠. 원래 그걸 위한 자료구조가 아닌걸요… 직접 구현하는 수밖에 없습니다. 이 방법에 대해서는 따로 코드를 첨부하지 않겠습니다.
Binary-search Tree
이진 탐색
트리는 이진 트리의 일종으로 각 노드의 왼쪽 자식은 부모 노드가 지닌 값보다 작은 값을 지니고, 오른쪽 자식은 부모보다 큰 값을 갖도록 구성되어 있습니다. 균형잡힌 이진 트리의 경우 데이터의 삽입, 삭제가 O(lg N)만에 가능합니다.
그리고 중요한 특징은, 이진 탐색 트리의 최소값과 최대값 역시 O(lg N)에 구할 수 있다는 것입니다. 이 방법 역시 O(N lg N)에 해결이 가능합니다.
소스 코드 : http://ideone.com/V3anCU
Indexed Tree
인덱스 트리라는 자료구조는 완전 이진 트리의 일종인데, 알고리즘 경시에
참여하는 사람들 사이에서 통용되는 이름입니다. 구간 트리라고도 불리는데 일반적인 구간 트리와는 약간
다릅니다.
일단 이 트리는 완전 이진 트리이므로 .N보다 크거나 같은 가장 작은 2의 지수를 M이라 할 때,
2*.M개의 저장공간을 필요로 합니다.
각 노드는 자신이 가리키는 구간을 ‘대표하는’ 값을 지니게 됩니다. 예를 들어 이 문제의 경우 트리의 루트 노드는 Min( Array[0..M-1] ) 또는 대응되는 Max의 값을 가지게 되겠죠. 루트의 왼쪽 노드는 0 ~ M/2-1까지의 구간을 대표하고, 루트의 오른쪽 노드는 M/2 ~ M-1까지를
대표하고.. 이런 식으로 깊이가 한단계 깊어질 때마다 노드가 대표하는 구간의 크기가 절반씩 줄어듭니다. 깊이가 log M이 되면 각각 길이 1의 구간을 대표하고 있게 되죠. (그 위치에 해당하는 Array의 값을 지닌다는 뜻)
트리의 갱신은 일단 가장 끝부분의 값을 바꾸고, 부모 노드를 하나씩
타고 올라오면서 값을 갱신해 줍니다. 두 자식의 값을 보고 자기자신을 바꾸는 recursive 함수를 작성하면 되겠죠?
이렇게 하면 임의의 구간에 대한 값을 구하는 건 lg M 개의 노드만 선택하면 어떤 구간이라도 커버가 가능하기 때문에… O(lg M) = O(lg N)입니다. M < 2*N이니까요.
지금까지 O(N lg N) 솔루션을 보았습니다. 그런데… 사실 이 문제를 해결하는 가장 빠른 알고리즘의 시간복잡도는 O(N)입니다. 믿기시나요?
일단 배열을 2*K-1개씩 쪼갭니다.
K=4이라면 배열을 7개 단위로 자르게 되겠네요. 다음을 봅시다.
A[0] A[1] A[2] A[3] A[4] A[5] A[6]이때 중앙에서부터 계산을 시작하면 다음과 같은 배열은 O(K)만에
계산이 가능하겠죠?
Min[0..3] Min[1..3] Min[2..3] A[3] Min[3..4] Min[3..5] Min[3..6]
그런데 이걸 잘 보시면요. 이 배열만으로 슬라이딩 윈도우 내에서 최소값이
무엇인지 다 알 수 있어요.
Min[0..3]은 배열 안에 있고요. Min[1..4] = Min[1..3]과 Min[3..4] 중 작은 값이죠.Min[2..5]는 Min[2..3]과 Min[3..5]중에 작은 값이죠…
어헣 간단하죠?
2*K-1개씩 배열을 나누면 대충 O(N/K)개의 부분배열이 나오죠? 각각의 부분배열에서 최대값과 최소값을 구하는 것은 O(K)만에 되니까 O(N/K) * O(K) = O(N) 이 되는 것입니다.
코드 : http://ideone.com/sduj2J
이 코드는 2007년에 제가 고딩이었던 시절에 작성한 거라 좀 더럽긴 한데 뭐 방법 자체는 충실히 구현하고 있습니다.
생각보다 길어졌네요. 과연 시리즈물로 찾아뵐 수 있을는지?