Sorted Map과 Skip List 톺아보기
1. Sorted Map
1.1 Sorted Map이란?
Sorted Map은 key-value 쌍 데이터를 key 순서대로 정렬하여 저장하는 자료구조다(key는 자연수임을 가정). 즉, 키를 통해 값을 빠르게 찾을 수 있을 뿐만 아니라, 정렬된 순서대로 데이터를 탐색할 수 있다는 장점이 있다.
1.2 Sorted Map의 활용 예: Maxima Sets (최대값 집합)
Maxima Sets는 2차원 평면에서 x 좌표가 증가할 때 y 좌표가 감소하지 않는 점들의 집합을 찾는 문제이다. Sorted Map을 사용하면 효율적으로 Maxima Sets를 찾을 수 있다.
def find_maxima_sets(points):
maxima_sets = []
sorted_map = {} # Sorted Map 사용
for x, y in sorted(points): # 점들을 x 좌표 기준으로 정렬
if not sorted_map or y > sorted_map.peekitem()[1]: # 현재 y 값이 가장 큰 y 값보다 크면
sorted_map[x] = y # Sorted Map에 추가
maxima_sets.append(list(sorted_map.items())) # Maxima Sets에 추가
return maxima_sets
위 코드는 Maxima Sets를 찾는 알고리즘이다. 점들을 x 좌표 기준으로 정렬한 후, Sorted Map을 사용하여 현재까지 가장 큰 y 값보다 큰 점들만 저장한다. 이렇게 하면 Maxima Sets를 효율적으로 찾을 수 있다.
2. Skip List
2.1 Sorted Map의 한계 극복
Sorted Map은 array나 linked list로 구현할 수 있다. 하지만 array로 구현하면 삽입/삭제 연산에 O(n) 시간이 소요되고, linked list로 구현하면 binary search을 사용할 수 없어 검색 속도가 느려진다. Skip List는 이러한 Sorted Map의 한계를 극복하기 위해 고안된 확률적 자료구조다.
2.2 Skip List의 구조
Skip List는 여러 개의 linked list로 구성되며, 각 리스트는 이전 리스트의 일부 노드만 포함한다. 결과적으로 검색, 삽입, 삭제 연산의 시간 복잡도를 평균 O(log n)으로 줄일 수 있다.
 |
| skip list |
* skip list의 동작 :
- next(p) : 같은 층의 다음 node return
- prev(p) : 같은 층의 이전 node return
- below(p) : 바로 아래 층의 node return
- above(p) : 바로 위 층의 node return
2.3 Skip List의 핵심 연산
- Search (검색): 가장 상위 리스트에서 시작하여, 찾는 키 값보다 작거나 같은 키 값을 가진 노드를 찾을 때까지 오른쪽(next 동작)으로 이동한다. 만약 다음 노드의 키 값이 찾는 키 값보다 크면 아래쪽 리스트(below 동작)로 이동하여 탐색을 계속한다.
- Insert (삽입): 먼저 검색 과정을 통해 삽입할 위치를 찾는다. 그 후, 동전 던지기를 통해 새로운 노드가 포함될 리스트(몇 층일지)를 결정하고, 해당 리스트에 노드를 삽입한다.
- Remove (삭제): 검색 과정을 통해 삭제할 노드를 찾은 후, 해당 노드를 모든 리스트에서 제거한다.
3. 마무리
Sorted Map은 key 순서대로 데이터를 관리하고 탐색하는 데 유용한 자료구조다. Skip List는 Sorted Map의 한계를 극복하여 검색, 삽입, 삭제 연산을 효율적으로 수행할 수 있도록 한다.역시 문제를 발견하고, 더 나은 알고리즘을 찾아 해결해나가는 것... 참 대단하다.
