문제 신호 → 알고리즘 매핑
Summary
문제를 읽고 “어떤 템플릿을 꺼낼지” 결정하는 표다.
한 문제에 신호가 여러 개 보이면제약조건 → 그래프/배열/문자열 형태 → 최적화 여부순서로 좁힌다.
제약조건 신호
| 문제 신호 | 먼저 의심 | 대표 복잡도 |
|---|---|---|
N <= 10, 모든 순서 | 순열, 백트래킹 | O(N!) |
N <= 20, 선택/미선택 | 부분집합, 비트마스크 | O(2^N) |
N <= 30, 경우의 수가 큼 | Meet-in-the-middle, 조합 DP | O(2^(N/2)) 후보 |
N <= 500, 모든 쌍 | Floyd, 3중 for DP | O(N^3) |
N <= 2,000 | 2중 for, LIS O(N²), DP | O(N^2) |
N <= 100,000 | 정렬, 이분탐색, 해시, PQ | O(N log N) 이하 |
N <= 1,000,000 | 누적합, BFS/DFS, 투포인터 | O(N) 중심 |
격자 N*M <= 1,000,000 | BFS/DFS/시뮬레이션 | O(NM) |
정점 V, 간선 E | 그래프 탐색/최단경로 | O(V+E) 또는 O(E log V) |
표현 신호
| 문제 표현 | 알고리즘/자료구조 | 대표 문서 |
|---|---|---|
| 최소 이동 횟수, 가중치 없음 | BFS | 알고리즘/03. BFS-DFS.md |
| 격자에서 몇 칸 만에 도착 | BFS | 알고리즘/03. BFS-DFS.md |
| 갈 수 있는 영역 개수 | BFS/DFS | 알고리즘/03. BFS-DFS.md |
| 모든 경우를 시도 | DFS/백트래킹 | 알고리즘/02. 완전탐색-백트래킹.md |
| 순서가 중요 | 순열 | 알고리즘/02. 완전탐색-백트래킹.md |
| 순서가 중요하지 않음 | 조합 | 알고리즘/02. 완전탐색-백트래킹.md |
| 선택한다/안 한다 | 부분집합, 비트마스크 | 알고리즘/02. 완전탐색-백트래킹.md |
| 연속 구간 + 모든 수 양수 | 투포인터 | 알고리즘/05. 투포인터-누적합.md |
| 연속 구간 + 음수 포함 | 누적합 + HashMap | 알고리즘/05. 투포인터-누적합.md |
| 구간합 질의 많음 | 누적합 | 알고리즘/05. 투포인터-누적합.md |
| 값 변경 + 구간 질의 | Fenwick, Segment Tree | 알고리즘/12. 세그먼트트리-Fenwick.md |
| 가능한 최대/최소 답 찾기 | 매개변수 탐색 | 알고리즘/04. 이분탐색-매개변수탐색.md |
| 최단거리 + 음수 없음 | Dijkstra | 알고리즘/07. 그래프-최단경로.md |
| 간선 비용 0 또는 1 | 0-1 BFS | 알고리즘/07. 그래프-최단경로.md |
| 음수 간선 있음 | Bellman-Ford | 알고리즘/07. 그래프-최단경로.md |
| 모든 정점 쌍 최단거리 | Floyd-Warshall | 알고리즘/07. 그래프-최단경로.md |
| 모든 정점을 최소 비용 연결 | MST, Kruskal | 알고리즘/08. 그래프-MST-UnionFind.md |
| 그룹 합치기, 같은 그룹 확인 | Union-Find | 알고리즘/08. 그래프-MST-UnionFind.md |
| 선수과목, 작업 순서 | 위상정렬 | 알고리즘/09. 그래프-위상정렬.md |
| 계속 최솟값/최댓값 꺼내기 | PriorityQueue | 알고리즘/10. 자료구조-PriorityQueue.md |
| 트리의 가장 먼 거리 | 트리 지름 | 알고리즘/11. 트리.md |
| 접두사, 자동완성, 사전 검색 | Trie | 알고리즘/13. 문자열-Trie.md |
| 괄호 짝, 직전 값 비교, 인접 제거 | Stack | 알고리즘/14. 스택-괄호.md |
| 윈도우 최댓값/최솟값 | Deque + 인덱스 | 알고리즘/16. 자료구조-Stack-Queue-Deque.md |
| 정렬 후 최적 선택 | Greedy | 알고리즘/15. 그리디.md |
Java 자료구조 신호
| 상황 | 선택 | 금지/주의 |
|---|---|---|
| BFS 일반 큐 | Queue<T> q = new ArrayDeque<>(); | 큐처럼 쓰면서 push() 금지 |
| 스택 문제 | Deque<T> st = new ArrayDeque<>(); + push/pop/peek | Stack 클래스 지양 |
| 양쪽 조작 | Deque<T> dq = new ArrayDeque<>(); + offerFirst/offerLast | 방향 없는 push/offer 혼용 금지 |
| 중복 제거 + 순서 유지 | LinkedHashSet 또는 Deque + 마지막 값 변수 | HashSet 순서 보장 X |
| 정렬 기준 있는 힙 | PriorityQueue<>(Comparator) | a - b Comparator 금지 |
| 큰 수 산술 | BigInteger | +, * 연산자 사용 불가 |
위험 신호
| 신호 | 확인 |
|---|---|
| 비용 합, 거리 합 | int 대신 long 필요 여부 |
| 경우의 수 | mod 연산 여부, long 초과 여부 |
재귀 깊이 100,000 | StackOverflow 위험. 반복 DFS/BFS 고려 |
| 중복 간선 | 최소 비용만 유지할지 확인 |
| 시작 == 도착 | 초기값으로 답이 바로 나오는지 확인 |
| 도달 불가능 | INF 출력 규칙 확인 |
| 정렬 Comparator | a - b 금지, Integer.compare() 사용 |
| Deque를 배열로 변환 | 현재 앞 → 뒤 순서. push()로 넣은 스택은 삽입 역순 |
ArrayDeque에 null 삽입 | 불가능. poll() 결과 null 언박싱 NPE 주의 |