[실전 알고리즘] 0x0D강 - 해쉬, 이진 검색 트리, 힙_구버전

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

현재 보고있는 강의는 구버전입니다. 내용에는 문제가 없으나 리뉴얼 중이니 이 게시글을 참고해주세요.

 

리뉴얼한 버전은 [실전 알고리즘] 0x15강 - 해시, [실전 알고리즘] 0x16강 - 이진 검색 트리, [실전 알고리즘] 0x17강 - 우선순위 큐에서 확인할 수 있습니다. 리뉴얼 버전으로 보시는 것을 추천드립니다.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

안녕하세요, 오랜만입니다. 이번 시간에는 해쉬, 이진 검색 트리, 힙을 다뤄보도록 하겠습니다. 내용이 굉장히 많으니 주의하세요.

 

 

들어가기 전, 해쉬, 이진 검색 트리, 힙의 경우 사실 코딩테스트에서 그다지 쓰임새가 많지는 않은 자료구조입니다. 그러나 차마 실전 알고리즘 강의라고 이름을 붙여놓고 안하고 가기는 좀 그런 중요한 자료구조들이라 이렇게 한 강을 할애해 소개를 드립니다. 그러니 본인의 공부 목적에 따라 내용을 취사선택해서 가져가세요. 코딩테스트가 임박해서 보고 있다면 STL의 사용법만 급하게 익히고 가셔도 됩니다.

 

두 번째로, 대학 자료구조 혹은 알고리즘 수업에서 배운다면 3개를 다 배우는데 보통 아무리 짧아도 8-10시수 정도는 할애하기 때문에 이번 강의 하나만으로 세 자료구조를 완벽하게 익히는 것은 불가능합니다. 대략적인 느낌만 가져가시고 필요에 따라 별도로 학습을 하셔야 합니다.

 

첫 번째로 다룰 자료구조는 해쉬입니다. 이 해쉬는 해쉬브라운의 그 해쉬입니다. 도대체 무엇을 하는 자료구조인지 천천히 알아봅시다. 위에 적힌 문제를 고민해보세요. 일단 배열에 (사람, 카드 번호)를 다 넣는다고 치면 주어진 카드 번호에 대응되는 사람을 찾는데 필요한 시간복잡도가 얼마일까요?

 

배열의 원소를 하나씩 보는 방법 이외에는 별 다른 방법이 없어보입니다. 0번지를 보니 카드번호가 일치하지 않고

 

1번지도 일치하지 않고

 

이런식으로 쭉쭉 가다가 7번지에서는 찾는데 성공했네요. 시간복잡도가 $O(N)$임을 쉽게 알 수 있습니다.

 

만약 카드 번호가 4자리였다면 어땠을까요? 마치 Count Sort에서 한 것과 비슷한 느낌으로 O(1)에 처리가 가능할 것 같습니다.

 

문제는, 지금 주어진 상황에서는 카드 번호가 16자리여서 테이블을 만드는 것이 불가능합니다. $10^$개의 원소를 가진 테이블의 크기는 어마어마하게 크거든요. 각 원소가 4byte만 잡는다고 쳐도 40PB가 필요합니다.

 

이제 여기서 잔꾀를 쓰는 것입니다. 지금과 같은 상황에서는 그냥 16자리를 전부 인덱스로 쓰지 말고 앞의 4자리만 써도 되지 않을까요?

 

이제 여기서 저희는 해쉬함수를 알 수 있게 되었습니다. 해쉬함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수입니다. 예를 들어 카드 번호 16자리를 앞 4자리만 떼내어 사용하는 것은 카드 번호 16자리를 4자리의 숫자로 대응시키는 해쉬함수를 사용한 것이죠.

 

그리고 해쉬함수를 이용해 앞에서와 같이 테이블을 만들면 그것이 해쉬 테이블입니다. 

 

