[실전 알고리즘] 0x16강 - 이진 검색 트리

 

안녕하세요, 이번 강의에서는 이진 검색 트리를 배워보겠습니다. 아마 이진 검색 트리도 해시처럼 어디에선가 들어보신 분이 많을 것 같습니다.

 

목차를 보고 혹시 뭔가 이상한 점을 눈치챈 분이 계실지 모르겠습니다. 이상한 점이라기보다는 이전 단원과 다른 점이라고 볼 수도 있겠는데, 구현이 아예 빠져 있습니다. 강의에서 구현의 필요성을 늘 강조했었지만 이진 검색 트리는 구현을 안할 예정입니다. 왜 안하냐면 첫 번째로 저희는 트리를 아직 배우지 않아서 설령 이진 검색 트리를 배워도 구현을 아직 할 수가 없습니다. 두 번째 이유는 사실 이게 구현을 다루지 않는 가장 큰 이유인데 설령 어찌저찌 이진 검색 트리를 구현했다고 쳐도 저기 챕터에 보이는 자가 균형 트리라는걸 적용하지 않으면 시간복잡도가 안 좋아져서 써먹을 수가 없습니다. 그렇다고 자가 균형 트리까지 구현을 하자고 하니 자가 균형 트리는 난이도가 헬이라 현실적으로 방법과 구현을 알려드린다 해도 그냥 관상용이지 실제로 문제를 풀 때 저거를 기억하고 있다가 밑바닥에서 구현하는건 그냥 불가능하다고 보시면 됩니다. 그래서 어차피 써먹지도 못할거 구현은 다 뺐습니다.

 

그러면 우리는 어떻게 해야 하는가, 우리에겐 무적의 STL이 있기 때문에 마음 편하게 STL을 가져다 쓰면 됩니다. 만약 STL을 쓸 수 없는 환경에서 이진 검색 트리를 쓰고 싶으면 어떻게 해야 하나 했을 때, 그럴 때에는 어떻게든 이진 검색 트리를 쓰지 않는 풀이를 찾아내야 합니다. 그냥 이진 검색 트리 자체를 구현하는 것도 실수할 여지가 많고 쉽지 않지만 앞에서 말했다시피 자가 균형 트리가 적용되지 않은 이진 검색 트리는 시간복잡도가 안좋아서 높은 확률로 시간 초과가 발생할거라 의미가 없습니다. 어떻게든 해시나 이분 탐색과 같은 다른 방법을 이용하는 풀이를 고민해야 합니다. 그러면 내용으로 들어가봅시다.

 

일단 이진 검색 트리는 뭔가 특별한 성질을 만족하는 트리인데 트리가 뭘까요? 아직 그래프와 트리 자료구조에 대해 공부를 하지 않았어서 엄밀한 정의를 소개해드릴 수는 없습니다. 그냥 트리는 지금 이 그림처럼 뭔가 계층 구조를 가지고 있고, 제일 꼭대기를 제외하고 각 동그라미들은 위로 딱 1개와 연결이 되어있는 녀석이라고만 받아들이고 넘어가겠습니다.

 

정의는 약간 불완전하지만 아무튼 적당히 이해했다고 치고, 트리에서 쓰이는 용어들을 몇 가지 정리해보겠습니다. 첫 번째로 트리에서의 각 원소는 정점이라고 부릅니다. 노드라고 부르기도 하는데 완전히 같은 뜻입니다. 트리의 제일 꼭대기에 위치한 정점은 루트입니다. 주어진 트리에서는 1번 정점이 루트입니다. 그리고 제일 말단에 위치해서 아래로 뻗은게 없는 정점은 리프입니다.

 

다음으로 정점을 연결하는 선은 간선입니다.

 

그리고 간선으로 연결된 위 아래의 관계를 부모 자식 관계라고 부릅니다. 예를 들어서 3번 정점은 7, 8번 정점의 부모 정점이고 7, 8번 정점은 3번 정점의 자식 정점입니다.

 

어떤 한 정점에 대해 그 밑에 있는 정점과 간선만을 모은 트리를 서브트리라고 합니다. 주황색으로 표시한 트리는 2번 정점에 대한 서브트리입니다.

 

마지막으로 트리의 높이는 위 아래로 뻗어있는 정도를 나타냅니다. 노드가 1개만 있을 때의 높이를 1로 두느냐 0으로 두느냐에 따라서 주어진 트리의 높이가 3일 수도 있고 4일 수도 있긴 한데 크게 중요한 부분은 아닙니다.

 

그러면 이제 이진 트리를 정의할 수 있는데, 이진 트리는 각 노드의 자식이 2개 이하인 트리를 말합니다. 자식이 2개 이하이기 때문에 자식을 왼쪽 자식과 오른쪽 자식으로 구분할 수 있습니다. 예를 들어 2번 정점은 1번 정점의 왼쪽 자식이고 3번 정점은 1번 정점의 오른쪽 자식입니다.

 

