개념
페이즈 2에서 배운 것은 전부 '완전탐색의 낭비를 어떻게 줄이는가'에 관한 것이었어요. 정렬로 순서를 만들어 두거나, 포인터 두 개로 이중 반복문을 접거나, 매번 절반을 버리거나. 이번 주는 그 도구들을 한 장으로 정리하고 섞어서 풀어 봐요.
도구 선택 기준
| 필요한 것 | 도구 | 주차 |
|---|---|---|
| 여러 기준으로 줄 세우기 | 비교자 / 키 함수 | 7주차 |
| 값의 범위는 큰데 종류는 적다 | 좌표 압축 | 7주차 |
| '정렬된 배열에서 두 수' | 양끝 투 포인터 | 8주차 |
| '가장 긴 연속', '연속된 구간' | 슬라이딩 윈도우 | 8주차 |
| '부분 수열의 합이 최대' | 카데인 | 8주차 |
| 매 순간 최선이 전체 최선인가 | 그리디 | 9주차 |
| 가장 최근 것과 짝 맞추기 | 스택 | 10주차 |
| 넣은 순서대로 처리하기 | 큐 · 덱 | 10주차 |
| 정렬된 데이터에서 빠른 검색 | 이분 탐색 | 11주차 |
| '최대의 최소' 같은 최적값 | 답을 이분 탐색 | 11주차 |
그리디를 믿어도 될 때
페이즈 2에서 가장 판단이 흔들리는 지점이에요. 그리디는 맞으면 가장 짧은 코드고, 틀리면 예제만 통과하고 제출은 떨어져요. 제출 전에 이 순서로 확인해요.- 지금 최선을 고르면 나중 선택지가 줄어드는가? 줄어든다면 그리디는 위험해요
- 작은 반례를 30초만 찾아봐요. 동전
[1, 4, 5]로 8원 만들기 같은 것 - 반례를 못 찾겠고
n도 작다면, 완전탐색으로 같은 답이 나오는지 대조해요 (4주차) - 여전히 불안하면 DP를 의심해요 — 그리디가 깨지는 문제의 대부분은 DP예요 (19주차)
이번 주 진행 방법
유형을 밝히지 않은 4문제예요. 90분 타이머를 걸고, 문제마다 '어떤 도구를 왜 골랐는지'를 한 줄로 적어둬요. 다 풀고 나서 그 메모를 다시 보면 판단이 어디서 흔들렸는지 보여요.모의고사
유형은 알려주지 않아요. 타이머를 걸고 풀어 보세요.셀프 체크
다음 주로 넘어가기 전에 소리 내어 답해 보세요. 막히면 그 부분이 아직 덜 익은 개념이에요.- 네 문제 각각에서 어떤 도구를 왜 골랐는지 한 문장으로 말할 수 있는가?
- 7~11주 중 다시 풀었을 때 가장 막혔던 주차는 어디인가?
- 문제를 읽고 목표 복잡도를 먼저 정하는 습관이 몸에 붙었는가?