질문 순서
- 정렬되어 있나? / 정렬해도 되나? (인덱스 손상 주의)
- “이전 값과 비교”인가? → 스택·모노톤
- “본 적 있나?” → 해시 Set/Map
- “구간·합·연속” → 투포인터·누적합·슬라이딩
- “최적 부분 구조 + 겹치는 부분” → DP
- “연결·최단” → BFS/DFS
빠른 매칭 표
| 느낌 | 후보 |
|---|---|
| 페어 합, 빈도 | Map |
| 회문, 정렬 배열 두 합 | 투포인터 |
| 괄호, next greater | 스택 |
| 연속 부분 최적 | 카데인·슬라이딩·DP |
| 격자 덩어리 | DFS/BFS |
틀렸을 때
패턴을 바꾸기 전에 파싱·경계를 먼저 의심하세요.
패턴이 틀린 경우는 추적표가 예제부터 안 맞을 때입니다.
연습
문제를 풀기 전에 주석 한 줄:
// pattern: hash · n=1e5통과 후 실제로 쓴 패턴과 같았는지 비교하면 감이 쌓입니다.
질문 순서 (확장)
- 정렬되어 있나? / 정렬해도 되나? (인덱스 필요하면 인덱스 쌍을 같이 정렬)
- “이전 값과 비교”인가? → 스택·모노톤
- “본 적 있나?” → 해시 Set/Map
- “구간·합·연속” → 투포인터·누적합·슬라이딩
- “최적 + 겹치는 부분문제” → DP
- “연결·최단(가중치 0)” → BFS
- “모든 순열·부분집합” + n≤20 → 비트마스크·백트래킹
빠른 매칭 표
| 느낌 | 후보 |
|---|---|
| 페어 합, 빈도 | Map |
| 회문, 정렬 배열 두 합 | 투포인터 |
| 괄호, next greater | 스택 |
| 연속 부분 최적 | 카데인·슬라이딩·DP |
| 격자 덩어리 | DFS/BFS |
| 구간 합 질의 다수 | 누적합 |
틀렸을 때
패턴을 바꾸기 전에 파싱·경계를 먼저 의심하세요.
패턴이 틀린 경우는 추적표가 예제부터 안 맞을 때입니다.
연습
문제를 풀기 전에 주석 한 줄:
// pattern: hash · n=1e5통과 후 실제로 쓴 패턴과 같았는지 비교하면 감이 쌓입니다.