그런데 이 방식에는 아주 큰 문제가 있습니다. 앞의 예시에서는 운 좋게 앞 4자리가 같은 카드번호가 없었지만, 입력이 많아지면 충분히 앞 4자리가 같은 카드번호가 등장할 수 있습니다. 이와 같이 해쉬함수에서 두 입력값에 대해 출력값이 동일한 것을 충돌이라고 부릅니다. 저희는 카드번호 "1351 9672 3313 4752"와 "1351 9167 1336 4732"를 전부 해쉬테이블의 1351번지에 넣고 싶지만 그럴 수는 없습니다. 뭔가 해결 방안이 필요합니다.

 

적절한 해쉬 함수를 잘 골라서 충돌이 안나게끔 하면 안되냐는 의문을 가질 수도 있는데, 애초에 해쉬 함수는 정의역의 공간을 줄이려고 씁니다. 마치 카드 번호의 종류가 $10^$개이므로 이를 앞 4자리만 이용해 $10^4$개로 줄인 것 처럼요. 그렇기에 충돌이 발생하는 것 자체는 달리 막을 방법이 없습니다.

 

다행히 똑똑한 학자분들이 이 충돌을 회피할 방법에 대해 많은 연구를 해두었습니다. 충돌을 회피하는 것을 Collision Resolution이라고 하는데 Collision Resolution을 하는 대표적인 방법 2개는 Open Addressing과 Chaining입니다. 먼저 Open Addressing을 알아봅시다.

 

Open Addressing은 충돌이 발생했을 때 원소를 저장하는 인덱스를 바꾸는 충돌 회피 방법입니다. 일단 Kim을 1237번지에 적읍시다.

 

그 다음에 Lee를 적어야하는데, 1237번지는 이미 차있습니다. 어떻게 해야할까요?

 

한 칸 오른쪽에 적으면 되겠네요. 1238번지에 Lee를 적습니다.

 

Choi의 카드 앞 4자리도 1237이네요. 마찬가지로 1237번지는 이미 점유되어있고

 

한 칸 오른쪽으로 가도 마찬가지입니다.

 

당황하지말고 한 칸 더 오른쪽으로 갑니다. 다행히 1239번지는 비어있네요. 1239번지에 Choi를 씁니다. 이후 과정은 생략하겠습니다.

 

그런데 맨 처음에는 해쉬 테이블에 이름만 썼는데 지금은 카드 번호도 같이 썼습니다. 왜 그런걸까요? 만약 카드 번호를 같이 적어놓지 않는다면 어떤 일이 발생하는지 고민해봅시다.

 

카드번호가 "1237 9672 3313 4752"인 사람이 누구냐는 질문에는 Kim을 답하고, "1237 0000 0000 0000"이 누구냐는 질문에는 그런 사람이 없다고 답을 해야하는데 카드 번호를 같이 적어두지 않는다면 둘을 구분할 수 없기 때문입니다.

 

지금과 같이 충돌을 회피하기 위해 한 칸씩 뛰는 방식을 Linear probing이라고 합니다. 이외에도 1, 3, 5, ... 칸씩 뛰어서 처음의 칸으로부터 1의 제곱, 2의 제곱, 3의 제곱 떨어진 칸을 보는 Quadratic probing, 그리고 또 다른 해쉬 함수를 두어 그 결과만큼 뛰는 Double hashing 등의 방식이 있습니다.

 

두 번째 방식은 Chaining입니다. Chaining은 해쉬 테이블에서 각 인덱스에 원소 1개만을 담는 것이 아니라 Linked List 구조로 여러 원소를 담고 있는 방식을 의미합니다. 꼭 Linked List일 필요는 없고 동적배열이어도 상관은 없습니다.

 

우선 Kim을 1237번지에 넣습니다.

 

그 다음 Lee를 넣는데, Lee의 카드 번호의 앞 4자리도 1237이니 1237번지에 들어가야 합니다. 맨 뒤에 붙여도 잘 동작하지만 맨 뒤에 두면 1237번지에 있는 노드의 갯수만큼 이동한 뒤에 새로운 노드를 부착해야 하므로 시간복잡도에서 손해를 봅니다. 대신 제일 앞에 두면 O(1)에 삽입이 가능합니다.

 