드디어 이진 검색 트리를 이해하기 위한 모든 과정이 끝났습니다. 왼쪽 서브트리의 모든 값은 부모의 값보다 작고 오른쪽 서브트리의 모든 값은 부모의 값보다 큰 이진 트리를 이진 검색 트리라고 합니다. 예를 들어서 값이 2인 정점을 보면 왼쪽 서브트리에 있는 1은 2보다 작고, 오른쪽 서브트리에 있는 3, 4는 2보다 큽니다. 값이 5인 정점도 살펴보면 왼쪽 서브트리에 있는 1, 2, 3, 4는 5보다 작고 오른쪽 서브트리에 있는 6, 7, 8은 5보다 큰걸 확인할 수 있습니다.

 

그냥 데이터를 배열이나 연결 리스트에 저장하면 되지 왜 굳이 이진 검색 트리를 써서 저장하는건가 하는 의문이 자연스럽게 들 수 있는데, 이진 검색 트리를 활용하면 insert, erase, find, update를 모두 O(lg N)에 처리할 수 있습니다. 예를 들어 배열에서 insert는 제일 뒤에 붙이면 되니 O(1)이라고 해도 erase는 배열 중간에 있는 원소가 제거될 상황이 나올 수 있으니 O(N)입니다. find, update 또한 전부 O(N)입니다. 그런데 이진 검색 트리는 저 연산들이 전부 O(lg N)이기 때문에 erase/find/update가 빈번하다면 이진 검색 트리를 활용할 수 있습니다. 그런데 여기까지만 보면 해시는 비록 충돌때문에 성능이 안 좋아질 수 있지만 기본적으로 저 4개의 연산이 O(1)이니까 그냥 해시가 이진 검색 트리의 상위 호환이 아닌가 하는 생각을 할 수 있습니다.

 

다행히 그렇지는 않고 해시에는 없는 이진 검색 트리의 강력한 또 다른 특성은 원소가 크기 순으로 정렬된다는 점에 있습니다. 예를 들어 해시에 1, 3, 5, 7, 9를 넣어뒀다고 해보겠습니다. 그런 상황에서 5보다 큰 최초의 원소가 무엇인지를 알고 싶습니다. 그러면 해시에서는 이 연산을 효율적으로 수행할 방법이 아예 없습니다. 해시라는 구조 자체가 원소를 크기 순으로 저장하는 자료구조가 아니기 때문입니다. 반면 이진 검색 트리에서는 5보다 큰 최초의 원소가 무엇인지를 O(lg N)에 알아낼 수 있습니다. 그렇기 때문에 insert, erase, find, update 등이 빈번하면서 동시에 뭔가 원소의 대소와 관련한 성질이 필요할 경우에는 이진 검색 트리를 사용해야 합니다.

 

그러면 실제로 insert, erase, find, update를 어떻게 수행할 수 있는지 같이 살펴보겠습니다. 먼저 45를 삽입하면 맨 처음에는 아무 것도 없으니까 45를 바로 루트로 만듭니다.

 

다음으로 25를 삽입할건데 25는 45를 기준으로 왼쪽에 있을까요? 오른쪽에 있을까요?

 

이진 검색 트리에서 부모보다 작은 값들은 왼쪽에 위치해야 하니 왼쪽에 있게 됩니다. 45의 왼쪽에 25를 부착합니다.

 

다음으로 35를 삽입할건데, 또 마찬가지로 루트인 45에서 출발한 후에 왼쪽으로 갈지 오른쪽으로 갈지 정해야 합니다.

 

35가 45보다 작으니 왼쪽으로 가는건 당연한건데, 왼쪽에는 이미 25가 있기 때문에 왼쪽에 바로 부착할 수는 없습니다. 그래서 25에서 왼쪽으로 갈지 오른쪽으로 갈지 또 정해야 합니다.

 

35가 25보다는 크기 때문에 오른쪽으로 가야하고 최종적으로 35는 25의 오른쪽에 부착되면 됩니다. 이런 식으로 현재 보고 있는 값과의 대소비교를 통해 빈 공간을 찾을 때 까지 왼쪽 혹은 오른쪽으로 계속 이동하면 됩니다. 이 다음부터는 설명을 조금 간소화해서 바로바로 넣겠습니다.

 

55를 삽입해보면 45의 오른쪽으로 가게 됩니다.

 

그 다음 50을 삽입하면 55의 왼쪽으로 갑니다.

 

마지막으로 15를 삽입하면 25의 왼쪽으로 가게 됩니다. 삽입은 이 정도로 보고 넘어가겠습니다.

 

다음으로는 데이터를 찾아보겠습니다. 검색도 삽입과 비슷하게 루트에서 출발한 후 좌우로 움직이면 됩니다. 예를 들어서 35를 한 번 찾아보겠습니다. 일단 출발은 루트인 45에서 하면 될거고 여기서 35를 찾기 위해 어디로 가야할지 생각을 해보겠습니다.

 

