Graph, String & Optimization

1. Overview

그래프, 문자열 및 최적화(Graph, String & Optimization, GSO)는 데이터를 선형으로 줄 세우거나 계층으로 쌓는 것을 넘어, 현대 사회의 내비게이션 경로, 소셜 네트워크의 복잡한 연결망, 그리고 게놈 프로젝트의 방대한 비정형 텍스트를 컴퓨터가 가장 효율적으로 처리할 수 있도록 추상화하는 고수준의 알고리즘을 다룹니다.

그래프 이론을 통해 점(Vertex)과 선(Edge)으로 이루어진 모델에서 최단 경로(Dijkstra)나 최소 비용의 통신망(MST)을 도출하며, 네트워크 유량(Flow) 알고리즘으로 시스템의 물리적 최대 처리량을 규명합니다. 또한 수백만 줄의 문자열 속에서 원하는 키워드를 단숨에 찾아내는 KMP 및 Aho-Corasick 알고리즘의 유한 상태 기계(Automata) 역학을 학습합니다. 최종적으로는 컴퓨터로도 우주의 수명 내에 완벽하게 풀 수 없는 난제들의 경계(P vs NP 클래스)를 파악하고, 불가능을 근사해 내는 실무 엔지니어로서의 한계 인식과 타협의 철학을 마스터합니다.

2. Scope & Boundaries

In-Scope

• 그래프 기초와 탐색 물리 (Graph Fundamentals): 정점(Vertex)/간선(Edge)의 인접 행렬 vs 리스트 기반 메모리 매핑, BFS/DFS 알고리즘, 사이클 판별, 위상 정렬(Topological Sort).
• 가중치 그래프 최적화 (Weighted Graph Logic): 최단 경로 알고리즘(Dijkstra, Bellman-Ford, Floyd-Warshall), 최소 신장 트리(MST - Kruskal, Prim).
• 고급 문자열 검색 역학 (String Mechanics): 라빈-카프(Rabin-Karp)의 롤링 해시(Rolling Hash), KMP(Knuth-Morris-Pratt)의 실패 함수 피드백, 다중 패턴 동시 검색용 Aho-Corasick 트라이 구조.
• 네트워크 유량 (Network Flow): 최대 유량 최소 컷(Max Flow Min Cut) 정리, 포드-풀커슨(Ford-Fulkerson) 및 에드몬드-카프(Edmonds-Karp) 파이프라인.
• 복잡도 한계 (Complexity Theory): 계산 불가능성 문제(Halting Problem), 다항 시간 환산(Reduction), P / NP / NP-완전(NP-Complete) / NP-난해(NP-Hard) 클래스.

Out-of-Scope

• 대규모 분산 그래프 데이터베이스 (Graph DB): Neo4j나 하둡 환경(GraphX)에서의 노드 분산 쿼리 및 파티셔닝 전략 → 06. Data Management 영역으로 위임.
• 인공지능 자연어 언어 모델 (NLP): LLM 텍스트 임베딩, 트랜스포머의 어텐션 메커니즘을 이용한 문맥 파악 등 기계학습 모델 → 11. Machine Learning 영역으로 위임.
• 순수 정보 이론 알고리즘: 채널 코딩, 에러 정정 부호(ECC), 섀넌 엔트로피 한계 분석 → 통신 공학 및 정보 이론 영역으로 위임.

Boundaries

• GSO vs. Design Techniques (04-03): ADT(04-03)가 탐욕법이나 동적 계획법이라는 범용적인 '생각의 도구'라면, GSO는 그 도구를 '그래프(도로망)'나 '문자열(DNA 염기서열)'이라는 매우 구체적이고 까다로운 특수 데이터 구조에 적용한 '실전 심화판'입니다.

3. Counterexample

