머리말
이 책으로 공부하는 법
이진 탐색
1. 이진 탐색 — 가운데 한 칸을 읽으면 나머지 절반이 후보에서 빠진다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
2. 파라메트릭 이진 탐색 — 답을 만들지 않고 「이 값이면 되는가」만 물으면 답이 후보 구간이 된다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
3. 삼진 탐색 — 두 자리의 함숫값을 비교하면 최솟점이 없는 3분의 1 이 정해진다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
해시맵 / 해시셋
4. twoSum — 짝을 찾지 않고 보수를 해시 맵에서 조회하면 한 번만 지나가도 되는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
5. missingInteger — 답이 n + 1 을 넘지 않아서 칸 n 개로 충분한 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
두 포인터 / 슬라이딩 윈도우
6. 슬라이딩 윈도 — 합이 S 이하인 가장 긴 구간에서 왼쪽 끝을 되돌리지 않아도 되는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
7. 구간 교차 쌍 세기 — 오른쪽 끝이 먼저인 쪽에서 쌍을 한 번씩만 세는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
누적합 (Prefix Sum)
8. 누적합 — 구간 합을 두 칸의 뺄셈으로 끝내는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
9. 합이 k 인 구간 세기 — 구간을 하나씩 재지 않고 지나온 누적합의 개수만 묻는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
10. 차분 배열 — 구간 전체를 고치지 않고 경계 두 칸만 적어 두는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
11. 게으른 전체 갱신 — 모든 칸을 맞추는 연산을 수 하나로 적어 두는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
정렬
12. 병합 정렬 — 합치는 비용이 가르는 자리와 무관해서 줄일 것은 층 수뿐이다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
13. 퀵 정렬 — 값 하나를 제자리에 놓으면 남은 일이 둘로 갈라진다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
14. 삽입 정렬 — 앞부분을 정렬된 채로 두면 비교 횟수가 흐트러진 정도로 정해진다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
15. 계수 정렬 — 값을 칸 번호로 쓰면 두 값을 비교할 일이 없다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
16. 자릿수 정렬 — 가장 높은 자리를 마지막에 처리해야 앞 바퀴의 순서가 남는다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
BFS
17. 너비 우선 탐색 최단 경로 — 꺼내는 순서를 거리 순서로 만들면 한 번 본 정점을 다시 안 본다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
18. 연결 성분 — 성분 번호를 성분 사이에 지우지 않으면 탐색 전체가 한 번으로 줄어드는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
DFS / 백트래킹
19. 깊이 우선 방문 순서 — 큰 번호부터 스택에 넣어야 작은 번호부터 나온다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
20. 모든 단순 경로 열거 — 되돌아갈 때 표시를 지워야 다음 경로가 만들어진다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
21. 섬 개수 세기 — 새 땅에서 탐색을 시작한 횟수가 그대로 섬의 개수가 되는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
22. N-Queens — 충돌이 확정된 행에서 멈추면 그 아래 배치를 하나도 만들지 않는다
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
Kadane's Algorithm (최대 부분합)
23. 카데인 알고리즘 — 직전 칸에서 끝나는 최대합이 음수면 이어 붙이지 않는 쪽이 항상 더 큰 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
24. 최대 부분 배열 곱 — 직전 칸의 최솟값이 다음 칸의 최댓값이 되는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
1차원 DP
25. 이웃하지 않은 칸의 최대 합 — 칸 i 를 고른 답이 두 칸 앞의 답에서 나오는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
26. 동전 조합의 경우의 수 — 동전 종류를 바깥 루프에 두면 같은 조합이 한 번만 세어지는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
27. 0/1 배낭 — 담는 쪽을 윗 줄에서 읽으면 물건이 한 번씩만 담기는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
28. 한 번 거래의 최대 이익 — 파는 날을 하나 고정하면 사는 날은 고를 것이 하나뿐인 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
재귀·분할 정복
29. 최솟값·최댓값 함께 찾기 — 원소 둘을 먼저 비교하면 비교 한 번에 후보가 둘 빠지는 이유
파트 1 — 아이디어에서 동작하는 코드까지
파트 2 — 적용 조건 · 보장 · 비용
실습 — 직접 풀어 보기
마무리