알고리즘

알고리즘(Algorithm)은 주어진 문제를 해결하기 위한 단계별 절차다. 어떤 알고리즘을 선택하느냐가 코드의 정확성과 성능을 결정하며, 컴퓨터 과학 전반의 핵심 역량이다.

알고리즘 복잡도

모든 알고리즘은 시간복잡도와 공간복잡도로 효율성을 평가한다.

O(1)        상수 시간  — 해시 테이블 조회, 배열 인덱스 접근
O(log n)    로그 시간  — 이진 탐색, 힙 삽입
O(n)        선형 시간  — 배열 순회, BFS/DFS
O(n log n)  선형로그   — 병합 정렬, 힙 정렬
O(n²)       이차 시간  — 버블 정렬, 단순 DP
O(2ⁿ)       지수 시간  — 부분집합 탐색, 백트래킹

분야별 구성

탐색과 정렬

그래프 알고리즘

동적 프로그래밍 (DP)

문자열 알고리즘

• •KMP: 패턴 매칭 O(n+m) — 접두사 함수 활용
• •라빈-카프: 해시 기반 패턴 매칭
• •Aho-Corasick: 다중 패턴 매칭 (KMP의 일반화)
• •접미사 배열(SA): 모든 부분 문자열 탐색
• •접미사 자동자(SAM): 부분 문자열 카운팅·최장 공통 부분 문자열

수학 알고리즘

고급 알고리즘

• •Heavy-Light Decomposition(HLD): 트리 경로 쿼리 O(log² n)
• •센트로이드 분할: 트리 거리 관련 문제 O(n log n)
• •Mo's 알고리즘: 오프라인 구간 쿼리 O((n+q)√n)
• •제곱근 분할(Sqrt Decomposition): 구간 연산 O(√n)
• •2-SAT: 2-리터럴 논리 만족성 문제 O(V+E)
• •DSU on Tree: 트리 위 서브트리 쿼리 O(n log n)
• •볼록 껍질(Convex Hull): 점들의 최외곽 다각형 O(n log n)

알고리즘 설계 패러다임

이론 컴퓨터 과학

• •P vs NP 문제: 다항 시간에 검증 가능한 문제가 다항 시간에 풀 수 있는가?
• •복잡도 클래스: P·NP·NP-완전·NP-하드·PSPACE의 구조
• •상각 분석: 연속 연산의 평균 비용 분석 (Union-Find, 동적 배열)
• •정보 이론: 엔트로피·최적 부호화·채널 용량

알고리즘 학습 로드맵

입문    → 정렬·이진 탐색·BFS/DFS·해시맵
기본    → 그리디·DP·그래프 (다익스트라·MST·위상 정렬)
중급    → 문자열 (KMP·트라이)·트리 (LCA·세그먼트 트리)·비트마스크 DP
고급    → 네트워크 플로우·SCC·FFT·고급 트리 분할·문자열 자동자
심화    → 복잡도 이론·근사 알고리즘·랜덤화·병렬 알고리즘