거두절미하고.. 제가 생각한 방법들의 시간복잡도는 다음과 같습니다.

1. 한 번의 쿼리에 대해 처리하는 데 O(1)
2. pre-processing O(N),  한 번의 쿼리에 대해 처리하는 데 O(lg N)
3. pre-processing O(N),  한 번의 쿼리에 대해 처리하는 데 O(lg N)
3. pre-processing O(N),  한 번의 쿼리에 대해 처리하는 데 O(lg N)

메모리 복잡도는 모든 문제에 대해서 O(N)


1번. 정수들의 배열 A가 있습니다. 여러분은 정수 i와 j를 입력받아 A[i]부터 A[j] 사이의 값을 모두 더한 결과(A[i] + A[i+1] + ... + A[j-1] + A[j])를 출력하는 프로그램을 만들어야 합니다. 그런데, 이러한 작업을 cntQuery번 수행해야 한다면 어떤 알고리즘을 사용하겠습니까? 그리고 그 알고리즘의 시간 복잡도는 무엇인가요?

먼저, S[n] = A[1] 부터 A[n]까지의 합이라고 정의합니다.  그러면 A[n] + A[n+1] + ... + A[m-1] + A[m] = S[m] - S[n-1] 입니다. S는 또 다음의 관계가 성립하므로 O(N)만에 구할 수 있습니다. S[n] = S[n-1] + A[n]

2번. 1번과 같습니다. 그러나 이번에는 구하여야 하는 것이 달라졌는데, A[i]와 A[j] 사이에서 가장 큰 값을 찾아 출력해야 합니다. 1번의 알고리즘을 변형시켜 그대로 이용할 수 있습니까? 그렇지 않다면 어떤 알고리즘을 이용해야 할까요?

1번과 같은 방법으로 접근해서는 금방 반례에 도달하게 됩니다. 어떤 경우냐면, 사용자가 입력한 쿼리의 범위보다 global minimum이 앞에 있는 경우입니다. 금방 발견할 수 있죠.

어떻게 풀 수 있는지는 3,4번 문제와 같이 설명하겠습니다.

3번. 1번과 같습니다. 그러나 고객이 새로운 요구사항을 추가했습니다. 그것은 배열의 내용을 변경시키고 싶다는 것입니다. 그래서 여러분은 고객이 음수인 i를 입력하였을 경우 A[-i] = j가 되도록 하겠다고 약속했습니다. 이 경우에도 1번의 알고리즘을 사용할 수 있나요? 그렇지 않다면 대안은 무엇입니까?

당연히 1번 알고리즘을 사용할 수 없습니다. A[n]의 값이 변하면 S[n], S[n+1], ... 의 값도 같이 변해야 합니다. 이 과정에서 한 번의 대입과정이 O(N)이 되어버리므로, 하지 않느니만 못할 수 있습니다.

4번. 다른 모든 조건은 3번 문제와 같지만, 구하여야 하는 것은 2번과 같습니다. 이 경우는 어떻게 됩니까?
2,3번과 같은 자료구조를 이용하면 쉽게 풀립니다.


Interval tree를 알고 계십니까? 컴퓨터 과학을 전공하신 분들은 우리말로 구간 나무라고 하기도 하는 이 자료구조에 대해 한 번쯤은 들어본 듯한 기억도 있을 겁니다. CLRS를 보시면 잘 설명되어 있습니다.

간단한 컨셉트를 설명드리면, 이 트리는 기본적으로 Binary Search Tree와 같습니다. 하지만 다른 점이 있다면, 각 노드가 지니고 있는 것은 특정 키 값이 아니라, 어떤 정수 구간입니다. 그리고 이 구간의 사이에 해당 노드의 자손들의 구간이 들어가게 됩니다. [1, 2] 구간을 지닌 노드와 [3,6] 구간을 지닌 노드가 [1,7] 구간을 지닌 노드의 자손으로 들어갈 수 있는 셈입니다.BST의 구간 버전이기 때문에 노드 하나를 삽입하거나 삭제하는데 필요한 비용은 O(lg N)입니다.

이해가 잘 안 되는 분들은 : http://en.wikipedia.org/wiki/Interval_tree 을 참고하시길 바랍니다.

