코딩 테스트 중상위 문제와 실무에서 종종 만나는 자료구조 12편을 모았습니다. 구간 질의를 맡는 세그먼트 트리와 펜윅 트리, 문자열을 담는 트라이·라딕스 트리·삼분 탐색 트리를 다뤄요. 최소 힙·최대 힙·우선순위 큐·d-진 힙과 단조 스택·단조 큐, LRU 캐시도 들어 있습니다.

모든 장은 계약에서 출발합니다. 이 자료구조가 무엇을 하고 어떻게 생겼는지 그림으로 먼저 봐요. 그다음 공개 메서드와 연산마다의 의미, 비용 상한을 계약으로 고정하고 그 계약을 지키는 내부 모양을 한 단계씩 쌓아 올립니다. 정해 둔 연산을 하나씩 불러 가며 내부가 어떻게 바뀌는지 끝까지 따라가면 마지막 단계에서 전체 코드가 완성돼요. 같은 계약을 지키는 구현이 여럿이면 방법마다 따로 다룹니다. 뒤 파트에서는 어디에 쓰는지, 연산을 몇 번 이어 불러도 참으로 남는 불변식은 무엇인지, 최악·상각·기대 비용이 어디서 갈리는지를 따집니다.

「그렇게 해도 되지 않나」 싶은 방법은 반례로 왜 틀리는지 짚고 넘어가요. 장 끝에는 스스로 답해 볼 물음과 그 답, 그 자료구조를 계약대로 직접 구현해 보는 문제가 있습니다. 코드는 TypeScript로 썼어요.

기본 자료구조를 익힌 뒤 구간 질의·문자열 탐색·우선순위 처리처럼 한 단계 위의 문제를 다루려는 분께 맞는 책이에요. 시리즈는 중요도에 따라 네 권으로 나뉘고, 이 책은 시리즈의 2권입니다.

본문 초고는 생성형 AI(Claude)가 쓰고, 저자가 검토하고 고쳤습니다.