토픽 88 / 92·비교표
문자열, 압축, 복잡도 이론
KMP vs Boyer-Moore vs Rabin-Karp vs Aho-Corasick
| 항목 | KMP | Boyer-Moore | Rabin-Karp | Aho-Corasick |
|---|
| 시간 | O(n+m) 보장 | 평균 O(n/m) | O(n+m) 평균 | O(n+m+z) |
| 비교 방향 | 왼→오 | 오→왼 | 해시 비교 | 트라이 기반 |
| 다중 패턴 | X | X | O | O (최적) |
| 장점 | 최악 보장 | 실제 빠름 | 다중 패턴 | 다중 패턴 선형 |
| 적용 | 단일 패턴 검색 | 텍스트 에디터 | 표절 검사 | 바이러스 스캔 |
LCS vs 최장 공통 부분 문자열
| 항목 | LCS (부분수열) | 최장 공통 부분 문자열 |
|---|
| 연속성 | 불연속 (순서만 유지) | 연속 |
| 시간 | O(mn) | O(mn) |
| 적용 | diff 알고리즘, DNA 비교 | 문자열 유사도 |
편집 거리 vs Hamming 거리
| 항목 | 편집 거리 (Levenshtein) | Hamming 거리 |
|---|
| 연산 | 삽입/삭제/치환 3가지 | 치환만 |
| 길이 제약 | 다른 길이 가능 | 같은 길이 필수 |
| 시간 | O(mn) | O(n) |
| 적용 | 맞춤법 교정, 유사도 | 오류 검출, 코딩 이론 |
허프만 vs LZW vs RLE
| 항목 | 허프만 | LZW | RLE |
|---|
| 방식 | 빈도 기반 가변 코드 | 사전 기반 | 연속 반복 압축 |
| 유형 | 무손실/최적 접두사 | 무손실/적응형 | 무손실/단순 |
| 적용 | ZIP, JPEG 내부 | GIF, TIFF | BMP, 팩스 |
P vs NP vs NP-Complete vs NP-Hard
| 항목 | P | NP | NP-Complete | NP-Hard |
|---|
| 정의 | 다항 시간 해결 | 다항 시간 검증 | NP 중 가장 어려움 | 최소 NP만큼 어려움 |
| 해결 시간 | 다항 (효율적) | 불명 (검증만 다항) | 불명 | 불명 |
| 검증 시간 | 다항 | 다항 | 다항 | 조건 없음 |
| 예시 | 정렬, 최단경로 | 해밀턴 경로 | SAT, TSP(결정), 3-색칠 | TSP(최적화), 정지 문제 |