35는 45보다 작기 때문에 왼쪽입니다.

 

그 다음에는 오른쪽으로 가야 합니다. 지금 보고 있는 값이 딱 35가 되었기 때문에 찾는 과정이 끝납니다.

 

사실 이진 검색 트리에서 가장 어려운 부분은 정점의 제거입니다. 그냥 없애버리면 되는게 아니라 상황이 좀 복잡한데, 지금 그림처럼 무턱대고 지워버리면 트리 구조가 깨져버립니다. 그러면 제거를 어떻게 수행할 수 있을지 같이 보겠습니다.

 

먼저 자식이 없는 정점을 지울 때에는 다행히 상황이 좀 쉬운데, 그냥 지워도 구조를 망가뜨리지 않습니다.

 

자식이 1개인 정점을 지우는 것도 괜찮은데, 이 경우에는 자식을 지워진 노드의 자리에 올리면 됩니다. 그림에서 15를 지울 때 10을 올려서 원래 이진 검색 트리의 정의인 왼쪽 서브트리의 모든 값은 부모의 값보다 작고 오른쪽 서브트리의 모든 값은 부모의 값보다 큰 이진 트리라는 조건이 잘 만족되도록 했습니다.

 

하지만 자식이 2개인 정점을 지우는 이 과정은 상당히 골치가 아픈데, 자식이 1개인 정점을 지울 때와 비슷하게 처리해보겠다고 25의 자식인 15와 35를 다 45에 달아버리면 45의 자식이 3개가 되어버리니 그럴 수가 없습니다. 뇌를 비우고 구현하는 방법 중 하나로 그냥 25 밑에 있는 10, 13, 15, 32, 34, 35, 40을 싹 다 지웠다가 다시 삽입을 하면 해결이 되긴 할텐데 저희는 최대한 연산을 덜 하는 방향으로 삭제를 구현하고 싶습니다. 가장 좋은 방법은 구조를 보존할 수 있게 어떤 적절한 정점을 25가 있는 위치로 옮기는건데, 25 밑에 있는 정점들 중에서 어떤걸 25의 자리로 옮겨도 될까요?

 

일단 32를 보면, 32를 지우고 25의 자리로 보내버리면 여전히 이진 검색 트리의 성질을 잘 만족합니다. 32를 지우면 자연스럽게 34도 위로 올라갑니다. 그런데 왜 하필 32가 이러한 성질을 만족하는걸까요? 그 이유는 바로 32가 25보다 크면서 가장 작은 원소이기 때문입니다. 그렇기 때문에 32는 25의 왼쪽에 있는 10, 13, 15보다는 크고, 25의 오른쪽에 있는 34, 35, 40보다는 작은 수가 되어서 지금 25의 위치로 와도 아무런 문제가 없습니다. 실제 구현을 할 때 32를 어떻게 찾냐면 지우고 싶은 원소에서 일단 오른쪽 자식을 보고 거기서부터 계속 왼쪽으로만 가면 됩니다. 비슷한 느낌으로 25보다 작으면서 가장 큰 15를 골라도 상관 없습니다.

 

그런데 지금 32를 지우고 25로 옮기는게 별 문제 없었던 이유가 32의 자식이 1개여서였습니다. 만약 32의 자식이 2개였으면 32를 지우는게 또 복잡해질텐데 이런 경우에는 어떻게 해야할까요? 한 번 고민을 해봅시다.

 

다행히 그런 일은 일어날 수가 없습니다. 만약 32에 왼쪽 자식이 있었다면 그 원소는 25보다 크고 32보다 작아야 합니다. 그렇기 때문에 왼쪽 자식이 있다면 32가 25보다 크면서 가장 작은 원소일 수 없습니다.

 

이렇게 이진 검색 트리에서 삽입, 검색, 삭제를 어떻게 하는지 알아봤습니다. 세 과정은 모두 트리의 높이가 얼마인지에 따라서 시간복잡도가 정해집니다. 만약 왼쪽 트리처럼 각 정점이 대부분 2개의 자식을 가지고 있다면 높이가 하나 내려갈 때 마다 자식의 수가 1, 2, 4, 8, ... 이렇게 2배씩 증가하기 때문에 정점이 N개 있다고 하면 높이가 대략 lg N입니다. 이 경우에는 시간복잡도가 O(lg N)입니다. 반면 오른쪽 그림처럼 트리가 편향되어 있다면 높이가 O(N)에 가깝기 때문에 이 경우 시간복잡도가 O(N)입니다. 우리는 각 연산을 O(lg N)에 수행하려고 이진 검색 트리를 쓰는건데 만약 트리가 오른쪽 그림처럼 생기면 그냥 사실상 Linked List에서 삽입, 검색, 삭제를 하는 것과 별반 차이가 없는 상황이 나와서 그냥 이진 검색 트리를 쓰는 이유가 없어집니다. 그리고 1, 2, 3, 4, ... 이렇게 크기 순으로 주어진 원소를 삽입한다면 1이 루트이고 나머지 원소들이 오른쪽에 일직선으로 연결되는 편향된 트리가 되니 편향된 트리가 만들어지는 상황은 아주 잘 발생할 수 있습니다.

 

