알고리즘 핵심 개념 요약¶
알고리즘 문제를 풀 때 반드시 숙지해야 할 핵심 개념들을 정리했습니다.
1. 완전탐색 (Brute-Force)¶
가장 기본적이면서도 강력한 방법입니다.
- 모든 경우의 수를 다 살펴봐도 시간 초과가 나지 않을지 먼저 확인합니다.
- 가능하다면 완전탐색으로 문제를 해결합니다.
- 만약 시간 초과가 예상된다면 더 효율적인 알고리즘(Greedy, DP, Binary Search 등)을 고려해야 합니다.
2. 탐욕법 (Greedy)¶
매 순간 최적이라고 생각되는 것을 선택하는 방식입니다.
- 완전탐색이 가능한지 먼저 확인합니다.
- Greedy 접근 시 반례가 없을지 신중하게 고려해야 합니다. 증명이 중요합니다.
- 안될 것 같으면 다른 효율적인 알고리즘을 찾습니다.
3. 그래프 구현 (Graph Implementation)¶
- 인접 행렬 (Adjacency Matrix)
- 메모리 사용량이 많음 ($V^2$)
- 조회 속도가 빠름 ($O(1)$)
- 인접 리스트 (Adjacency List)
- 메모리 사용량이 적음 ($V + E$)
- 조회 속도가 상대적으로 느림 ($O(N)$)
- 간선이 적은 희소 그래프(Sparse Graph)에서 유용합니다.
4. DFS & BFS¶
모든 노드를 탐색하므로 항상 답을 찾을 수 있다는 장점이 있습니다.
| 구분 | DFS (Depth First Search) | BFS (Breadth First Search) |
|---|---|---|
| 구현 방식 | 스택(Stack) 또는 재귀함수 | 큐(Queue) |
| 특징 | 깊이 우선 탐색 | 너비 우선 탐색 |
| 유리한 경우 | 모든 경로를 탐색해야 할 때 | 최단 거리 구하기 문제 |
5. 백트래킹 (Backtracking)¶
퇴각 검색이라고도 불리며, 모든 경우를 탐색하되 불필요한 경로를 사전에 차단합니다.
- 기본적으로 DFS/BFS와 유사하게 모든 경우를 탐색합니다.
- 가지치기 (Pruning)를 통해 탐색 경우의 수를 줄이는 것이 핵심입니다.
- "가망이 없으면 더 이상 가지 않는다"는 전략으로 최악의 경우를 대비합니다.
6. 이진 탐색 (Binary Search)¶
탐색 범위를 절반씩 줄여나가며 답을 찾는 효율적인 방식입니다.
- 전제 조건: 탐색 전 데이터가 반드시 정렬되어 있어야 합니다.
- 파라메트릭 서치 (Parametric Search):
- 최적화 문제를 결정 문제(YES/NO)로 바꾸어 이진 탐색으로 푸는 기법입니다.
- 최솟값이나 최댓값을 구하는 문제에서 자주 활용됩니다.
7. 동적 계획법 (Dynamic Programming)¶
문제를 작은 문제로 쪼개어 해결하고, 그 결과를 저장하여 더 큰 문제를 푸는 방식입니다.
구현 방식¶
- Top-down (Memoization)
- 재귀 함수를 사용하며, 필요한 부분 문제만 해결합니다. (Lazy-Evaluation)
- 장점: 직관적이며 코드 가독성이 좋습니다.
- 단점: 재귀 호출 오버헤드가 발생할 수 있습니다.
- Bottom-up (Tabulation)
- 반복문을 사용하며, 부분 문제의 답을 테이블에 미리 채워 나갑니다. (Eager-Evaluation)
- 장점: 시간과 메모리 효율이 상대적으로 좋을 수 있습니다.
- 단점: 테이블을 채워 나가는 올바른 순서를 알아야 합니다.
요약¶
- 핵심: 메모이제이션(Memoization)과 점화식 정의
- 점화식을 찾고 테이블을 잘 정의하는 것이 문제 해결의 열쇠입니다.