토픽 84 / 92·비교표
알고리즘 기초와 복잡도
재귀 vs 반복 vs 꼬리 재귀
| 항목 | 재귀 | 반복 | 꼬리 재귀 |
|---|---|---|---|
| 구현 | 간결 | 복잡 | 간결 |
| 스택 | 깊이 비례 (오버플로 위험) | 없음 (안전) | 최적화 시 O(1) |
| 적용 | 트리 순회, 분할정복 | 반복 작업 | 함수형 언어 |
메모이제이션 vs 테이블링
| 항목 | 메모이제이션 (Top-Down) | 테이블링 (Bottom-Up) |
|---|---|---|
| 방식 | 재귀 + 캐시 | 반복문 + 테이블 |
| 계산 범위 | 필요한 부분만 | 모든 하위 문제 |
| 공간 | 스택 + 캐시 | 테이블만 |
| 적용 | 희소 부분 문제 | 밀집 부분 문제 |