2.2.3 적합한 자료 구조 생각하기

몇 가지 문제에서는 가장 적합한 자료 구조를 선택하기가 쉽습니다. 예를 들어 주어진 값에서 최솟값과 최댓값을 찾는 문제가 있다면 힙(heap)이 적합합니다. 이 책에서는 많은 자료 구조를 다루는데, 그중에서 필요한 자료 구조를 찾아내야 합니다.

문제 하나를 살펴봅시다. 스트림 데이터가 주어졌을 때 언제든지 중간값(median)을 찾아서 값을 확인하고 꺼낼(pop) 수 있어야 합니다. 중간값을 루트로 가지는 균형 트리(balanced tree)의 정렬을 고려해 볼 수 있습니다. 기다리세요! 중간값을 루트로 만드는 것은 그리 쉬운 일이 아닙니다.

힙을 사용하면 최솟값 또는 최댓값만 구할 수 있어서 원하는 결과를 얻을 수 없습니다. 최대 힙(max heap)과 최소 힙(min heap)의 두 개 힙을 사용한다면 어떨까요? 작은 값들은 최대 힙으로 보내고 큰 값들은 최소 힙으로 보냅니다. 또한, 힙에 몇 개의 원소가 있는지 셀 수 있습니다. 알고리즘의 나머지 부분은 여러분 스스로 생각해 보세요.

처음 보는 문제를 접할 때마다 자료 구조를 떠올려 보세요. 이 중 하나 또는 몇 개의 조합으로 문제를 풀 수 있을 것입니다.

이전에 풀어 본 비슷한 문제를 생각해 보세요. 두 연결 리스트의 머리(head) 포인터가 주어진 상황을 가정해 봅시다. 두 리스트가 어떤 지점에서 만나는지 그 교차점을 찾아야 합니다. 두 연결 리스트의 끝은 널 포인터 대신에 루프로 되어 있습니다.

여러분은 교차하는 두 연결 리스트의 교차점을 찾는 법을 알고 있고 연결 리스트에 루프가 있는지를 확인하는 법도 알고 있습니다(플로이드의 순환 찾기 알고리즘). 따라서 이 두 가지 해결책을 이용해 이 문제의 해결책을 찾을 수 있습니다.