• 음수 간선에 대한 무지 (Dijkstra Fallacy): 가중치가 있는 모든 그래프 문제에 다익스트라(Dijkstra) 알고리즘만을 만능키처럼 적용하는 오류. 다익스트라는 **'방문할수록 경로 비용은 절대 줄어들지 않는다'**는 전제 하에 작동하는 탐욕 알고리즘이므로, 과거로 돌아가는 타임머신이나 손실을 복구하는 이익 구간(음수 가중치 간선)이 섞여 있을 경우 탐색 논리가 완전히 무너집니다. 이럴 때는 전체 간선을 V-1번 반복하여 업데이트하는 벨만-포드(Bellman-Ford) 릴레이션 방식을 채택해야만 합니다.
• 문자열 단순 비교($O(NM)$)의 함정: 수백만 자의 텍스트에서 10자짜리 키워드를 찾기 위해, 1칸씩 문자를 옮기며 이중 for문을 돌리는 순진무구한 브루트 포스(Brute Force). 데이터가 AAAAAAAB 처럼 극단적으로 반복될 경우 최악의 시간 폭발이 일어납니다. KMP 알고리즘이 문자열 접두사-접미사 테이블을 미리 구축해 두어 한 번 스캔한 문자는 두 번 다시 되돌아보지 않는(백트래킹 없는 $O(N)$ 전진) 오토마타 구조를 완벽하게 설계해야 합니다.

4. Prerequisites

• 알고리즘 설계 기법 (Basic): 동적 계획법(Floyd-Warshall)과 탐욕법(Dijkstra, Kruskal)이 그래프 문제의 근간을 이루므로 선수 학습이 필수입니다. (04-03. ADT)
• 핵심 자료 구조 (Basic): 다익스트라 최적화에 필요한 힙(Heap, 우선순위 큐)과 위상 정렬에 쓰이는 스택/큐, 크루스칼을 구현할 분리 집합(Disjoint Set / Union-Find)에 대한 이해가 선행되어야 합니다. (04-02. CDS)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 그래프 메모리 모델링과 위상 정렬 (Graph Models & Sort)

• Why to Learn: 대학교 선수 과목 요건이나 스타크래프트 테크 트리처럼 '방향성이 있고 순서가 엄격한 종속성 관계'를 메모리에 그려내어 모순 없이 실행하기 위함입니다.
• What to Learn:
  • Concepts: 무방향/방향 그래프, 진입/진출 차수(In-degree, Out-degree), 이분 그래프(Bipartite Graph), DAG(Directed Acyclic Graph).
  • Skills: 인접 행렬(Adjacency Matrix, $O(V^2)$ 공간) vs 인접 리스트(Adjacency List, $O(V+E)$ 공간)의 물리적 장단점 평가, 위상 정렬(Topological Sort)의 큐(Queue) 릴레이션 과정.
  • Tools: 그래프 시각화 유틸리티(Graphviz).
  • Trade-offs: 페이스북 친구 관계처럼 서로 듬성듬성 아는 희소(Sparse) 그래프에서는 인접 리스트가 메모리를 아끼지만 특정 간선의 존재 여부 확인이 $O(V)$로 느림 vs 모든 도시가 거미줄처럼 촘촘히 이어진 밀집(Dense) 그래프에서는 인접 행렬이 $O(1)$ 즉시 조회를 보장하는 딜레마.
• How to Learn:
  • 1단계: 1만 명의 사용자 노드를 인접 행렬로 잡을 때 빈 0으로 가득 찬 메모리가 100MB를 넘어가 터져버리는 희소 그래프의 비효율성을 수치로 증명합니다.
  • 2단계: 큐를 이용해 In-degree가 0인 노드를 계속 빼내면서 간선을 자르는 과정을 시뮬레이션하여, 만약 큐가 비었는데 남은 노드가 있다면 닭과 달걀 같은 '순환 모순(Cycle)'이 발생했음을 파악합니다.
• Implement: $N$개의 소프트웨어 빌드 종속성(A 라이브러리는 B가 먼저 깔려야 함) 텍스트 파일이 주어졌을 때, 충돌 없는 빌드 순서를 출력하는 위상 정렬 스크립트 작성.

Recommended

Core Topic 02: 가중치 그래프의 최적 경로와 신장 트리 (Weighted Graphs & Paths)

