토픽 86 / 92·비교표
검색과 알고리즘 설계 기법
선형 검색 vs 이진 검색 vs 해시 검색
| 항목 | 선형 검색 | 이진 검색 | 해시 검색 |
|---|---|---|---|
| 시간 | O(n) | O(log n) | O(1) 평균 |
| 사전 조건 | 없음 | 정렬 필요 | 해시 테이블 구축 |
| 공간 | O(1) | O(1) | O(n) 추가 |
| 적용 | 소규모, 비정렬 | 정렬된 배열 | 빈번 검색 |
보간 검색 vs 이진 검색 vs 지수 검색
| 항목 | 보간 검색 | 이진 검색 | 지수 검색 |
|---|---|---|---|
| 시간 | O(log log n) 균일 | O(log n) | O(log i) |
| 조건 | 균일 분포 + 정렬 | 정렬 | 정렬 |
| 장점 | 균일 시 매우 빠름 | 범용적 | 앞쪽 원소 빠름 |
| 적용 | 균일 데이터 | 범용 | 무한/미지 크기 |
분할 정복 vs 동적 프로그래밍 vs 그리디
| 항목 | 분할 정복 | 동적 프로그래밍 | 그리디 |
|---|---|---|---|
| 부분 문제 | 독립적 | 중복 (재사용) | 없음 (순간 선택) |
| 접근 방식 | 분할→해결→결합 (재귀) | 메모이제이션/테이블링 | 지역 최적 선택 |
| 최적 보장 | 문제 의존 | 보장 (최적 부분구조) | 불보장 (탐욕 선택) |
| 시간 | 다양 | 다항 시간 | 빠름 |
| 예시 | 병합정렬, 퀵정렬 | 피보나치, 배낭, LCS | 허프만, 크루스칼 |
Top-Down vs Bottom-Up (DP)
| 비교 항목 | Top-Down (하향식/메모이제이션) | Bottom-Up (상향식/타뷸레이션) |
|---|---|---|
| 구현 방식 | 재귀 함수 + 캐시(배열/해시맵) | 반복문 + DP 테이블(배열) |
| 계산 순서 | 큰 문제 → 작은 문제 (필요할 때 계산) | 작은 문제 → 큰 문제 (순서대로 계산) |
| 부분 문제 계산 | 필요한 부분 문제만 계산 (Lazy) | 모든 부분 문제를 계산 (Eager) |
| 스택 사용 | 재귀 호출 스택 사용 → 깊이 제한, 오버플로우 위험 | 반복문만 사용 → 스택 오버플로우 없음 |
| 실행 속도 | 재귀 호출 오버헤드 있음 | 반복문으로 더 빠름 (상수 계수 작음) |
| 코드 직관성 | 점화식과 직접 대응, 이해 쉬움 | 테이블 채우기 순서 설계 필요 |
| 공간 최적화 | 어려움 (재귀 구조 제약) | 가능 (이전 행만 유지 등, 예: 피보나치 O(1) 공간) |
| 적합한 경우 | 모든 부분 문제가 필요하지 않을 때, 빠른 프로토타이핑 | 모든 부분 문제가 필요할 때, 성능 최적화 |
그리디 vs DP 상세
| 항목 | 그리디 | DP |
|---|---|---|
| 선택 | 지역 최적 (현재 최선) | 전역 최적 (모든 경우) |
| 조건 | 탐욕 선택 속성 + 최적 부분구조 | 최적 부분구조 + 중복 부분 문제 |
| 속도 | 빠름 (단일 선택) | 느림 (테이블 구축) |
| 정확도 | 최적 불보장 (문제 의존) | 최적 보장 |
| 예시 | 활동 선택, 허프만, MST | 배낭, LCS, 편집 거리 |
백트래킹 vs 브루트 포스 vs 휴리스틱
| 항목 | 백트래킹 | 브루트 포스 | 휴리스틱 |
|---|---|---|---|
| 탐색 범위 | 가지치기로 축소 | 전체 | 근사 |
| 속도 | 중간 | 매우 느림 | 매우 빠름 |
| 정확도 | 정확 | 정확 | 근사 |
| 적용 | N-Queen, 스도쿠 | 소규모 문제 | 대규모 최적화 |