유용한 자료구조와 알고리듬

• Bloom Filter: 확률적으로 멤버십을 테스트하는 자료 구조, 실시간 탐지에 유용하다.
• Dancing Link: NP-complete 문제의 하나인 exact cover(subset의 collection이 다시 set을 정확하게 구성하는 조합)를 풀기 위해 알고리듬 X의 기반이 되는 자료구조이다.
• Trie: prefix가 일치하는 인덱스를 통해 빠르게 값을 찾을 수 있는 자료구조로서, 동적인 해시 트리라고 할 수 있다.
• Suffix Tree: suffix가 일치하는 인덱스 자료구조로서, 특정 문자열의 패턴을 검출하는 도구로 사용된다.
• Splay Tree: 최근에 접근했던 데이터를 다시 빠르게 접근할 수 있는 자료 구조로서 균형잡힌 이진 탐색 트리 구조이다.
• Rope: string 타입의 확장 자료형, 이 블로그에서도 전에 STL의 rope container를 소개한 바가 있다.
• R-tree: 2차원 공간 데이터의 포함 관계를 나타내기에 적합한 자료구조
• KD-tree: 다차원 공간 데이터의 구간 탐색이나 이웃 탐색에 유리한 자료구조이다.
• Bit array: 비트맵 자료구조
• QuadTree: sparse한 2차원 데이터의 공간적인 관계를 표시하거나 이미지 표현에 유용한 자료구조이다.
• Inverted Index: 문서에 포함된 키워드가 문서를 가리키도록 만들어진 인덱스 자료구조, full text search에 가장 쉽게 사용되는 자료 구조이다.
• Disjoint-set data structure: 집합을 partition하거나 MST를 찾는 알고리듬을 지원하는 자료구조
• Binary space partitioning: 복잡한 구조의 객체를 단순한 볼록 다각형으로 partition하는 알고리듬, 3D 객체를 2D 화면에 렌더링하면서 색칠할 때 복잡한 색칠 순서를 결정하는 데 도움을 주는 방법이다.
• van Emde Boas tree: 기본 연산의 수행 시간이 O(log log n)인 트리 자료 구조. 한정된 2^n 비트 키 공간에서 특정 키를 이진 탐색으로 찾아내기에 유리한 트리들의 트리 구조
• Huffman coding: 무손실 압축 알고리듬에 이용되는 기본 코딩 방식
• Binomial heap: 주로 두 개의 heap을 합치는 데 사용되는 binary heap
• Fibonacci heap: 설명 생략
• Pairing heap: 설명 생략
• Spiral Storage: 점진적으로 커지는 해시 기반의 저장소
• Judy array: hash table보다 빠른 해시 자료구조. 빠르고 공간 사용량이 적어서 주로 cache 알고리듬에 이용된다.
• Cuckoo hashing: 해시 충돌 해소 알고리듬. 뻐꾸기 새끼가 다른 알을 내버리는 것처럼, 새로운 키를 놓을 때 같은 자리에 이미 놓여있던 기존 키를 다른 위치로 옮기고 새로운 키를 그 자리에 놓는 방법이다.
• Circular buffer: 너무나 유명한 링 버퍼, 설명이 필요없다.
• Counted B-tree: 중앙값이나 백분위수를 빠르게 찾을 수 있는 b-tree 변형
• Suffix array: 부분문자열을 빠르게 찾을 수 있는 인덱스 자료구조
• Binary decision diagram: binary decision tree를 효율적으로 재배치한 자료구조로서 회로 설계에서 주로 사용된다.
• Skiplist: 계층적인 구조로 만들어진 리스트, 일반 linked list와는 달리 random access에 유리하다. 이진 탐색 트리의 장점을 도입한 리스트라고 할 수 있다.

작년 가을에 회사 신규채용 필기시험 출제위원으로 문제를 출제한 경험이 있다. 다른 출제위원들과 함께 자료구조와 알고리듬 분야를 담당하였다. 마침 문제 검토 회의가 추석 지나고 바로 뒤에 잡힌 덕분에, 추석 연휴 내내 학부시절에 배웠던 자료구조와 알고리듬 책을 꼼꼼하게 살펴보며 복습하는 시간을 갖게 되었다. 입시준비하는 고등학생처럼 추석 명절에 책에 파묻혀 공부할 수 밖에 없는 상황이 황당할 수 밖에 없었지만, 책임지고 좋은 문제를 내려면 열심히 공부하지 않을 수가 없었다. 실상은 학부 시절에 열심히 공부하지 않았던 탓이 크다.

입사 필기시험에 나오는 문제에는 이 글에서 소개한 것처럼 어려운 자료구조나 알고리듬은 나오지 않는다. 이 중에서 trie, suffix tree, r-tree, kd-tree, bit-array, inverted index, huffman coding, fibonacci/binomial heap, circular buffer 등은 교과서에도 나오는 쉬운 자료구조니까 필수적으로 알 필요가 있지만, 나머지 자료구조는 어떤 용도에 쓰이는지, 어떤 장점을 가지는지를 알고 있기만 하면 된다.

매년 입시에서 서울대 수석들은 이렇게 말하곤 한다.

“교과서를 기반으로 국/영/수 과목의 예습/복습을 철처히 했다.”

이 말은 필승 입시 전략이라는 제목 하에 종종 우스개소리로 회자되곤 한다. 너무 당연한 소리고, 실상 아무런 쓸모가 없는 이야기니까 우스개가 되는 것이다.

하지만, 서울대 수석들이 거짓말을 했을까? 난 아니라고 생각한다. 국/영/수의 기초를 서울대 수석만큼 쌓는 것은, 어렵고 다양한 문제집을 많이 풀어보는 것으로는 도달할 수 없는 수준인 것이다. 서울대 본고사 문제를 본 사람들이라면 느꼈겠지만, 타 학교의 문제와 큰 차이를 보인다. 의외로 평범한 문제들만 나오는 게 다른 점이다. 수학 정석으로 치자면 실력편이 아닌 기본편에 심화 문제도 아니고 기본 문제로 나오는 그런 문제들만 나온다. 그 문제를 서울대 지원한 학생들끼리 누가 더 제대로 풀고 증명하는지 경쟁하는 꼴이다. 이게 비비 꼬아서 어렵게 만든 문제를 푸는 것보다 어려울까 쉬울까?

내가 하고 싶은 말은 개발자들이 독특한 자료구조나 알고리듬으로 손쉽게 해법을 찾으려 하지 말고 기초 자료구조와 알고리듬을 제대로 익혀두라는 말이다. 필기시험 문제가 주로 너무나 뻔한 문제들이 객관식으로 출제되는 데다가 그냥 대충 비슷한 답을 골라도 다 맞출 수 있는 수준인데도 겨우 평균 50점 밖에 안 된다니 한심스러워서 하는 말이다. 사실 출제를 해봤다지만 나도 부족한 점이 많아서 잘 모르는 알고리듬에 대해서 계속 공부를 해야겠다는 생각이 든다. 한국 개발자들은 너무 공부를 하지 않는 것이 문제다.