Top-K — heap 이 항상 답은 아니다
K번째 큰 값 문제에서 heap 은 반사적인 선택이지만, 전체 배열이 이미 메모리에 있다면 Quick Select 가 평균 더 빠르다. heap 크기 K 유지와 Quick Select 의 메커니즘, 그리고 데이터 형태에 따른 선택 기준.
알고리즘
Union-Find — 두 최적화가 O(N) 을 상수로 만든다
Union-Find 는 그룹마다 root 대표를 두고 같은 그룹인지 판정한다. 최적화 없는 구현은 사슬 트리에서 find 가 O(N) 까지 늘어지지만, path compression 과 union by rank 를 더하면 사실상 상수가 된다.
위상정렬 — 진입차수 0 부터 처리한다
위상정렬의 Kahn BFS 는 진입차수 0 인 노드를 반복해서 꺼내 처리하는 알고리즘이고, 사이클 검출은 별도 로직 없이 따라온다. Kahn BFS 의 메커니즘, Course Schedule 유형, DFS post-order 와의 선택 기준.
슬라이딩 윈도우와 누적합 — 단조성이 도구를 가른다
부분 배열 합 문제는 슬라이딩 윈도우와 누적합 두 도구로 O(N) 환원된다. 입력에 음수가 섞이거나 합이 정확히 K 인 등식 조건이 붙으면 단조성이 깨지고, 도구는 누적합 + 해시 영역으로 넘어간다.
Parametric Search — 답을 이분탐색한다
답을 직접 찾지 못하는 문제도 결정 함수와 단조성이 보이면 답 자체를 이분탐색할 수 있다. parametric search 의 사고 패턴 — 결정 함수 정의, 단조성 방향, lo/hi 정당화.