Choi 또한 1237번지에 넣습니다.

 

Son은 4611번지입니다.

 

Park은 9748번지이구요.

 

마지막으로 Ma를 1237번지에 넣어주면 테이블의 구성이 끝납니다.

 

이와 같이 해쉬 자료구조를 알아보았습니다. 해쉬에서 원소의 삭제에 대해 다룰까말까 고민하다가 뺐는데, 다음에 시간이 남으면 한 번 찾아보시기를 추천드립니다. 예를 들어 Linear Probing으로 1, 2, 3, 4, 5번지를 해쉬 값이 1인 5개의 원소가 차지하고 있는데 적절한 처리를 하지 않고 그냥 3번째 원소를 지우게 되면 4, 5번째 원소는 지우지 않았음에도 불구하고 앞으로는 찾아지지 않는 큰 문제를 야기할 수 있습니다.

 

해쉬구조의 모습을 살펴보시면 알겠지만 기본적으로 삽입, 삭제, 검색은 모두 $O(1)$입니다. 그러나 충돌이 빈번히 발생할수록 실제 시간복잡도는 나빠집니다. 그러므로 데이터의 성격에 따라 테이블의 크기를 크게 한다거나, 적절한 해쉬 함수를 사용한다거나 하는 방식으로 충돌이 최대한 일어나지 않도록 하는 것이 중요합니다.

 

사실 코딩테스트에서 해쉬 테이블을 직접 구현해야 할 일은 거의 없긴 합니다. STL을 허용하지 않으면서 문제도 굉장히 까다로운 삼성역량테스트 B, C형에서는 삽입, 삭제, 검색을 $O(N)$보다 빠르게 수행해주는 자료구조가 필요할 수 있고, 이런 자료구조 중에서 해쉬가 그나마 구현이 간단한 편이기에 필요할 수 있는데 다른 곳에서는 해쉬 테이블을 쓰는 것 보다 STL에 이미 구현되어 있는 이진 검색 트리를 사용하는 것이 더 낫기 때문입니다. 참고로 STL에 해쉬도 unordered_set, unordered_map이라는 이름으로 해쉬 테이블을 이용한 자료구조가 있습니다만 이진 검색 트리 기반의 set, map과 기능이 동일하기에 저는 별로 사용하지 않습니다.

 

앞에서 주구장창 언급한 이진 검색 트리가 무엇일까요? 이진 검색 트리는 특별한 성질을 만족하는 트리입니다. 일단 트리가 뭔지를 알아야할 필요가 있는데, 아직 그래프와 트리 자료구조에 대해 공부를 하지 않았기 때문에 엄밀한 정의를 만들어내는 것은 불가능합니다. 지금 이 그림처럼 뭔가 계층 구조를 가지고 있고, 제일 꼭대기를 제외하고 각 동그라미들은 위로 딱 1개와 연결이 되어있는 정도로만 받아들이고 넘어갑시다.

 

정의는 비록 불완전하지만 그래도 적당히 이해했다고 치고, 트리에서 쓰이는 용어들을 몇 가지 정리하고 가겠습니다. 첫 번째로 트리에서의 원소는 노드라고 부릅니다.

 

그리고 제일 꼭대기의 원소는 루트입니다.

 

제일 끝의 노드, 아래로 뻗은게 없는 노드들은 리프입니다.

 

그리고 위아래로 인접한 노드는 부모, 자식 관계이고 부모가 같은 두 노드는 형제입니다.

 

마지막으로 트리의 높이는 위아래로 뻗어있는 높이이고, 루트를 1로 잡느냐 0으로 잡느냐에 따라 이 그림에서 트리의 높이가 3일수도 있고 4일수도 있는데 크게 중요한 부분은 아닙니다.

 

이진 트리는 각 노드의 자식이 2개 이하인 트리입니다.

 

자식이 2개 이하이기 때문에 왼쪽 자식과 오른쪽 자식으로 구분할 수 있습니다.

 