그렇기 때문에 이진 검색 트리가 편향되면 그걸 해결해줄 필요가 있습니다. 이러한 트리를 자가 균형 트리(Self-Balancing Tree)라고 부르고 대표적으로 AVL 트리, Red Black 트리가 있습니다. 둘 중에서 AVL은 구현이 조금 쉬운편인데 성능 자체는 Red Black 트리가 더 좋아서 STL에 있는 이진 검색 트리는 Red Black 트리를 가지고 구현되어 있습니다.

 

진짜 간단하게 원리를 설명드리면 지금 이 그림처럼 뭔가 불균형이 발생했을 때 트리를 꺾어버립니다. 이러면 불균형을 없앨 수 있습니다. 아주 간단하게 설명하면 이런거고, 둘 중 어느 하나라도 어떻게 동작하는지를 알고 나면 드디어 실제로 써먹을 수 있는 이진 검색 트리를 구현할 수 있어서 설명을 드리고 싶긴 한데 문제는 방법이 너무 복잡합니다. 삽입/삭제가 일어날 때 마다 불균형을 확인해야 하는데 각 정점의 자식이 0개/1개/2개일 때 이런 식으로 케이스를 나눠서 각각 방식을 설명해야 하고 뭐 여러가지로 쉽지가 않습니다. 그래서 자가 균형 트리가 무엇이고, 왜 필요한지, 그리고 아주 대략적으로나마 구현이 어떤 식으로 이루어지는지만 안걸로 만족하고 자세한건 설명을 생략하겠습니다. 이렇게 편향성을 해소해주는 자가 균형 트리를 사용할 때 비로소 이진 검색 트리에서 삽입, 검색, 삭제가 모두 O(lg N)이 됩니다.

 

계속 강조했지만 이진 검색 트리는 이미 STL에 구현이 잘 되어 있고 특히 트리의 편향 문제로 인해 직접 구현하는게 불가능에 가깝기 때문에 앞으로 이진 검색 트리가 필요할 때에는 STL을 애용하게 됩니다. STL에 구현된 해시는 이름이 unordered_set, unordered_multiset, unordered_map이었고 이진 검색 트리는 이름이 set, multiset, map입니다. 앞에 붙어있던 unordered_ 이게 빠져서 타이핑 치기는 편합니다. 인터페이스도 거의 똑같아서 이번에 처음 봤지만 친숙하게 쓸 수 있습니다.

 

먼저 set부터 소개를 해보겠습니다. 14번째 줄 이전의 내용은 unordered_set이랑 차이가 없습니다. 단 이진 검색 트리는 내부적으로 원소가 크기 순으로 저장이 되어있긴 합니다. 그런데 15번째 줄부터 나오는 저 부분이 set이 unordered_set과 차별화되는 점입니다. unordered_set에서는 "-40보다 크면서 가장 작은 원소가 무엇인가?" 라는 문제를 풀기 위해서는 그냥 그냥 모든 원소를 다 살펴보는 방법 밖에는 없었습니다. 반면 set에는 원소가 정렬되어 있기 때문에 O(lg N)에 가능합니다. 코드를 보시면 iterator가 원소를 가리키고 있고 해당 원소에서 prev나 next나 advance와 같은 멤버 함수를 이용해서 좌우로 움직일 수 있습니다. begin()은 처음 원소의 iterator를 반환하고 end()는 마지막 원소의 한칸 뒤의 iterator를 반환합니다. end가 한 칸 뒤의 iterator를 반환하는 것도 그렇고 저 iterator 자체도 vector, list 등에서 이미 나왔던거라 그렇게 낯설 것 같지는 않습니다. 그리고 사실 C++11 이상부터는 15번째 줄처럼 굳이 저 뭔가 쓰기 싫게 생긴 자료형을 다 쓰는 대신에 그냥 17, 20, 21번째 줄처럼 auto를 쓰면 됩니다. 한 번 코드를 눈으로 잘 봐두고 lower_bound, find 같은 멤버 함수도 잘 기억했다가 써먹기 좋은 문제가 나오면 잘 써먹어보도록 합시다.

 

lower_bound는 이분탐색 단원에서 나왔던 그 lower_bound랑 기능이 동일한데, 특정 원소가 삽입되어도 오름차순 순서가 그대로 유지되는 가장 왼쪽 위치를 나타냅니다. lower_bound가 있다는 것에서 짐작할 수 있겠지만 순서가 그대로 유지되는 가장 오른쪽 위치를 나타내는 upper_bound랑, lower_bound와 upper_bound 쌍을 반환하는 equal_range도 그대로 있습니다. 이 멤버 함수들의 시간복잡도를 보면, set에서는 진짜 그냥 온갖 연산이 다 O(lg N)이라고 생각하면 됩니다. size, end, begin 함수는 그냥 멤버 변수로 가지고 있던 값을 바로 반환할테니 O(1)이지만 insert, erase, find, lower_bound, next, prev 등은 모두 O(lg N)입니다. 단 advance의 경우에는 한 칸을 움직이는게 O(lg N)이기 때문에 advance(it, 100); 이라고 하면 이게 그냥 O(lg N)이 아니고 한 칸 움직이는 O(lg N) 연산을 100번 수행하는 상황이란건 기억을 하고 계셔야 합니다.

 

