이 책으로 공부하는 법
Dijkstra 최단 경로
1. 다익스트라 — 우선순위 큐에서 거리가 가장 작은 정점을 꺼내면 그 거리가 이미 최단인 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
위상 정렬
2. 위상 정렬 — 진입 차수가 0 이 되는 순간 큐에 담으면 맨 앞에 놓을 정점을 다시 찾지 않는다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
3. DAG 최단 경로 — 위상 순서대로 한 번씩 완화하면 정점의 차례에 그 거리가 이미 확정되는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
2D DP
4. 최장 공통 부분 수열 — 마지막 두 글자만 보면 과제가 한 칸 작아지는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
5. 편집 거리 — 마지막 한 번의 편집만 정하면 과제가 한 칸 작아지는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
6. 최대 k 번 거래의 최대 이익 — 거래 번호를 상태에 넣으면 거래 조합 열거가 날마다 상태 2k 개의 갱신이 되는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
LIS (최장 증가 부분 수열)
7. 최장 증가 부분 수열 — 길이마다 가장 작은 끝값만 남기면 자리를 이진 탐색으로 찾을 수 있는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
최소 신장 트리 (MST)
8. 크러스컬 최소 신장 트리 — 사이클 검사를 두 끝점의 대표 비교 한 번으로 줄이는 유니온 파인드
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
9. 프림 최소 신장 트리 — 경계를 넘는 가장 가벼운 간선을 우선순위 큐가 들고 있어 매번 다시 찾지 않는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
세그먼트 트리 / Fenwick Tree
10. segmentTreeRangeMin — 반씩 갈라 적어 둔 구간으로 질의는 깊이마다 둘, 갱신은 깊이마다 하나만 만지는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
11. 펜윅 트리 — 칸마다 최하위 1 비트만큼의 구간을 맡기면 갱신과 질의가 둘 다 자릿수만큼만 걸리는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
Trie
12. 트라이 — 같은 앞부분을 한 노드에 모으면 조회가 담긴 단어의 개수를 안 보는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
13. 라딕스 트리 — 갈림 없는 구간을 라벨 하나로 접으면 노드 수가 단어 수를 따라가는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
문자열 검색 (KMP, Z, Rabin-Karp)
14. findAllOccurrences — 이미 맞은 부분이 다음 시작 자리를 스스로 알려 주는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
힙 / 우선순위 큐
15. 두 힙으로 구하는 스트림 중앙값 — 정렬된 수열 전체가 아니라 가운데 두 자리만 알면 되는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
Top-K 문제
16. 빈도 버킷으로 상위 k 개 고르기 — 등장 횟수는 N 을 넘지 못해 그 수를 칸 번호로 쓸 수 있다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
Quickselect (k번째 원소)
17. 퀵셀렉트 — 기준값 하나의 자리가 정해지면 목표가 없는 쪽은 다시 볼 이유가 없다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
비트마스크·비트 연산
18. 서브마스크 열거 — 1 을 빼고 mask 로 거르면 다음 서브마스크가 바로 나오는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
19. XOR 누적 — 짝수 번 나온 값이 스스로 지워져 하나만 남는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
20. x & -x — 자리올림이 최하위 1 비트에서 멈춰 검사 없이 그 비트만 남는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
21. binary gap — 직전 1 비트의 자리 하나만 기억하면 한 번 차례로 읽어 답이 나오는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
회전된 정렬 배열 탐색
22. 회전된 정렬 배열에서 찾기 — 가운데에서 가르면 두 반쪽 중 하나는 반드시 정렬돼 있다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
단조 스택
23. nextGreaterElement — 답을 기다리는 자리를 쌓아 두면 큰 값 하나가 여러 자리의 답을 한꺼번에 정하는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
24. largestRectangleInHistogram — 막대를 단조 스택에서 꺼내는 순간 그 막대를 높이로 하는 가장 넓은 직사각형의 양 끝이 함께 정해지는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
단조 덱
25. slidingw-indowMaximum — 창 밖으로 나간 자리는 앞에서, 답이 될 수 없는 자리는 뒤에서 버리면 창마다 최댓값이 맨 앞에 남는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
사이클 검출
26. 유향 사이클 탐지 — 지금 따라가는 경로 위의 정점으로 되돌아오는 간선이 사이클의 증거다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
27. 무향 사이클 탐지 — 방금 지나온 이웃 하나만 빼면 표시 한 벌로 판정된다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
이분 그래프 판정
28. 이분 그래프 판정 — 한 정점의 쪽을 정하면 연결 성분 전체의 쪽이 따라 정해지는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
부분집합 합·배낭 변형
29. 부분집합 합 판정 — 합이 같은 부분집합을 구분하지 않으면 2^n 가지가 DP 테이블 한 장이 된다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
30. 최소 동전 개수 — 같은 줄에서 읽으면 같은 액면가를 몇 개든 쓰게 되는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
트리 DP
31. 트리 최대 가중 독립집합 — 정점마다 칸을 둘로 갈라 올려야 부모가 자식의 선택을 안다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
32. 트리 지름 — 아무 정점에서 가장 먼 곳은 반드시 지름의 한쪽 끝이다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
구간 DP
33. 행렬 체인 곱셈 최소 비용 — 마지막으로 곱하는 자리 하나가 나머지를 두 조각으로 가른다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
34. 팰린드롬 분할 최소 컷 — 회문 판정을 구간마다 한 번 적어 두면 접두사마다 컷 수 하나로 답이 나온다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
자리수 DP (Digit DP)
35. 자릿수 DP — 「아직 상한 N 에 붙어 있는가」 참·거짓 하나로 수를 세지 않고 자리마다 만들 수 있는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
거듭제곱 (Fast Exponentiation)
36. 이진 거듭제곱 — 지수를 한 칸 옮길 때마다 곱셈이 많아야 두 번인 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
37. 행렬 거듭제곱 피보나치 — 한 걸음을 행렬 하나로 적으면 이진 거듭제곱이 걸음 수를 합치는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
GCD / 확장 유클리드
38. 유클리드 호제법 — 큰 수를 나머지로 바꿔도 공약수 집합은 그대로다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
39. 확장 유클리드 호제법 — 나머지를 만든 몫 하나가 계수 갱신까지 정한다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
40. 이항 계수 mod 소수 — p 진 자릿수로 가르면 분모의 역원이 언제나 있는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
에라토스테네스의 체·소수 판정
41. 에라토스테네스의 체 — 소수인지 묻지 않고 배수를 지우면 남는 수가 소수인 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
42. 소수 판정 (시행 나눗셈) — 작은 약수는 √n 을 넘지 않아서 거기까지만 나눠 보면 된다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
마무리