드디어 이진 검색 트리가 무엇인지를 이해하기 위한 모든 과정이 끝이 났습니다! 이진 검색 트리는 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 이진 트리입니다.

 

데이터를 삽입할 때 위에서 언급한 "왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 이진 트리"라는 조건이 위배되지 않도록 해야 합니다. 구체적으로 어떤 과정을 거쳐서 데이터를 삽입하는지 알아봅시다.

 

45를 삽입하고 싶습니다. 일단 맨 처음에는 아무것도 없으니 45를 바로 루트로 만듭니다.

 

그 다음에는 25를 삽입합니다. 25는 45를 기준으로 왼쪽에 있을까요? 오른쪽에 있을까요?

 

이진 검색 트리는 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 크므로 25는 왼쪽에 위치해야 합니다. 45의 왼쪽에 25를 부착합니다. 

 

35를 삽입하고 싶습니다. 35는 우선 45의 왼쪽에 있어야합니다.

 

그렇다고 해서 45의 왼쪽 자식으로 35를 둘 수는 없습니다. 왜냐하면 25가 이미 있기 때문입니다. 이제 35는 어디로 가야할까요?

 

25의 오른쪽으로 가면 되겠네요.

 

이런식으로 현재 보고있는 값과의 대소비교를 통해 빈 공간을 찾을 때 까지 왼쪽 혹은 오른쪽으로 계속 이동하면 됩니다. 55를 삽입해보았습니다.

 

50을 삽입하면 55의 왼쪽에 위치하게 됩니다.

 

마지막으로 15는 25의 왼쪽에 위치합니다.

 

삽입하는 과정을 생각해보면 특정 노드를 삽입하는데 필요한 시간은 해당 노드가 자기 자리를 찾아가기 위해서 비교를 몇 번 해야하는지, 즉 해당 노드의 높이가 얼마인지에 비례합니다. 만약 왼쪽 그림과 같이 높이가 전반적으로 균등하다면 노드의 갯수가 $N$이라고 할 때 높이가 대략 $lg N$이기 때문에 삽입에 필요한 시간복잡도는 $O(lg N)$이지만 오른쪽 그림과 같이 트리가 편향되어 있으면 높이가 $O(N)$에 가깝기 때문에 삽입에 필요한 시간복잡도는 $O(N)$이 됩니다.

 

검색은 삽입과 비슷하게 루트에서 출발해 대소비교를 하며 좌우로 이동하면 됩니다.

 

 

과정을 생각해보면 삽입과 마찬가지로 시간복잡도는 높이에 비례함을 알 수 있습니다.

 

이진 검색 트리에서 가장 힘든 부분은 노드의 삭제입니다. 예를 들어 25를 지우고 싶다고 할 때, 무턱대로 25를 날려버리면 트리의 구조 자체가 깨지게 됩니다. 어떤 식으로 노드를 제거할 수 있을까요?

 

지우고 싶은 노드의 자식의 수에 따라 지우는 방법이 다릅니다. 첫 번째로 자식이 없는 노드를 지우는 경우를 생각해봅시다. 자식이 없는 노드일 경우 그냥 지우면 됩니다.

 

자식이 1개인 노드도 그럭저럭 쉽습니다. 자식을 지워진 노드의 자리에 올리면 됩니다. 그림에서 15를 지울 때, 10을 올림으로서 10의 자식인 13 또한 자연스럽게 위치가 이동됨을 명심하세요.

 

핵심은 자식이 2개인 노드를 어떻게 지울까입니다. 어떻게 하면 될까요?

 

25의 자손인 10, 13, 15, 32, 34, 35, 40을 다 지웠다가 다시 삽입을 하면 해결이 되긴 할텐데, 저희는 최대한 연산을 덜 하는 방향으로 삭제를 구현하고 싶습니다. 가장 좋은 방법은 어떤 적절한 노드를 25가 있는 위치로 옮기는 것입니다. 10, 13, 15, 32, 34, 35, 40중에 어떤 노드를 25의 자리로 옮겨도 될까요?

 