• Why to Learn: 단순히 '연결'된 것을 넘어, 그 길을 건너갈 때 소모되는 통행료, 지연 시간, 기름값 등의 물리적 페이로드(Weight)를 최소화하는 절대 해답을 구하기 위해서입니다.
• What to Learn:
  • Concepts: 릴레이션(Relaxation), 탐욕적 접근, 다이나믹 프로그래밍.
  • Skills: 최단 경로(Dijkstra, Bellman-Ford, Floyd-Warshall의 3중 for문), 최소 신장 트리(MST: 크루스칼 간선 정렬 로직, 프림의 정점 확장 물리).
  • Tools: 우선순위 큐 힙 매핑, 분리 집합(Union-Find) 트리 포인터 단축 기법.
  • Trade-offs: 하나의 시작점에서 모든 목적지를 구하는 다익스트라 알고리즘($O(E \log V)$) vs 모든 지점에서 모든 지점의 거리를 한 번에 도출해 내지만 시간 복잡도가 $O(V^3)$으로 폭발하는 플로이드-워셜의 스케일 차이.
• How to Learn:
  • 1단계: 임의의 점 5개에 음수 가중치 -10을 하나 섞어 그래프를 그리고, 다익스트라 알고리즘이 "이미 확정된 노드는 다시 보지 않는다"는 오만에 빠져 최단 거리를 틀려버리는 경로를 추적합니다.
  • 2단계: Union-Find(서로소 집합)를 사용해 크루스칼 알고리즘이 가장 싼 간선을 계속 고르더라도 사이클(Cycle)이 형성되는 것을 회피하는 물리적 Find 루트 포인터 탐색 과정을 도식화합니다.
• Implement: 서울 시내 지하철 노드 데이터와 역간 소요 시간을 입력받아, 가장 빠른 시간 내에 도착역을 계산하되 힙(우선순위 큐)으로 $O(E \log V)$ 속도를 뽑아내는 다익스트라 엔진.

Practical

Core Topic 03: 고급 문자열 스캐닝 오토마타 (String Mechanics)

• Why to Learn: 10기가바이트짜리 서버 로그 텍스트 더미 속에서 "Exception"이라는 단어를 찾을 때, 일반적인 비교법으로 서버 CPU를 터뜨리지 않고 눈 깜짝할 새 스캔하기 위함입니다.
• What to Learn:
  • Concepts: 접두사(Prefix)와 접미사(Suffix) 일치 테이블, 롤링 해시(Rolling Hash), 트라이(Trie), 유한 상태 오토마타(FSA).
  • Skills: 라빈-카프(Rabin-Karp)의 모듈로 산술 윈도우 해시 이동, KMP(Knuth-Morris-Pratt) 실패 함수(Pi 배열) 구축, Aho-Corasick 다중 패턴 탐색.
  • Tools: 문자열 알고리즘 분석기.
  • Trade-offs: 단일 검색어에 극한으로 최적화된 KMP의 빠른 단발 스피드 vs 백신 프로그램처럼 10,000개의 바이러스 시그니처를 '동시에' 검색해야 할 때 한 번의 텍스트 훑기로 1만 개를 다 잡아내는 Aho-Corasick 오토마타 트리의 극악한 초기 메모리 구축 비용.
• How to Learn:
  • 1단계: 라빈-카프 알고리즘에서 "ABC"를 검사한 뒤 한 칸 옮겨 "BCD"를 검사할 때, 문자를 일일이 다시 계산하지 않고 'A'를 빼고 'D'만 더하는 수학적 창문(Sliding Window) 롤링 해시 기법을 수식화합니다.
  • 2단계: KMP 알고리즘의 본질인 $Pi$ 배열($Pi[i]$: 길이 $i$인 부분 문자열 중 접두사와 접미사가 일치하는 최대 길이)을 'ABACABA' 문자열에 대해 손으로 직접 계산하여 배열 칸을 채웁니다.
• Implement: 특정 악성코드 바이트 시그니처 배열(수백 개)을 Trie 자료 구조에 올려 실패(Fail) 링크를 연결한 뒤, 덤프 파일을 1회 스트리밍하며 모든 시그니처를 잡아내는 Aho-Corasick C++ 모델 구현.

Advanced

Core Topic 04: 한계 인식을 위한 네트워크 유량과 P/NP (Complexity & Flow)

