Jins' Dev Inside

LinkedHashMap 은 Linked List 의 특성을 지니는 HashMap 이다.

정확히는 HashMap 구현에 있어 Linked List 를 이용함으로써 키들 간의 순서를 보장해주고, Link 를 연결시켜 준다.

각 노드들은 before, after, next 상태를 저장하는 포인터를 지니고 있는데 각 포인터들은 다음을 가리킨다.

before : 해당 노드가 가진 키 값의 이전 키값을 참조한다. 이 노드 직전에 삽입된 노드를 가리킨다.

after : 해당 노드가 가진 키 값의 다음 키값을 참조한다. 이 노드 직후에 삽입된 노드를 가리킨다.

next : 해당 노드가 가진 키 값 내에서 다음 항목을 참조한다.

각 노드들은 상호 계층적으로 서로를 참조하며 HashMap 과 동일한 연산을 수행하는데 이 때,

put / remove 등 구조를 변경시키는 연산에 대해서 참조 링크를 바꾸어 가면서 기준값을 중심으로 정렬된 Linked List 형태를 유지한다.

좀 더 자세한 구현과 좋은 설명은 다음 링크를 참조하자.

https://medium.com/@mr.anmolsehgal/java-linkedhashmap-internal-implementation-44e2e2893036

자료구조 Disjoint Set 을 구현하기 위한 알고리즘 혹은 Union Find 알고리즘이라 부르며, 원소들간의 집합을 분류하는 데 사용하는 자료구조이다. 흔히 Minimum Spanning Tree 를 구하는 데 있어서 핵심 자료구조로 많이 사용된다.

우리나라 말로는 서로소 집합 알고리즘 혹은 합집합 알고리즘으로 번역이 되는데, 어떤 의미로든 각 요소들에 대한 집합을 만드는 알고리즘으로 이해하면 쉽다.

주로 알고리즘 문제를 해결할 시, 일정한 기준이 주어지면 그 기준을 토대로 노드들에 대한 집합을 구성해서, 정보를 얻어내는 데 사용된다.

자료구조의 핵심적인 연산으로 Union 연산과 Find 연산이 제공된다.

Union : 두개의 집합을 합치는 연산

Find : 원소가 속한 집합을 반환하는 연산. 함수는 원소가 포함된 집합의 대푯값을 반환해야 한다.

그 외의 연산으로 MakeSet 이라는 특정한 원소를 갖는 집합을 만드는 연산이 있다.

위의 연산들을 이용해서 데이터 간의 파티션을 분류하고, 나뉘어진 파티션을 이용해 정보를 유도해내거나 최적화된 솔루션을 찾는데 이용된다.

연산은 배열 혹은 트리로 구현될 수 있다.

먼저 배열을 통해 구현할 경우 알고리즘은 다음과 같이 동작한다.

1. Find(i) : Array[i] 라는 방식으로 직접 i번째 요소의 메모리에 접근할 수 있다. i번째 요소가 대푯값을 갖고 있으면 O(1) 의 시간복잡도로 구할 수 있다.

2. Union(i, j) : i번째 요소와 j번째 요소를 합친다. 편의상 j번째 요소를 i번째 요소에 합칠 경우, 배열을 전부 순회하여 j번째 요소의 대푯값 J를 대푯값으로 갖는 요소들의 대푯값을 i번째 요소의 대푯값 I로 바꾸어준다. 

O(N) 의 시간복잡도가 생긴다.

따라서 이런 배열식 구현의 경우 N개의 요소에 대해 Union 할 경우 일반적으로 복잡도를 O(NLogN) 으로 여긴다. (각 Union 연산 시 O(N) 의 복잡도가 작업을 수행할 수록 줄어들기 때문이다.)

반면 트리로 구현할 경우, 일반적인 시간복잡도는 O(logN), 아래 기술할 경로압축까지 수행할 경우의 시간복잡도는 O( $${\displaystyle \alpha (n)}) 이 된다. 여기서  $${\displaystyle \alpha (n)} 은 극도로 빠르게 감소하는 상수에 가까운 함수이다. 