32를 지우고 25의 자리로 보내면 여전히 이진 검색 트리의 성질을 만족합니다. 왜 하필 32가 이러한 성질을 만족하는걸까요?

 

32는 25보다 크면서 가장 작은 원소이기 때문입니다. 그렇기에 32는 25의 왼쪽에 있는 10, 13, 15보다 크다는 것이 보장되고, 32의 오른쪽에 있는 34, 35, 40보다 작음도 보장이 되고, 이는 곧 32가 25의 자리에 있어도 문제가 없음을 의미합니다. 비슷한 관점에서 25보다 작으면서 가장 큰 15를 25의 자리로 옮겨도 문제가 없습니다.

 

그런데 지금 이 예시에서는 15나 32가 자식이 1개인 원소이므로 쉽게 제거가 가능한데 32에 자식이 2개였으면 어떻게 될까요?

 

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

 

이진 검색 트리에서 삽입, 검색, 삭제에 대해 알아보았습니다. 세 과정은 모두 대상이 되는 노드의 높이가 얼마인지에 따라 시간복잡도가 정해집니다. 만약 트리가 균형 트리에 가까운 모습일 경우 이 세 연산은 빠르게 동작하지만 편향된 트리에 가까울 경우 굉장히 비효율적이게 되어 그냥 Linked List나 배열을 쓰는 것과 시간복잡도는 비슷한데 공간은 더 많이 쓰는 어이없는 상황이 벌어질 수도 있습니다. 그리고 편향된 트리가 만들어지는 상황은 의외로 잘 발생합니다. 예를 들어 1, 2, 3, 4, 5, 6, 7, 8을 트리로 만들 경우 자연스럽게 1, 2, 3, 4, 5, 6, 7, 8이 1을 루트로 하고 오른쪽 방향에 일직선으로 뻗는 편향된 트리가 나올 것입니다.

 

그렇기에 트리가 편향되어 있으면 사실상 트리를 쓰는 이유가 없어집니다. 저희는 연산들을 $O(lg N)$에 수행하기 위해 트리를 사용하니까요.

 

그렇기 때문에 이진 검색 트리가 편향되지 않게 바로잡도록 삽입, 삭제를 개선한 트리가 존재합니다. 이는 자가 균형 트리라는 이름으로 불리고 AVL 트리, Red Black 트리 이 두 예시가 유명하지만 이번 강의에서 두 트리에 대한 설명은 생략하겠습니다. 지금 그림과 같이 불균형이 발생할 때 회전을 시키는 방식으로 구현이 이루어지나, 실제로는 다소 복잡합니다.

 

지금까지 배운 것을 토대로 구현을 할 수도 있긴 하지만, 실제로 구현을 해보면 구현 난이도가 저세상입니다. 심지어 자가 균형 트리를 사용하지 않는 이상 시간복잡도도 보장되지 않습니다. 그렇기에 코딩테스트에서 이진 탐색 트리를 직접 구현해야 하는 상황은 절대 없습니다. STL을 쓸 수 있으면 그냥 STL set/map을 사용하면 되기 때문입니다. 만약 STL을 사용할 수 없는 코딩테스트라고 할지라도 이진 탐색 트리를 구현하는 것 보다는 차라리 해쉬테이블을 구현하는게 그나마 낫습니다.

 

STL set은 값들을 이진 검색 트리로 저장하는 자료구조이고, map은 (key, value)를 key에 대한 이진 검색 트리로 저장하는 자료구조입니다. 이 때 이 이진 검색 트리의 구현은 자가 구현 트리로 되어있기 때문에 트리가 편향되지 않음이 보장됩니다. 단, set에서는 값이 중복되어 들어올 수 없는 반면 multiset에서는 값을 중복해서 넣을 수 있습니다. 비슷하게 multimap은 중복 key가 허용되는데, 사실 multimap은 써본 적이 없네요.

 

그냥 직접 예시를 보고 이해하시면 될 것 같습니다. set에서는 값이 중복되어 들어갈 수 없음에 굉장히 주의해야합니다.

 

