자료구조

높이 쌓아올려진 책에 대해 생각해보자. 각각의 책은 너무나 무거워서, 책탑의 중간에서 한 권을 빼낸다는 일은 불가능하다. 우리가 안전하게 꺼낼 수 있는 책은 탑 맨 꼭대기에 놓인 책뿐이고, 책을 얹을 때에도 맨 위에만 얹을 수 있다.

 

이것도 '스택(stack)'이라고 부를 수 있을까? 의견이 조금 갈릴 것 같다. 스택과 닮은 구석은 있지만 스택이라고 단언하기에는 마음에 걸리는 부분이 있는 것이다.

 

그렇다면 Python에서 list, append(), pop()으로 구현한 스택은 스택이 맞나? 어찌 되었건 pop(idx)를 통해 list의 가장 끝이 아닌 인덱스의 원소도 빼낼 수 있지 않나?

 

후입선출의 구조를 상호작용의 자유도 측면에서 제한해야만 스택일까? 사용자 측에서 후입선출의 특징만을 이용하고 있는 것만으로는 부족할까?

 

자료구조는 해당 자료구조를 정의하는 특성이 있다. 그리고 그러한 특성과 어울리는 부류의 문제들이 있다. 결국 자료구조란 문제를 해결하기 위한 방법론 중 하나라고 생각한다. 쌓인 책을 들어내는 방식이나, 수많은 사람이 늘어선 대기열을 처리하는 방식 등.

 

문제는 어떤 자료구조는 보다 추상적이고, 어떤 자료구조는 보다 구체적이라는 점이다. 스택이나 큐(queue)처럼 아주 간단한 원칙만을 갖고 있는 자료구조는 세부 구현의 여지가 다양하다. 힙(heap)의 경우에는 세부 구현의 여지가 없다시피 하다.

 

중간 정도 되는 예를 생각해보자. 우선순위 큐(priority queue)는 무엇이 들어오든 간에 우선순위가 높은 것이 먼저 나오는 자료구조다. 이러한 자료구조를 구현하는 방법은 무수히 많다. 배열에 입력을 저장하되 입력이 들어올 때마다 우선순위를 매길 대상을 기준으로 매번 오름차순 정렬을 하여 pop이 가능하도록 만들더라도 우선순위 큐다. 다만 효율적이지 않을 뿐.

 

달리 말하자면 우선순위 큐를 구현하는 데 있어 힙은 효율적인 선택에 불과하고, 힙 그 자체는 우선순위 큐가 아니며, 우선순위 큐 또한 힙이 아니다. 더 나아가서 우선순위 큐로 스택이나 큐를 구현할 수도 있다. 삽입되는 순서에 맞춰 우선순위를 부여하면 된다.

 

다시 돌아가서, 이러한 특성들과 잘 맞닿는 영역에 대해서도 알아야 한다. 단순히 알고리즘 문제 해결에서 단순히 적절한 자료구조를 선별하여 구현의 베스트 프랙티스를 인출하는 것뿐만 아니라, 인터페이스 안쪽에서 최적화를 꾀하는 사람들은 인터페이스 바깥에서의 상황을 고려하여 더 나은 방식으로 구현하기 위해서 고민해야 하며 데이터베이스의 인덱스에 대해 알아보고 있다면 B+ 트리가 어째서 선택되었는지를 이해해야 한다.

 

자료구조는 이렇듯 특성이, 특성의 추상도가, 구현 방식이, 실제 활용이 중요하다. 그 넷을 전부 알아야 한다.