Graph, String & Optimization

1. Overview

그래프, 문자열 및 최적화(Graph, String & Optimization, GSO)는 현실 세계의 복잡한 연결 관계와 비정형 텍스트 데이터를 처리하는 고수준 알고리즘들을 다룹니다.

그래프는 네트워크, 사회적 관계, 경로 탐색 등 현대 사회를 모델링하는 핵심 도구이며, 문자열은 정보 검색과 생명 정보학의 근간입니다. 학습자는 최단 경로(Shortest Path), 최소 신장 트리(MST), 네트워크 유량(Flow) 등의 그래프 핵심 이론과 KMP, Trie 등의 문자열 매칭 기법을 학습합니다. 또한 P vs NP 문제와 같은 계산 복잡도 이론의 정점을 탐구하여 '해결 가능한 문제'의 경계를 인식합니다.

2. Scope & Boundaries

In-Scope

• Graph Foundations: 인접 행렬 vs 리스트 물리 저장, 탐색(BFS/DFS), 위상 정렬(Topological Sort)
• Weighted Graphs: 최단 경로(Dijkstra, Bellman-Ford, Floyd-Warshall), 최소 신장 트리(Kruskal, Prim)
• String Mechanics: KMP, Rabin-Karp, Aho-Corasick 등 고도로 최적화된 문자열 매칭 역학
• Optimization & Complexity: 네트워크 유량(Max Flow/Min Cut) 기초, P/NP 클래스 및 NP-완전성 개념

Out-of-Scope

• 인공지능 기반 자연어 처리(NLP) (11. Machine Learning 영역으로 위임)
• 순수 그래프 데이터베이스(GDB) 쿼리 최적화 (06. Data Management 영역으로 위임)

Boundaries

• GSO vs. Design: 04-03(Algorithm Design)이 '방법론'을 다룬다면, GSO는 그 방법론들이 적용되는 '특수하고 복잡한 도메인'에 집중합니다.

3. Counterexample

• 단순히 BFS로 미로를 찾는 것은 GSO 학습의 일부분일 뿐입니다. 음수 가중치가 있는 그래프에서 왜 다익스트라(Dijkstra)가 실패하는지 물리적 릴레이션(Relaxation) 관점에서 설명하고, 수백만 개의 소스 코드에서 특정 패턴을 동시에 검색하기 위해 **문자열 자동파(Automata)**를 어떻게 설계할지 논할 수 있어야 합니다.

4. Prerequisites

4. Prerequisites

• 기초 및 복잡도 (Basic): Big-O를 통한 복잡도 연산 및 실행 시간 예측 능력이 필요합니다. (04. Foundations)
• 핵심 자료 구조 (Recommended): 힙(Heap), 스택/큐, 해시 테이블의 동작 원리가 그래프 성능 최적화에 필수적입니다. (04. CDS)

5. Learning Map

1. Modeling Connections: 정점(Vertex)과 간선(Edge)을 이용해 관계를 물리 메모리에 매핑하는 법을 익힙니다.
2. Traversal & Sorting: 그래프의 모든 노드를 방문하고 실행 순서를 결정하는 기초 논리를 이해합니다.
3. Advanced Graph Logic: 가중치 환경에서의 최단 거리와 연결성 보장을 위한 최적해를 구합니다.
4. Pattern Matching: 비정형 텍스트 속에서 특정 패턴을 $O(N)$에 수렴하게 찾는 문자열 물리 기법을 실습합니다.
5. Complexity Limits: 문제의 난이도를 분류하고 효율적 해결이 불가능한 한계점(NP)을 탐구합니다.

6. Learning Topics

Basic

Core: 그래프 표현과 기초 탐색 (Representations & Traversal)

• Why to Learn: 복잡한 네트워크 데이터를 컴퓨터가 처리할 수 있는 물리 구조로 변환하기 위함입니다.
• What to Learn:
  • 인접 행렬(Adjacency Matrix) vs 인접 리스트(Adjacency List)의 공간/시간 복합도
  • BFS(너비 우선)를 이용한 최단 경로(Unweighted) 탐색 물리
  • DFS(깊이 우선)를 이용한 사이클(Cycle) 감지 및 연결 요소 분석
• How to Learn:
  • 메모리 사용량 계산기를 통해 노드 수 100만 개일 때의 행렬 크기 체감
  • 큐와 스택을 이용하여 수기 시뮬레이션으로 탐색 순서 기록 연습
• Implement: 방향/무방향 그래프를 입력받아 사이클 유무를 판별하는 기본 모듈

Recommended

Core: 가중치 그래프와 경로 최적화 (Weighted Graphs)

• Why to Learn: 지도 서비스나 네트워크 라우팅 등 실제 비용이 존재하는 환경의 해답을 구하기 위해서입니다.
• What to Learn:
  • Dijkstra 알고리즘의 탐욕적 접근과 우선순위 큐(Heap) 가속화
  • MST(최소 신장 트리): Kruskal(Union-Find 활용) 및 Prim 알고리즘
  • 음수 가중치 처리를 위한 Bellman-Ford 알고리즘의 물리적 릴레이션 과정
• How to Learn:
  • 대규모 도시 간 거리 데이터를 활용하여 특정 지점 간의 최단 경로 시각화 실습
  • Union-Find 자료 구조를 직접 구현하여 Kruskal의 정렬 성능 병목 분석
• Implement: 다익스트라 알고리즘을 활용한 최단 경로 탐색 엔진(중간 경유지 포함)

Practical

Core: 문자열 처리와 패턴 매칭 (String & Automata)

• Why to Learn: 대용량 로그나 소스 코드에서 원하는 정보를 낭비 없이 찾아내기 위함입니다.
• What to Learn:
  • KMP 알고리즘의 실패 함수(Failure Function)를 이용한 불필요 비교 건너뛰기
  • Trie와 Aho-Corasick을 이용한 다중 패턴 동시 매칭 원리
  • 정규 표현식(Regex)의 배후에 있는 유한 오토마타(NFA/DFA) 물리 개념
• How to Learn:
  • 단순 매칭($O(NM)$)과 KMP($O(N+M)$)의 문자 비교 횟수 차이 실측
  • 대용량 가사 데이터에서 특정 단어들의 출현 빈도를 Trie로 고속 계산
• Implement: 파일 내 실시간 키워드 감지를 위한 고속 문자열 검색 엔진

Advanced

Core: 유량 역학과 복잡도 이론 (Flow & Complexity)

• Why to Learn: 시스템의 최대 처리 한계를 분석하고, 해결 불가능한 문제에 자원을 낭비하지 않기 위해서입니다.
• What to Learn:
  • 네트워크 유량: Edmonds-Karp 알고리즘과 최대 유량-최소 컷(Max-flow Min-cut) 정리
  • P, NP, NP-Complete 클래스의 정의와 다항 시간 환산(Reduction) 기초
  • 외판원 문제(TSP) 등 난제에 대한 근사 알고리즘(Approximation) 접근법
• How to Learn:
  • 도로망에서 교통 병목 지점을 찾기 위해 유량 알고리즘 적용 시각화
  • SAT 문제가 다른 NP 문제로 변환되는 논리적 흐름 연구
• Implement: 이분 매칭(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 지식과 결합해 설명할 수 있는가?