자료구조와 알고리즘을 두 개의 시리즈로 나눠 다룹니다. 자료구조 시리즈는 데이터를 담고 정리하는 구조를, 알고리즘 시리즈는 그 안에서 찾고 결정하는 방법을 봅니다. 각 편이 독립적으로 읽히도록 구성했고, 이 편은 전체 지도 역할을 합니다.
read →
시간 복잡도를 정의부터 다시 정리하고, 입력 크기 N에서 허용 가능한 복잡도를 역산하는 방법을 다룹니다. 상수를 버리는 표기법의 이점과 한계, 최선과 평균과 최악을 구분해야 하는 이유, 공간 복잡도를 함께 세는 습관까지 확인합니다.
배열이 연속된 메모리라는 사실에서 따라오는 비용 구조를 정리하고, 해시 테이블의 충돌 처리 방식과 평균 성능이 깨지는 조건을 확인합니다. 자바스크립트 배열로 큐를 만들 때 생기는 함정과 그 해법도 함께 다룹니다.
자바스크립트 기본 정렬이 값을 문자열로 바꾼다는 사실에서 출발해, 안정 정렬이라는 성질이 다중 기준 정렬에서 어떻게 작동하는지 다룹니다. 퀵 정렬과 병합 정렬과 힙 정렬의 성격 차이, 비교 정렬의 하한과 그것을 우회하는 계수 정렬까지 정리합니다.
이진탐색트리가 절반씩 버리는 원리와 그 전제가 무너지는 편향 상황을 확인하고, 균형 트리가 어떤 방식으로 높이를 통제하는지 정리합니다. 힙이 완전 정렬을 포기해서 얻는 이득과, 자바스크립트에 없는 우선순위 큐를 직접 구현하는 방법도 다룹니다.
누적합으로 구간 질의를 상수 시간으로 만드는 방법과 2차원 확장을 다루고, 중간에 값이 바뀌는 상황에서 그 전략이 무너지는 지점을 확인합니다. 세그먼트 트리가 질의와 갱신을 모두 O(log N)으로 유지하는 원리와 선택 기준을 정리합니다.