이 트리를 어떻게 하면 이들 문제를 풀기 위해 적용할 수 있을까요? 노드에 값 필드 하나를 추가합니다. 그리고 이 값이 구간 전체의 대표값이 되도록 하는 겁니다. 예를 들어 2번 문제에서 어떤 노드가 나타내는 구간이 [1, 5]이고 대표값이 8이라면, A[1]부터 A[5]까지의 합이 8인 겁니다.

이 인터벌 트리를 일단 구성하면 특정 위치의 값을 변경하는 것은 간단합니다. a[n] = b라는 쿼리가 주어졌다면, [n,n] 구간을 나타내는 노드를 O(lg N) 만에 찾아서, 뿌리 노드까지 올라가면서 대표값을 바르게 갱신하면 됩니다. 이진 탐색 트리이므로 트리의 깊이는 O(lg N)입니다. 따라서 대입 연산의 전체 시간 복잡도가 O(lg N)이 됩니다.

임의의 구간이 주어졌을 때 그 구간 내부에 해당하는 모든 노드를 찾는 연산은 Interval Tree 자체를 공부하시면 나옵니다. 이를 약간 고쳐서 고객이 요구한 답을 찾을 수 있어요. [1, 6] 구간의 대표값을 알고 있다면, [1,3] 구간이나 [4,6] 구간의 대표값을 굳이 알아야 필요가 없겠지요? 이 과정에서는 2 * lg N개 이상의 노드가 필요하지 않습니다. 이 역시 O(lg N)입니다.


그리고 이 Interval Tree를 기반으로 몇 가지 편리한 특성을 추가한 자료구조가 있습니다. 컴퓨터 과학을 전공한 사람이라도 이 자료구조에 대해서는 잘 모르는 경우가 많습니다. 저 같은 경우 Binary Cache Tree라고 부릅니다만 Indexed Tree 라고 부르는 사람도 있고, Hash Tree라고 부르는 사람도 있습니다. 그러나 뭐.. 그냥 Interval tree라고 볼 수도 있겠습니다.

Interval Tree를 사용하는 일반적인 문제들은 대체로 그렇지 않습니다만, 이번에 제가 낸 문제는 배열의 모든 인덱스 각각에 대해서 노드 하나씩을 반드시 사용해야 합니다. 이 경우 Interval Tree는 Binary Tree이므로 Complete Tree가 됩니다. 그렇다면 이 트리를 구현하기 위해 포인터를 포함한 복잡한 구조체를 작성한다거나 할 필요가 있을까요?

Complete Binary Tree를 이용하는 자료구조의 전형적인 예가 있습니다. 바로 Heap입니다. Heap 구현하실 때 트리구조를 나타내기 위해 무엇을 이용합니까? 배열이죠. 마찬가지로 배열을 이용해 이 자료구조를 구현하면 다음과 같은 편리한 특성들을 얻을 수 있습니다.

1. N개의 데이터가 미리 주어져 있을 때, 이 데이터를 Tree에 모두 삽입하는 데 걸리는 시간복잡도는 O(N lg N)이 아닌 O(N)입니다. 맨 아래 레벨에 미리 채워두고 나머지 칸을 거꾸로 순회하면서 해당 노드의 대표값을 구할 수 있습니다.
2. 어떤 노드가 부모의 왼쪽 자식인지, 오른쪽 자식인지를 나머지 연산으로 구할 수 있습니다.
3. N = 2 ^ k이면, 필요한 배열의 크기는 2*N입니다.
4. 코딩이 간단하고 편리합니다.
5. 각 노드가 자신이 나타내는 구간의 시작과 끝을 굳이 저장하고 있을 필요가 없습니다. 뿌리 노드가 나타내는 구간의 크기는 1이고, 그 윗 레벨에서는 2입니다. 또 그 위의 레벨에서는 4죠. 이러한 관계로부터 알아낼 수 있습니다.


알고리즘과 자료구조는 공부하면 할 수록 재미있는 분야입니다. 프로그래밍을 해 본 사람들만이 느낄 수 있는 즐거움이 있어요. 저는 지금까지 공부하면서 재밌다고 느낀 것은 얘들 뿐입니다. 여러분도 한번 그 재미를 느껴 보세요.