알고리즘 관계도

mindmap
  root((알고리즘<br/>80개 토픽))
    기초 개념
      알고리즘
      시간 복잡도
      공간 복잡도
      재귀
      메모이제이션
    정렬 알고리즘
      기본 정렬
        정렬
        버블 정렬
        선택 정렬
        삽입 정렬
        셸 정렬
      고급 정렬
        병합 정렬
        퀵 정렬
        힙 정렬
        팀 정렬
      선형 시간 정렬
        계수 정렬
        기수 정렬
      정렬 이론
        안정 정렬 vs 불안정 정렬
        외부 정렬
    검색 알고리즘
      검색
      선형 검색
      이진 검색
      해시 검색
      보간 탐색
    설계 기법
      분할 정복
      동적 프로그래밍
      탐욕 알고리즘
      백트래킹
      브루트 포스
      비트마스크 DP
      그리디 vs DP 비교
    알고리즘 기법
      Two Pointers
      Sliding Window
    그래프 알고리즘
      그래프 탐색
        그래프 탐색
        DFS
        BFS
      최단 경로
        최단 경로
        Dijkstra 알고리즘
        Bellman-Ford 알고리즘
        Floyd-Warshall 알고리즘
        A* 알고리즘
      최소 스패닝 트리
        최소 스패닝 트리
        Kruskal 알고리즘
        Prim 알고리즘
      위상 정렬
      그래프 구조
        Tarjan's SCC
        이분 매칭
        헝가리안 알고리즘
      네트워크 플로우
        최대 유량
        최소 컷
        Ford-Fulkerson / Edmonds-Karp / Dinic
      트리 알고리즘
        LCA
        Heavy-Light Decomposition
    문자열 알고리즘
      문자열 매칭
        문자열 매칭
        KMP 알고리즘
        Boyer-Moore 알고리즘
        Rabin-Karp 알고리즘
        Aho-Corasick 알고리즘
      문자열 처리
        Manacher 알고리즘
        Z 알고리즘
        Suffix Array
      문자열 DP
        최장 공통 부분 수열
        편집 거리
        LIS
    고급 자료구조 알고리즘
      Segment Tree
      Fenwick Tree
      Trie
      Union-Find
    기하 알고리즘
      Convex Hull
    수학/변환
      FFT
      허프만 코딩
    특수 알고리즘
      Mo's Algorithm
    복잡도 이론
      NP 완전
      P vs NP 문제
    고급 알고리즘 이론
      근사 알고리즘
      온라인 알고리즘
      병렬 알고리즘
    메타휴리스틱
      메타휴리스틱
      유전 알고리즘
      시뮬레이티드 어닐링
    응용 수학
      대기행렬 이론

O(n²) - 기본
  ├─ 버블 정렬
  ├─ 선택 정렬
  ├─ 삽입 정렬 (거의 정렬된 데이터에 효율적)
  └─ 셸 정렬 (삽입 정렬 개선, 간격 기반)

O(n log n) - 고급
  ├─ 병합 정렬 (안정, 추가 메모리)
  ├─ 퀵 정렬 (평균 빠름, 최악 O(n²))
  ├─ 힙 정렬 (제자리, 비안정)
  └─ 팀 정렬 (병합+삽입, 실전 최적화, Python/Java 기본)

O(n) - 특수 조건
  ├─ 계수 정렬 (정수, 범위 제한)
  └─ 기수 정렬 (자릿수 기반)

특수 정렬
  └─ 외부 정렬 (메모리 초과 데이터, 다단계 병합)

분할 정복 (Divide & Conquer)
  ├─ 병합 정렬
  ├─ 퀵 정렬
  └─ 이진 검색

동적 프로그래밍 (DP)
  ├─ LCS
  ├─ 편집 거리
  ├─ LIS
  ├─ 배낭 문제
  ├─ 비트마스크 DP (상태 압축)
  └─ 메모이제이션 (Top-Down DP)

탐욕 알고리즘 (Greedy)
  ├─ Dijkstra
  ├─ Prim
  ├─ Kruskal
  └─ 허프만 코딩

백트래킹
  ├─ N-Queens
  └─ 순열/조합

그리디 vs DP 비교
  ├─ 최적 부분 구조 (공통)
  ├─ 탐욕 선택 속성 (Greedy만)
  └─ 중복 부분 문제 (DP만)

DFS 응용
  ├─ 사이클 탐지
  ├─ 위상 정렬
  ├─ Tarjan's SCC
  └─ 이분 매칭

BFS 응용
  ├─ 최단 경로 (무가중치)
  └─ 레벨 순회

단일 시작점 (Single Source)
  ├─ Dijkstra (음수 간선 없음, 그리디)
  └─ Bellman-Ford (음수 간선 허용, DP)

모든 쌍 (All Pairs)
  └─ Floyd-Warshall (DP, O(V³))

휴리스틱
  └─ A* (목표 지향, h(n) 함수)

간선 중심
  └─ Kruskal (Union-Find, 간선 정렬)

정점 중심
  └─ Prim (우선순위 큐, Dijkstra와 유사)

최대 유량 (Max Flow)
  ├─ Ford-Fulkerson (기본, DFS 기반)
  ├─ Edmonds-Karp (BFS 기반, O(VE²))
  └─ Dinic (레벨 그래프, O(V²E))

최대유량-최소컷 정리
  ├─ 최대 유량 = 최소 컷
  └─ 이분 매칭과 연결 (쾨닉 정리)

매칭
  ├─ 이분 매칭 (호프크로프트-카프)
  └─ 헝가리안 알고리즘 (최소 비용 할당)

단순 매칭
  └─ 브루트 포스 O(nm)

전처리 기반
  ├─ KMP (패턴 전처리, O(n+m))
  ├─ Boyer-Moore (역방향, 실전 빠름)
  └─ Rabin-Karp (해시, 다중 패턴)

다중 패턴
  └─ Aho-Corasick (트라이 + KMP, 여러 패턴)

회문/반복
  ├─ Manacher (최장 회문)
  └─ Z 알고리즘 (접두사 매칭)

접미사 기반
  └─ Suffix Array (모든 부분 문자열)

Segment Tree
  ├─ 구간 합/최소/최대
  ├─ 레이지 업데이트
  └─ O(log n) 쿼리/업데이트

Fenwick Tree (BIT)
  ├─ 누적 합
  ├─ 메모리 효율적
  └─ O(log n) 쿼리/업데이트

순차 검색
  └─ 선형 검색 O(n)

분할 기반
  ├─ 이진 검색 O(log n) - 정렬 필수
  └─ 보간 탐색 O(log log n) - 균등 분포 시

해시 기반
  └─ 해시 검색 O(1) 평균 - 해시 충돌 처리

메타휴리스틱
  ├─ 유전 알고리즘 (진화 기반)
  ├─ 시뮬레이티드 어닐링 (물리 기반)
  └─ NP-Hard 문제의 근사 해

근사 알고리즘
  ├─ 다항 시간 보장
  └─ 근사 비율 분석

온라인 알고리즘
  ├─ 미래 입력 모름
  └─ 경쟁 비율 (Competitive Ratio)

Two Pointers
  ├─ 정렬된 배열에서 쌍 찾기
  ├─ 부분 배열 합
  └─ O(n) 선형 시간

Sliding Window
  ├─ 고정/가변 크기 윈도우
  ├─ 부분 문자열/배열 최적화
  └─ Two Pointers의 특수한 형태