알고스팟의 MORDOR 풀기 위해 '구간 최소 트리'(이하 RMQ)를 구현했습니다.
RMQ에 관해서 간략하게 설명하자면,
'특정 구간에서 최소값은 무엇인가?' 에 대한 답을 구하기 위해 binary tree를 응용해서 최소값을 구할 수 있는 tree를 미리 구현하고 이를 활용하는 것입니다.
예를 들면 0~9까지 10개의 길이를 가지는 어떤 배열에서 다음의 질의(Query)에 답할 수 있습니다.
0~5 중 가장 작은 값은?
2~9 중 가장 작은 값은?
subarray의 min으로도 처리 할 수 있는데, subarray 생성시간 + min 연산시간(O(n)) 이 소모되는 반면, 이미 구성해둔 tree에서의 search 는 O(logn) 의 시간에 답을 구할 수 있습니다.
기본 원리는
1. 각 구간을 binary tree로 쪼갬
2. 각 구간 중 가장 작은 값을 저장
위의 예에서 다음과 같은 값들이 저장됩니다.
0~9: 가장 작은 값
0~4: 가장 작은 값, 5~9: 가장 작은 값
0~2: 가장 작은 값, 3~4: 가장 작은 값, 5~7: 가장 작은 값, 8~9: 가장 작은 값
각각의 leaf에는 자기 자신 저장
이와 같은 형태로 구성됩니다.
Query로 구간(Range)를 받으면, 생성된 Tree에서 어떤 Node가 필요한지를 알아낸 뒤에 그 중 가장 작은 값을 Return 합니다.
예에서 0~5라면 0~4의 최소 값를 저장한 노드와 5 (는 하나니까)노드가 필요합니다.
이 중 작은 값을 Return 하면 됩니다.
이런 알고리즘의 구현이 '알고리즘 문제해결 전략' 책에는 C로 되어 있는데, 그냥 Python 으로 옮겼습니다.
여기에는 Binary Tree 구현을 위해 Array를 사용했는데요, Left와 Right를 odd, even으로 mapping 시켰습니다. 비교적 꽉 찬 이진트리의 경우 이렇게 구현하는 것이 메모리를 좀 더 효율적으로 쓴다고 하니 참고하세요.
Array의 길이는 주어진 n과 가장 가까운 2의 제곱 수에 2를 곱한 만큼입니다.
가령 n = 6이면 가장 가까운 2의 제곱 수인 8(2^3) 에 2를 곱한 16입니다.
구현에서는 이것이 귀찮으므로 넉넉하게 계산했습니다.
#!/usr/bin/python
import sys
class RMQ(): #Range Minimum Query
RMList = []
length = 0
def __init__(self, targetList):
self.length = len(targetList)
self.RMList = [""]*self.length*4
self.init(targetList, 0, self.length-1, 1)
def init(self, targetList, left, right, nodeIdx):
if left == right:
self.RMList[nodeIdx] = targetList[left]
return targetList[left]
mid = (left + right) / 2
leftMin = self.init(targetList, left, mid, nodeIdx*2) # left idx is even number
rightMin = self.init(targetList, mid+1, right, nodeIdx*2+1) # right idx is odd number
self.RMList[nodeIdx] = min(leftMin, rightMin)
return self.RMList[nodeIdx]
def _query(self, left, right, nodeIdx, nodeLeft, nodeRight):
if right < nodeLeft or nodeRight < left: return sys.maxint
if left <= nodeLeft and nodeRight <= right: return self.RMList[nodeIdx]
mid = (nodeLeft + nodeRight) / 2
return min(self._query(left, right, nodeIdx*2, nodeLeft, mid),
self._query(left, right, nodeIdx*2 + 1, mid+1, nodeRight))
def query(self, left, right):
return self._query(left, right, 1, 0, self.length - 1)
책의 구현이 워낙 깔끔해서 더 수정할 부분은 없는 것 같습니다.
다만 이렇게 구현하고, 문제를 도전(!!!) 했으나 시간초과.......
보니까 C,C++,Java 만 문제를 풀었더군요-
pypy로도 안되는 것을 보면, 아무래도 Python 으로는 한계가 있는게 아닐까 싶습니다.
좀 더 빠르게 하는 방법이 있으면 생각해봐야죠-