한편 next, prev의 경우에는 정확히는 최악의 경우 O(lg N)이지만 amortized O(1)입니다. 운이 정말 안좋다면 1번 next나 prev 연산을 하는건 O(lg N)일 수 있지만, 예를 들어 K번 next나 prev를 한다고 하면 amortized O(1)이기 때문에 O(K)의 시간이 필요하게 됩니다. 

다음으로는 multiset입니다. unordered_multiset과 마찬가지로 원소의 중복이 허용되는 STL이고 그 점만 유의해서 보면 set이랑 큰 차이 없이 이해가가능합니다. 10번째 줄과 같이 erase를 하면 15를 1개 지우는게 아니라 모든 15를 지운다는 점을 유의하시고, 또 16번째 줄을 보시면 find 멤버 함수가 있는데 set에서의 find 멤버 함수와는 상황이 좀 다릅니다. set에서는 어차피 1개니까 있으면 그 원소의 iterator를 반환하면 되고 없으면 s.end()를 반환하면 됐는데, multiset에서는 같은 원소가 여러 개 있을 수 있습니다. 그러면 그 중에서 뭘 반환해줄지가 좀 애매한데 표준을 보면 그 중에서 아무거나 준다고 되어 있습니다. 다만 저희가 주로 쓰는 gcc에서는 제가 확인을 해보니 적어도 제가 실험을 해본 버전들에서는 항상 제일 먼저 등장하는 원소의 iterator를 주긴 했다만 이건 구현에 달린 문제이고 기본적으로는 여러 개가 있을 때에는 그 중에서 아무거나 준다는 점을 기억하도록 합시다.

 

만약 제일 먼저 등장하는 원소의 iterator가 필요한 상황이라면 find를 쓰는 대신 lower_bound를 써야 합니다. 그리고 it2를 보면 100의 upper_bound는 100이 들어갔을 때 오름차순이 유지되는 가장 오른쪽 위치니까 시작점(-10)으로부터 3칸 떨어진 곳, 즉 multiset의 마지막 원소가 있는 곳에서 한 칸 오른쪽으로 간 곳입니다. 여기는 ms.end()입니다. 그리고 여기는 가리키는 원소가 없기 때문에 만약 *it2를 출력하게끔 했다면 런타임 에러가 발생합니다. iterator가 end()를 가리키고 있는데 거기의 값을 참조하도록 하는건 set/multiset/map에서 런타임 에러를 유발하는 주요 원인중 하나라 이런 실수를 하지 않도록 조심하고 또 런타임 에러가 발생했다면 이 이유를 생각해볼 수 있습니다. 또한 unordered_multiset과 마찬가지로 count 함수는 O(lg N)이 아닌 O(원소의 개수)만큼의 시간이 걸림에 유의하세요.

 

마지막은 map입니다. 이 친구도 key로 value를 찾는 인터페이스가 잘 되어있는 STL이고 이미 prev, next, lower_bound, upper_bound 이런건 앞에서 설명을 잘 했어서 14번째 줄만 한 번 보고 가겠습니다. it1이 가리키는 대상은 pair<string, int>이기 때문에 it1->first, it1->second로 key와 value를 가져올 수 있습니다.

 

그리고 알아두시면 피가 되고 살이 될 정보가 있는데, 첫 번째로 만약 문제를 풀다가 뭔가 set, map 느낌의 성질이 필요하면서 특히 lower_bound나 prev, next 이런걸 사용해야만 풀리는 문제라면 꼭 STL set, map으로 해결을 해야 합니다. 반면에 그냥 key로 value를 빠르게 찾거나, 원소의 삽입/검색/삭제만 빠르게 처리를 해주어야 할 경우라면 STL unordered_set, unordered_map을 사용해도 상관이 없습니다. 그리고 실제로 속도를 비교해보면 평균적으로는 set/map보다 unordered_set/unordered_map이 빠릅니다. 그럼에도 불구하고 저는 set/map을 쓰는걸 선호를 하는데, 왜 그렇냐면 unordered_set/unordered_map은 평균적으로는 빠를지언정 충돌이 얼마나 빈번한가에 따라서 속도의 저하가 발생할 수 있어서 항상 빠르게 동작한다는 보장을 할 수 없다는 치명적인 단점이 있습니다. 물론 그런 일이 흔치는 않겠지만 출제자가 의도적으로 충돌을 유발하는 데이터를 넣어둔다거나 하면 각 연산이 O(1)이 아닌 O(N)에 동작하게 되어서 꼼짝없이 시간초과가 발생합니다. 반면 set/map은 평균적으로는 느릴지언정 항상 O(lg N)이기 때문에 데이터가 어떻게 들어있던간에 실행 시간이 어느 정도인지 가늠을 할 수 있습니다. 그래서 여러분들도 unordered_set/unordered_map보다는 set/map을 쓰는게 더 좋지 않을까 하는 생각을 아주 살짝 해봅니다. 이건 제가 100% 옳은건 아니고 여러분이 판단하셔서 정하면 됩니다.

 