(좀 더 수학적인 자료는 다음을 참고한다. https://en.wikipedia.org/wiki/Disjoint-set_data_structure)

트리로 구현하는 점이 코드도 더 간단하고 성능도 좋기 때문에 본 포스팅에서는 트리를 통한 구현을 설명한다.

기본적인 Union Find 알고리즘은 단순히 집합 A 와 집합 B 를 합칠 뿐이지만, Rank 를 부여하면 성능을 더 향상시킬 수 있다.

가령 다음 그림을 보자.

위의 그림처럼 순차적으로 Union 시, 자식노드로 합쳐진다면 이는 배열을 통한 구현과 다를게 없다. 트리의 높이가 높아지는 효과이기 때문에 O(N) 의 시간복잡도를 갖게 된다.

이를 방지하기 위해서는, Rank 의 개념을 도입하여, Rank 가 적은 트리를 높은 트리쪽에 합쳐주는 방법이 사용된다.

이렇게 두 트리를 합칠 때, 두 트리의 Rank 가 같을 경우에만 rank 를 증가시킴으로써, 무분별하게 tree 가 선형으로 합쳐지는 걸 방지하고 트리의 높이를 관리할 수 있다.

Rank 까지 사용하도록 구현하면 최악의 경우에도 시간복잡도가 O(logN) 이 된다.

여기서 좀 더 나아가 노드끼리 서로 합칠 때 포인터를 바로 루트 노드를 참조하도록 하는 방법이 있다. 이를 경로압축(Path Compression) 이라 하며, 최종적으로 생성된 트리는 평평한 구조가 된다.

그리고 마침내 최적화된 O( $${\displaystyle \alpha (n)}) 의 시간복잡도를 가진 알고리즘이 만들어진다.

위의 이론을 바탕으로 한 소스이다. 이론이 다소 어려울 수 있음에도 불구하고, C++로 작성된 다음 소스는 놀랍도록 단순하다.

C/C++ 에서 union 은 키워드로 관리되기 때문에, find / unite 라는 네이밍을 사용하였다. 다음은 위의 코드의 출력 결과이다.

각 집합이 Rank 에 따라 합쳐지고, 성공적으로 대푯값을 갱신하는 것을 볼 수 있다.

앞서 언급했듯이, MST를 구하기 위해 크루스칼 알고리즘이 이용하는 자료구조로도 사용되고, 다양한 값들을 대표값을 기준으로 분류하는데 은근히 많이 사용되는 알고리즘이다. 코딩 면접이나 알고리즘 공부를 한다면 알아두면 매우 유용하게 사용할 수 있다.

 Binary Indexed Tree(이하 BIT) 는 알고리즘이라기 보다는 자료구조에 가깝지만, 흔히 기본 자료 구조라고 할 수 있는 스택, 큐와 같은 자료구조보다는 고급의 자료구조이다. 사촌 격인 Segment Tree 도 있으나 조금 더 설명하기가 어렵기 때문에 본 포스팅에서는 Binary Indexed Tree 만 소개한다.

BIT의 원래 명칭은 Fenwick Tree 이며, 구현 상 Binary Tree 를 이용하기 때문에 BIT(Binary Indexed Tree) 라고 부른다. 

이 이진트리 형태의 자료구조는 효과적으로 부분 요소의 갱신(Update) 와 조회(Select) 를 하기 위하여 만들어진 자료구조로, 많은 변경과 많은 데이터의 조회가 빈번하게 일어날 때 한번에 처리할 수 있는 간단하면서도 유용한 자료구조이다.

특히, 데이터의 일부분이 갱신되었을 때 데이터 전체의 값이 변하는 경우, 가령 데이터 전체의 총합을 구하거나 최댓값을 구하는 일 등을 가장 효과적으로 수행할 수 있는 자료구조이다.

설명을 위해 다음 배열을 준비해보았다.

준비한 배열은 음... 온라인 게임의 유저들의 점수를 나타낸 랭킹 Database라고 해보자. 6명의 유저들이지만 엎치락 뒤치락하고 있는 것을 볼 수 있다. 

이 데이터베이스에서 가장 점수가 높은 유저는 맨 앞에 있는 10점을 획득한 유저이고, 최고점은 10점이다. 최고점을 우리는 DB를 모두 뒤져 시간복잡도 O(N) 만에 최댓값을 찾아내었다. 그런데 10분뒤 상황이 바뀌었다.

갑자기 몇몇 유저의 약진에 힘입어 10점을 획득한 유저는 3등이 되었다. 이런.. 당신은 다시 최고점을 구하기 위하여 DB를 모두 뒤져 최댓값 15를 찾아내기에 이른다. 시간복잡도는 O(N)

이 구조는 효과적일까? 전혀 그렇지 않다. 심지어 실시간 게임이라면 이런식으로 관리했다간 100만명의 유저에 대해 매 Tick 마다 100만명을 전부 검사해야 한다. 물론 알고리즘의 적용 대상을 이런 종류의 실시간 서비스를 예시로 드는건 적절하지 않아보이지만, 더 최적화할 수 있는 방안은 분명히 있다.

<BIT 가 적용된 새로운 자료구조>

위의 그림은 BIT 가 적용된 새로운 자료구조를 보여준다. 위에 보이는 것 처럼 Binary Tree 를 이용한 구조는 추가적인 메모리를 사용하지만, 토너먼트 형태로 최댓값을 구해내고 있다. 또한 보면 알 수 있겠지만 범위별로 최댓값을 구하는 것도 가능하다. 토너먼트를 해당 범위에 대해서만 열면 그만이다.

 눈치챌 수 있겠지만 이 자료구조는 토너먼트 형식을 이용해서 비교해야할 대상과만 비교한다. 가령, A가 B보다 크다는게 보장이 되었을 때, C가 B보다 크다면 A와 C는 서로 비교할 필요가 없다. 전부 비교할 필요 없이 두번만에 최댓값 C를 구할 수 있는 것이다.

다음 코드는 이를 좀 더 명확히 나타내며 C로 작성된 코드지만 이해하기 어렵지 않을 것이다.

 코드를 보면 추가적인 공간을 할당해, 그부분 부터 값을 채우면서 루트 노드에 최댓값을 갱신하고 있는 모습이다.

위의 코드를 이용하면 set 을 통해 인덱스 a에 값 v를 저장하여 펜윅트리를 구성할 수 있고, get 함수를 통해 l 부터 r 까지 범위 내에 있는 최댓값을 어렵지 않게 구해낼 수 있다.

물론 시간복잡도는 set 하는 부분에서 O(logN) 이 소모되지만 get 하는 부분에서 O(logN) 의 효율성을 보인다.

기존에 최댓값을 구하려면 범위 내 모든 요소를 검사해야 했던 O(N) 의 자료구조보다 향상된 범위 검색(Select) 퍼포먼스를 낼 수 있는 것이다. 물론 이를 위해 값의 갱신(Update) 에 O(1) 이 아닌 O(logN) 의 비용을 지불하지만 이는 어떤 종류의 데이터들에 대해 훨씬 효율적일 수 있다.

이번에 포스팅 한 BIT의 경우 Single Update (포인트 갱신) & Range Query (범위 검색) 이지만, 이를 좀 더 수학적으로 개선하면 Range Update (범위 갱신) & Range Query (범위 조회) 에 있어서도 구현이 가능한 막강한 자료구조를 만들어 낼 수도 있다. 이는 Segment Tree 포스팅 이후에 별도로 포스팅을 할 예정이다. (내용이 어렵다 ㅜ)

 힙(Heap)은 특정 연산을 빠르게 수행하기 위한 이진 트리 자료 구조로 부모 노드와 자식 노드간의 일련의 규칙을 통해 일관성있는 결과를 도출해내기 위한 자료구조이다. 

 가령 Min Heap 이라함은 부모가 자식보다 작은 이진 트리를 구성하며 루트노드가 즉 전체 데이터의 최솟값이 된다. 반대로 Max Heap 은 부모가 자식보다 큰 자료구조이기 때문에 루트노드는 전체 데이터의 최댓값을 나타낸다.

 Binary Heap 을 구현할 경우 이진 트리의 Root 노드부터 단일 Leaf 노드까지의 순회비용만 가질 뿐이므로 Insert 와 Delete 연산이 모두 O(logN) 의 복잡도를 갖으며 Min Heap / Max Heap 과 같은 기능적 힙을 구현하는 경우 (아마 대부분의 경우), 조회(Peek) 의 시간 복잡도는 O(1) 로 아주 효율적이다.

다음은 Binary Heap 의 배열을 이용한 예시의 그림이다. 

<Binary Heap 에서 Push 의 Work flow>

 Binary Heap 에서 새로운 값을 Push 할 때에는 Heap 의 마지막 위치(Leaf Node)에 값을 넣고, 루트 노드(Root Node) 까지 올라오면서 맞는 위치를 찾는다.

Min Heap 이냐 Max Heap 이냐에 따라서 조건에 만족한다면 해당 위치에 멈추고, 더 위쪽 노드로 가야한다면 부모노드와 Swap 해준다. 자매 노드(Siblings) 를 고려하지 않아도 되기 때문에 구현은 편안하다.

<Binary Heap 에서 Pop 의 Work flow>

 Pop 연산은 이와 반대로 구현된다. 특성상 무조건 Root Node 에 원하는 값이 있다. Min Heap 의 경우 데이터 전체의 최솟값이, Max Heap 의 경우 데이터 전체의 최댓값이 있다.

따라서 꺼내오는 시간은 O(1) 이며, 대신 꺼낸 자리에 Leaf Node 로 보낼 값을 집어넣는다. Min Heap의 경우 최댓값을 넣어 무조건 맨 끝으로 보낼 수 있게 한다. 그리고 나서는 왼쪽 자식(Left) 과 오른쪽 자식(Right) 을 비교하여 더 작거나(Min) 더 큰(Max) 값과 부모의 값을 교환하면서 내려간다.

이에 대한 자세한 구현은 다음 코드를 참조하자. C 로 구현되어있으나 어렵진 않을 것이다.

이처럼 힙은 데이터를 다루고 관리하는 유용한 자료구조이며 이 자료구조를 응용한 대표적인 사례가 우선순위큐(Priority Queue) 이다. 가령 각 노드별로 우선순위를 기록하고, 모든 노드의 우선순위(1~N) 대로 Min Heap 을 구성한다면 우선순위의 Ordering 이 낮은 순서대로 데이터를 뽑아낼 수 있다.

우선순위큐는 우선순위를 순차적으로 뽑아낼 수 있는 Push / Pop 이 가능한 자료구조일 뿐 그 구현이 Heap 일 필요는 없지만, 보통 Heap 을 이용해서 구현할 경우 Push 와 Pop 에 O(logN) 이라는 저렴한 시간복잡도가 들기 때문에 주로 Heap으로 구현이 된다.

즉, Priority Queue 를 Heap 을 이용해 만들 수 있지만 Heap 과 Priority Queue 간에는 직접적인 연관은 없으며 다만 구현에 있어서도, 기능에 있어서도 Heap 을 이용해 만드는 것이 효과적이므로 거의 동일어나 다름없이 혼용되고 있을 뿐이다.

각종 기업 면접과 테스트에서 코딩 테스트라 불리는 알고리즘 역량이 상당히 중요해진 만큼, 연습하는데 있어서 정말 유용한 자료구조이니, 위의 코드는 외워두고 써도 좋다.