[Algorithm] 코딩테스트 알고리즘 선택방법 요약
in Algorithm
코딩테스트 알고리즘 선택 방법에 대해 정리해보았습니다.
코딩테스트에서 어떤 알고리즘을 선택해야 할지 고민될 때가 많다. 이 글에서는 코테 기준으로 딱 필요한 만큼만 정리한다.
1️⃣ 문제를 읽자마자 던질 5가지 질문
| 순서 | 스스로에게 묻는 질문 | YES면 |
|---|---|---|
| Q1 | 최단 거리 / 최소 횟수인가? | 👉 아래 Q2 |
| Q2 | 모든 간선 가중치가 같은가? | 👉 BFS |
| Q3 | 가중치가 다르지만 음수는 없는가? | 👉 다익스트라 |
| Q4 | 모든 쌍 (i, j) 최단거리인가? | 👉 플로이드-워셜 |
| Q5 | 트리(사이클 없음)인가? | 👉 DFS / 트리 DP |
2️⃣ BFS / DFS / 다익스트라 / 플로이드 비교표
| 구분 | BFS | DFS | 다익스트라 | 플로이드 |
|---|---|---|---|---|
| 목적 | 최단 거리(가중치=1) | 탐색/구조 | 최단 거리(가중치≠1) | 모든 쌍 최단 |
| 자료구조 | Queue | 재귀 / Stack | PriorityQueue | 2차원 배열 |
| 시간복잡도 | O(N+M) | O(N+M) | O((N+M)logN) | O(N³) |
| 거리 배열 | O | △ | O | O |
| visited | O | O | △ | X |
| 대표 문제 | 미로, 숨바꼭질 | 트리 지름 | 최단 비용 | 플로이드 |
3️⃣ “가중치”로 바로 고르는 공식 (암기용)
최단 거리 + 가중치 = 1 → BFS
최단 거리 + 가중치 다름 → 다익스트라
모든 쌍 최단 거리 → 플로이드
4️⃣ “트리”가 나오면 이렇게 생각하자
| 문제 키워드 | 거의 정답 |
|---|---|
| 트리 / 부모 / 자식 | DFS |
| 가장 긴 경로 | 트리 지름 |
| 서브트리 | 트리 DP |
| 루트가 있음 | DFS |
| 간선 = 노드 - 1 | 트리 |
👉 트리 = DFS 기본값
5️⃣ 인접 리스트 vs 인접 행렬 선택표
| 상황 | 선택 |
|---|---|
| N ≥ 1,000 | 인접 리스트 |
| BFS / DFS / 다익스트라 | 인접 리스트 |
| 플로이드-워셜 | 인접 행렬 |
| 메모리 제한 빡빡 | 인접 리스트 |
코테 기본값
List<int[]>[] graph;
6️⃣ 문제 문장 → 알고리즘 자동 변환 예시
| 문제 문장 | 바로 떠올릴 것 |
|---|---|
| “최소 몇 번 만에” | BFS |
| “최소 비용” | 다익스트라 |
| “모든 도시 쌍” | 플로이드 |
| “가장 긴 경로” | 트리 지름 |
| “연결되어 있는가” | DFS/BFS |
| “K 거리인 노드” | BFS |
7️⃣ 실전에서 쓰는 판별 한 줄 공식
최단 거리인가?
→ 가중치가 전부 1인가?
→ YES: BFS
→ NO : 다익스트라
트리인가?
→ DFS / 트리 DP
8️⃣ 너가 자주 헷갈리던 문제들, 정답 알고리즘
| 문제 | 정답 알고리즘 |
|---|---|
| 특정 거리의 도시 찾기 | BFS |
| 숨바꼭질 | BFS |
| 트리의 지름 | DFS (2번 or DP) |
| 거짓말 | DSU / BFS |
| 치킨 배달 | 조합 + 거리 계산 |
| 플로이드 | 플로이드-워셜 |
🎯 최종 요약 (이 문장만 외워도 됨)
“알고리즘은 외우는 게 아니라, 문제 조건으로 제거하고 남는 하나를 고르는 것”