두 번째로 이진 검색 트리의 연산은 확인한 것 처럼 O(lg N)이 되는건 맞지만 같은 O(lg N)중에서도 상당히 느립니다. 저희가 지금까지 배운 알고리즘들 중에서 시간복잡도에 로그가 붙는걸 생각해보면 이분탐색이나 정렬 알고리즘을 떠올릴 수 있습니다. 이분탐색에서는 lg N번의 연산 동안 인덱스의 값만 왔다갔다하면 되지만 이진 검색 트리에서는 새로운 노드를 동적할당으로 생성하거나, 편향성을 해소해주기 위해 노드를 뗐다 붙였다 하거나 하는 식으로 다소 무거운 연산을 해야 할 일이 많습니다. 그렇기 때문에 이분탐색이나 정렬에서는 N = 100만이라고 할 때 N개의 데이터에서 이분 탐색을 N번 하거나 정렬을 해서 O(NlgN)짜리 연산을 수행한다고 하면 크게 부담스럽지 않게 통과가 되겠다 하고 짐작을 할 수 있는 반면 이진 검색 트리에서는 N = 100만일 때 N개의 데이터에서 연산을 N번 수행해야 한다고 하면 조금 부담이 됩니다. 상황에 따라 차이는 좀 있지만 보통 저런 상황에서 1초 제한이라고 하면 간당간당할 수가 있습니다. 그래서 이진 검색 트리는 O(lg N)이지만 좀 느리다는걸 기억해두면 좋습니다. 또 이진 검색 트리를 쓰는 문제인 것 같긴 한데, N = 100만과 같이 N이 좀 큰 상황에서 내가 생각한 풀이는 O(NlgN) 같고 시간 제한이 좀 넉넉하지 않은 상황을 마주한다면 STL set/map으로 풀었을 때 시간초과가 날 가능성도 있습니다. 이럴땐 일단 구현을 해보고 TLE가 난다면 기도하는 심정으로 STL unordered_set/unordered_map으로 교체해서 내보고, 그래도 또 TLE가 난다면 뭔가 set/map을 사용하지 않고 이분 탐색이나 정렬이나 아니면 그냥 배열의 인덱스를 가지고 푸는 다른 풀이를 고민을 해볼 필요가 있습니다.

 

그러면 이진 검색 트리를 이용해서 풀 수 있는 문제를 소개해보겠습니다. 우선 전 단원에 있던 문제들은 당연히 set/map으로도 해결이 가능합니다. 그 외에 대소관계가 잘 설정된다는 특성을 이용할 수 있는 문제로 먼저 BOJ 7662번: 이중 우선순위 큐 문제를 보겠습니다. 우선순위 큐는 다음 단원에서 배울거라 조금 상황이 웃기긴 한데 문제가 괜찮아서 들고왔습니다. 우선순위 큐를 모르더라도 문제를 푸는데에 지장은 없으니 걱정마시고, 문제를 잘 보시면 삽입, 최댓값 삭제, 최솟값 삭제를 구현해야 합니다. 그냥 배열로 막 구현하면 O(k²)이 된다는건 쉽게 감이 올거고 해시를 잘 써먹을 방법이 있나 생각해봐도 해시의 특성상 해시 테이블 안에 있는 원소 중에서 최댓값 혹은 최솟값을 효율적으로 찾을 방법이 없습니다. 그런데 이진 검색 트리는 딱 이 문제의 상황에 적합합니다.

 

트리에서 가장 작은 원소는 루트에서 시작해서 왼쪽 자식을 타고 계속 갔을 때 만나는 원소이고

 

가장 큰 원소는 루트에서 시작해서 오른쪽 자식을 타고 계속 갔을 때 만나는 원소입니다. 결론적으로 자가 균형 트리라고 할 때 최댓값 삭제, 최솟값 삭제는 모두 O(lg N)입니다. 삽입도 당연히 O(lg N)입니다. 그래서 이진 검색 트리를 쓸 수 있다는 것만 감을 잡으면 이 문제는 그냥 STL 연습용 문제라고 생각하시면 되고, STL 사용법에 익숙해질겸 직접 레퍼런스를 보던가 앞에서 간략하게 설명한 사용법을 토대로 구현해보겠습니다. 또 set, multiset, map 중에서 무엇을 쓰는게 가장 적절할지도 고민을 해보면 됩니다.

 