map은 코드를 보면 알겠지만 마치 인덱스가 정수로 제한되지 않은 배열을 쓰듯이 사용하면 됩니다. multimap은 당장 저도 써본적이 없어서 별로 익숙하지가 않네요.

 

마지막으로 힙입니다. 힙은 이진 검색 트리와 비슷하게 트리이지만, 자식과 부모 사이에서의 대소 관계가 조금 다릅니다. 이진 탐색 트리와 헷갈리지 않도록 주의하세요.

 

이진 탐색 트리에서는 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 컸던 반면 최소 힙에서는 왼쪽 오른쪽과 관계없이 부모는 자식보다 작아야하고, 최대 힙에서는 부모는 자식보다 커야 합니다. 이 조건이 만족되면 최소 힙의 경우 루트가 최솟값이고, 최대 힙의 경우 로트가 최댓값입니다.

 

최소 힙에서는 원소의 삽입, 최솟값 확인, 최솟값 삭제의 기능을 제공하고 최대 힙에서는 원소의 삽입, 최댓값 확인, 최댓값 삭제의 기능을 제공합니다. 최소 혹은 최대가 아닌 값의 존재 여부 확인 혹은 원소 제거는 불가능합니다.

 

힙에서의 삽입은 일단 원소를 트리 상의 다음 공간에 추가하고, 이후 힙의 성질을 만족하게끔 서로 자리를 바꾸는 식으로 구현됩니다. 트리 상의 다음 공간이라는 표현이 헷갈릴 수 있는데 높이가 작은 곳 부터, 높이가 같다면 왼쪽부터 채워나간다고 생각하면 됩니다. 위의 그림에서 번호가 붙은 순서대로 트리가 채워집니다.

 

최소 힙을 한 번 만들어봅시다. 일단 최초의 원소인 35를 루트로 만듭니다.

 

55를 일단 다음 위치에 둡니다. 35는 55보다 작으므로 부모가 자식보다 작아야한다는 성질을 잘 만족합니다.

 

그 다음은 15입니다. 일단 15를 다음 위치에 넣긴 했는데, 35와 15에서 최소 힙의 조건이 위배됩니다. 어떻게 해야할까요?

 

둘의 자리를 바꾸면 되겠군요. 삽입이 종료되었습니다.

 

그 다음은 8입니다. 8을 일단 제자리에 넣긴 했는데 최소 힙의 성질을 만족하지 않습니다. 어떻게 해야할까요?  

 

당황하지말고 앞에서 한 것과 같이 8과 55의 자리를 바꿉니다. 그런데 바꾸고 나서도 8과 15에서 문제가 생기네요.

 

이 둘의 자리도 바꿔줌으로서 삽입이 종료됩니다.

 

32를 삽입해봅시다. 이번에는 문제가 안생기므로 그대로 종료됩니다. 과정을 보면 알겠지만, 아무리 비교를 많이 해도 최대 높이 만큼만 올라가면 삽입이 가능하고 힙의 구조 상 균형 트리이기 때문에 삽입의 시간복잡도가 $O(lg N)$임이 보장됩니다.

 

최솟값 확인은 더 간단합니다. 그냥 루트에 적힌 값이 최솟값입니다.

 

마지막으로 최솟값 삭제를 어떻게 해야할지 이해해봅시다. 이진 탐색 트리와 비슷하게 무턱대고 8을 지우면 트리 구조가 깨집니다.

 

그렇기 때문에 일단 8과 트리 구조 상에서 가장 마지막 위치인 52의 위치를 바꾸고 8을 제거합시다. 그러면 8은 자식이 없기 때문에 아무 문제 없이 제거할 수 있습니다.

 

그런데 지금 52가 루트로 옴으로 인해 부모가 자식보다 작다는 조건이 위배되었습니다. 뭔가 조치가 필요합니다. 52, 12, 20 사이에서 위치를 바꿈으로서 이를 해결해봅시다.

 

셋 중에 가장 작은 원소가 부모로 가면 됨은 자명합니다. 12와 52의 자리를 바꾸면 일단 52, 12, 20 사이에서의 문제는 해결됩니다.

 