• Why to Learn: 파이프라인의 병목을 찾아 시스템 전체의 물리적 처리량 한계를 뚫어내고, 동시에 현존하는 컴퓨터로는 절대로 최적해를 단시간에 구할 수 없는 난제들을 식별하여 프로젝트의 매몰 비용(삽질)을 막기 위해서입니다.
• What to Learn:
  • Concepts: 용량(Capacity)과 유량(Flow), 잔여 네트워크(Residual Network), P / NP / NP-Hard / NP-Complete 클래스 정리.
  • Skills: 에드몬드-카프(Edmonds-Karp) 최대 유량 알고리즘, 이분 매칭(Bipartite Matching) 응용, NP 문제의 근사(Approximation) 및 휴리스틱 해법.
  • Tools: 다항 시간 환산(Polynomial Time Reduction) 논리 전개.
  • Trade-offs: 최적의 유량을 보내는 경로를 찾았음에도 불구하고 그보다 더 나은 경로 조합이 숨어 있을 때, 가상의 '역방향 간선'을 뚫어 이전에 보낸 유량을 취소(환불)함으로써 전역 최대 유량에 도달하는 포드-풀커슨(Ford-Fulkerson)의 경이로운 수학적 기만술.
• How to Learn:
  • 1단계: 정수기 필터들을 잇는 파이프 네트워크를 그리고, 물을 최대로 흘려보내는 유량 계산 과정과 그 물줄기를 완전히 끊어버리기 위해 가위로 파이프를 자를 때 최소 비용을 구하는 'Max-Flow Min-Cut' 정리가 동일한 거울임을 직관합니다.
  • 2단계: 배달의 민족(라우팅)에서 $N$개의 중국집 배달 경로 최단 거리를 찾는 외판원 순회 문제(TSP)가 왜 $O(N!)$로 폭발하는지 그려보고, 이 NP-Hard 문제에 다익스트라를 돌리려고 시도하는 주니어를 논리적으로 만류하는 상황극을 짭니다.
• Implement: 남녀 미팅 배정, 혹은 작업자 100명과 서버 100대를 각자의 호환성 조건에 맞춰 가장 많이(최대 유량) 짝지어주는 이분 매칭(Bipartite Matching) 헝가리안 또는 네트워크 플로우 로직 시뮬레이터.

7. Terminology

8. References

Primary References

• [P1] CS2023 - AL/Advanced & Specialized Algorithms — Graphs and strings.
• [P4] DS-BoK - Data Infrastructure — Graphs for data science.

Secondary References

• [Algorithms on Strings, Trees, and Sequences] Dan Gusfield — String authority.
• [Introduction to Algorithms (CLRS)] Cormen et al. — Comprehensive graph section.

Industry References

• [Google Maps Routing Internals - Blog] — Real-world graph applications.
• [Elasticsearch/Lucene String Storage Mechanics] — Industrial-scale string indexing.

9. Final Checklist

Primary Checklist

• 노드 간의 관계가 희소(Sparse)한지 밀집(Dense)한지에 따라 최적의 하드웨어 저장 방식(Matrix vs List)을 제안할 수 있는가? (P1, P4)
• 다익스트라와 벨만-포드 알고리즘의 물리적 시간 복잡도를 비교하고 음수 가중치 유무에 따른 선택 기준을 제시 가능한가? (P1)

Secondary Checklist

• 다중 문자열 매칭 시 매번 $O(N)$ 검색을 수행하는 것과 Trie를 구축해 검색하는 것의 메모리/시간 트레이드오프를 인지하는가?
• 특정 실무 문제(예: 스케줄링)를 그래프 유량 모델이나 매칭 모델로 치환하여 모델링할 수 있는가?

Industry Checklist

• 프로젝트 도중 만난 문제가 'NP-완전'임을 식별하고, 완벽한 해답 대신 휴리스틱이나 근사 알고리즘으로의 선회를 결정 가능한가? (SFIA)
• 수백만 개의 정점을 가진 거대 그래프 처리 시 분산 환경(GraphX 등)에서의 탐색 한계를 PCM 지식과 결합해 설명할 수 있는가?