이 문제는 key, value 대응 관계가 필요한건 아니니 map보다는 set이나 multiset이 나을거고 또 동일한 정수가 삽입될 수 있다는 조건으로 볼 때 중복된 원소가 있을 수 있으니 multiset을 써야합니다. 기초적인 느낌의 문제라 그냥 잘 짜시면 되긴하는데 놓치거나 실수하기 쉬운 점들을 몇 개 짚어보겠습니다.

 

첫 번째로 ms가 empty인데 erase를 하면 런타임 에러가 납니다. 그렇기 때문에 19번째 줄과 같은 처리가 필요합니다. 또 최댓값을 지울 때에는 ms.erase(ms.end())가 아니라 ms.erase(prev(ms.end()))입니다. ms.end()는 마지막 원소의 한 칸 뒤를 가리킨다는 점을 꼭 명심하셔야 합니다. 마지막으로 multiset을 처음 설명 드릴때에도 말씀드렸지만 만약 ms.erase(*ms.begin())과 같이 작성했다면 최솟값이 여러 개일 때 1개만 지우는게 아니라 싹 다 지우는 대참사가 발생할 수 있습니다. 처음에는 조금 손에 안익을수도 있는데 자주 쓰다보면 금방 익숙해질 수 있습니다(코드).

 

다음 문제는 BOJ 1202번: 보석 도둑 문제입니다. 이 문제는 조금 어렵긴 합니다. 사실 많이 어렵다고 해도 될 것 같습니다. 뭔가 그냥 얼핏 봤을 땐 knapsack DP 같은 느낌이 나고 이게 set이랑 어떤 관련이 있는지 좀 짐작이 어려울 것 같습니다. 그러면 일단 set에 얽매이지 말고 문제를 어떤 식으로 풀어야할지, 상덕이가 어떤 방식으로 보석을 선택해야 최댓값을 얻을 수 있을지 고민해보겠습니다.

 

사실은 여기서 갑분 그리디가 튀어나옵니다. 어떤 그리디 풀이가 가능할지 고민을 좀 해보겠습니다. 그리디 단원에서 강조를 했었지만 잘못된 그리디 풀이를 잡았다가는 말짱 꽝이기 때문에 그리디 풀이를 떠올린 후에 수학적으로 증명을 할 수 있다면 제일 좋고, 혹시 좀 깔끔하게 증명을 못하겠더라도 진짜 다양한 입력 상황들을 생각해보면서 내 풀이가 정말 정당한가 꼭 따져봐야 합니다. 지금까지 배워오면서 느끼셨겠지만 이런 수학적인 직관을 필요로 하는 경우가 종종 있습니다. 수학적인 직관력을 잘 갖추고 있다면 당연히 좋은 일이고 아마 알고리즘을 배우는 속도도 다른 사람들에 비해 빠르긴 합니다. 하지만 설령 직관력이 뛰어나지는 않아서 생판 처음 보는 문제를 잘 풀어내지는 못한다고 해도 저희가 마치 수능을 공부하는 것 마냥 여러 유형들을 익히고 반복 학습을 통해 숙달하면 잘 할 수 있으니 너무 걱정은 하지 않으셔도 됩니다.

 

그러면 다시 본론으로 돌아와서 이 문제를 푸는 그리디 풀이는 무엇이냐고 했을 때 가장 가격이 높은 보석부터 확인하며 해당 보석을 담을 수 있는 가방 중 최대 무게가 가장 작은 가방을 이용해 보석을 담는 방법입니다. 두 번째 예시를 가지고 설명을 해보면 먼저 무게가 2이고 가격이 99인 보석은 최대 무게가 2인 가방, 10인 가방 둘 다 수용이 가능한데 둘 중에 최대 무게가 2인 가방을 사용합니다. 이렇게 되면 최대 무게가 10인 가방밖에 안남았으니 그 다음으로 무게가 1이고 가격이 65인 보석을 최대 무게가 10인 가방에 담으면 됩니다. 대충 방법은 알겠는데 이 방법이 왜 맞는지를 생각해봐야 합니다. 귀류법으로 증명해보겠습니다.

 

첫 번째로 생각할 수 있는 경우는 가장 가격이 높은 보석을 담긴 담을건데, 최대 무게가 가장 작은 가방을 이용하지 말고 그것보다 더 큰 가방을 이용하는 경우입니다. 서술의 편의를 위해 가방의 이름을 A와 B라고 붙이고 보석의 이름을 x라고 붙였습니다. 이런 경우가 더 이득이 될 수 있는지 생각해보면 이건 좀 당연하게 그럴 수 없습니다. 직관적으로 생각해도 굳이 더 큰 가방을 쓰는게 이득일 수가 없습니다.

 