하지만 여기서 끝은 아닙니다. 52, 16, 16에서 또 문제가 발생하네요.

 

16을 부모로 올리고 52를 자식으로 내립시다. 왼쪽을 택하든, 오른쪽을 택하든 아무 상관이 없습니다.

 

52는 마지막까지 말썽이군요. 이번엔 어떻게 하면 될지 상상이 가시죠?

 

22를 부모로 올리면 됩니다.

 

이렇게 최솟값의 삭제가 완료되었습니다.

 

지금부터 12를 삭제하는 과정을 보여드릴건데, 넘기기 전에 직접 한 번 손으로 해보시고 결과를 비교해보시는 것을 추천드립니다.

 

 

 

마찬가지로 아무리 운이 안좋아도 최대 높이 만큼만 내려가면 삭제가 가능하고 균형 트리이기 때문에 $O(lg N)$임이 보장됩니다.

 

트리 구조는 Node class를 만들어 구현하는 것이 정석적이지만 지금 상황처럼 위에서부터 꽉꽉 채워서 저장됨이 보장될 경우에는 트리의 각 원소를 배열에 대응시키면 구현이 간편합니다. BOJ 1927번 : 최소 힙 문제를 해결하는 코드를 확인해보세요.

 

웬만한건 다 있는 STL에 힙도 있습니다. 이름은 priority_queue이고, 이 힙은 기본적으로 최대힙입니다. 최소힙으로 써먹기 위해서는 힙을 선언할 때 명시를 해줘야할 게 있는데, 직접 STL을 이용해 BOJ 1927번 : 최소 힙 문제를 해결하는 코드를 확인해보세요.

 

강의를 끝내기 직전 질문을 하나 준비했습니다. 직장 혹은 대학원 면접이라고 치고, 면접관이 "힙에서 할 수 있는건 어차피 균형 이진 트리에서도 할 수 있지 않나요? 그러면 균형 이진 트리가 더 제공해주는 기능이 많은데 힙을 쓸 이유가 있나요?" 라고 물었을 때 뭐라고 답을 하면 깔끔한 답이 될까요?

 

답은 이렇습니다. 힙에서 할 수 있는걸 균형 이진 트리에서 할 수 있는 것이 맞고, 자가 균형 트리라는 가정하에 시간복잡도가 $O(lg N)$으로 동일한 것도 맞습니다. 그러나 힙은 균형 이진 트리보다 수행 속도도 빠르고, 구현도 쉽고, 공간도 적게 차지하기에 최소 혹은 최댓값의 확인/삭제만 필요할 떄에는 힙을 쓰는 것이 더 좋습니다.

 

이번 시간에는 학부 자료구조의 3대장 해쉬, 이진 검색 트리, 힙을 다 다뤘습니다. 내용이 굉장히 많았을텐데 따라오느라 고생 많으셨습니다. 해쉬는 삽입, 삭제, 검색 모두 이론적으로 $O(1)$이나 충돌이 발생함에 따라 시간복잡도가 더 나쁠 수 있고, 이진 검색 트리는 삽입, 삭제, 검색 모두 $O(lg N)$이나 트리가 편향됨에 따라 실제 시간복잡도는 $O(N)$이 될 수도 있고, 이를 해결하기 위해 자가 균형 트리가 존재합니다. 그리고 힙은 삽입, 최솟(혹은 최댓)값 삭제가 $O(lg N)$, 최솟(혹은 최댓)값 확인이 $O(1)$입니다.

 

코딩테스트에서 해쉬 테이블, 이진 검색 트리를 직접 구현해야 할 일은 99.999% 확률로 없을테지만 힙은 희박한 확률로 나올 수 있긴 합니다. 하지만 대부분의 코딩테스트에서 STL을 허용하니 꼭 힙의 구현을 빡세게 공부할 필요는 없지만 set, map, priority_queue의 사용법과 각 연산에 대한 시간복잡도는 익혀두는 것을 추천드립니다. 문제집에 있는 문제들을 STL을 사용해서 풀어보세요.