조금 그럴싸한 용어로 정리해보면, A 말고 가방 B를 이용해서 더 이득을 봤다고 해보겠습니다. 그 경우에 대해서 만약 가방 A에 다른 보석 y가 있었다면 y의 무게는 A의 최대 무게보다 작고 B의 최대 무게는 A보다 크다고 했으니까 가방 A와 가방 B의 내용물을 바꿔도 아무 문제가 없습니다. 그리고 가방 A에 다른 보석이 없다면 그냥 보석 x를 가방 B에서 A로 옮겨도 아무 문제가 없습니다. 이말인즉슨 우리는 적어도 가방 B에 보석 x를 넣어둔 상황과 동일한 효과를 가방 A에 보석 x를 넣어서 얻을 수 있고, 즉 가방 B에 x를 담는게 가방 A에 x를 담는 것 보다 이득일 수 없다는 얘기입니다. 이게 첫 번째로 따져야할 상황입니다.

 

여기서 끝은 아니고 두 번째로 따져봐야할건 보석 x를 담을 수 있는 가방이 있음에도 불구하고 넣지 않는게 더 이득일 수 있는지 여부입니다. 물론 비록 실제 그리디 문제를 대회나 코딩테스트에서 풀 때에는 이렇게 세세하게 적어가면서 하지는 않겠지만 내 풀이가 정당한지 확인을 하고 진행해야 하니 적어도 이 내용을 머릿속에서 대략적으로라도 생각해보고 코딩에 들어가야 합니다. 그러니까 앞에서의 논리 전개 내용을 참고해서 지금 이 귀류법도 한번 모순을 찾아보겠습니다.

 

이건 어떻게 생각을 하면 되냐면, 또 마찬가지로 A에 안 넣는게 이득인 경우가 있다고 해보겠습니다. 그런 경우 가방 A에 다른 보석 y가 있다면 x가 가장 가격이 크다고 했으니 y 대신 x를 넣는게 더 이득입니다. 만약 가방 A에 다른 보석이 없다면 보석 x를 버리는 것 보다 A에 넣는게 더 이득입니다. 결론적으로 보석 x를 담지 않는게 가방 A에 x를 담는 것 보다 이득일 수 없습니다. 이렇게 정당성을 차근차근 따져본 결과 그리디 풀이가 맞다는걸 알 수 있었고 구현을 하면 되는데 구현을 딱 하려고 본 순간 뭔가 단순히 배열만 가지고는 해결이 안되는구나 하는걸 알 수 있습니다. 그냥 막 구현하면 O(NK)이고, 어떻게 시간복잡도를 좀 줄여보겠다고 보석을 가격 순으로 정렬하고 가방도 최대 무게 순으로 정렬하면 매 순간마다 해당 보석을 담을 수 있는 가방 중 최대 무게가 가장 작은 가방 자체는 이분 탐색으로 O(lg K)에 찾을 수 있지만, 문제는 이렇게 채워진 가방을 제거해야 합니다. 그런데 그냥 배열이면 제거가 O(K)여서 의미가 없습니다. 그래서 배열로는 어떻게 잘 안되고 대신 이진 검색 트리를 이용하면 해당 보석을 담을 수 있는 가방 중 최대 무게가 가장 작은 가방도 O(lg K)에 찾고, 가방의 제거도 O(lg K)에 할 수 있습니다. 바로 다음 슬라이드에 코드가 나오니까 구현을 해보고 넘어오도록 합시다.

 

코드를 보시면 알겠지만 가방들을 이진 검색 트리로 관리합니다. 그렇게 되면 매 순간마다 해당 보석을 담을 수 있는 가방 중 최대 무게가 가장 작은 가방을 찾는걸 lower_bound 함수로 편하게 처리할 수 있습니다. 이 때 무게가 중복될 수 있으니 set 대신 multiset을 이용해야 하고, 답을 담을 ans는 int 범위를 초과할 수 있으니 long long으로 둬야 합니다. 그리고 32번째 줄과 같이 만약 lower_bound를 한 결과가 bag.end()일 경우에는 최대 무게가 m 이상인 가방이 없다는 의미이기 때문에 continue를 꼭 해줘야 합니다. 이외에 다른 구현의 디테일은 직접 코드를 보면 충분히 이해가 될 것 같아서 더 자세한 설명은 생략하겠습니다(코드).

 

이렇게 이진 검색 트리 강의도 끝이 났습니다. 아주 간단하게 요약을 하자면 이진 검색 트리에서는 원소가 크기 순으로 저장되어 있고 삽입, 삭제, 검색 등이 전부 O(lg N)에 동작합니다. 그렇기 때문에 일단 N이 커서 O(N^2)은 통과가 안될 상황이고 원소의 대소 관계가 필요한데 삽입 혹은 삭제가 빈번하다면 이진 검색 트리가 유용하게 쓰일 수 있습니다. 꼭 대소 관계가 아니더라도 그냥 key로 value를 빠르게 찾거나, 원소의 삽입/검색/삭제만 빠르게 처리를 해주어야 할 경우라고 해도 unordered_set/unordered_map을 쓰듯이 set/map을 편하게 쓸 수 있습니다. 그럼 강의를 여기서 마치겠습니다.