방향 그래프에서 소스(S)에서 싱크(T)로 흘러갈 수 있는 최대 유량을 구하는 문제입니다. Ford-Fulkerson 알고리즘은 잔여 그래프에서 증가 경로(augmenting path)를 반복해 찾아 최대 유량을 계산합니다.
이분 그래프(Bipartite Graph)에서 최대 매칭을 찾는 문제입니다. 구직자-일자리, 학생-기숙사 배정 같은 할당 문제를 모델링합니다. 증가 경로 기반으로 O(VE)에 해결합니다.
주어진 점들을 모두 포함하는 가장 작은 볼록 다각형입니다. Graham Scan 알고리즘은 정렬 후 스택으로 O(n log n)에 구합니다. GPS 좌표 경계, 충돌 감지, 컴퓨터 비전에 활용됩니다.
N개의 도시를 모두 정확히 한 번씩 방문하고 출발지로 돌아오는 최단 경로를 찾는 문제입니다. 완전 탐색(Brute Force)은 O(n!)이라 비현실적이고, 근사 알고리즘(최근접 이웃)으로 O(n²)에 해결합니다.
NP-완전 문제는 다항 시간에 풀 수 있는 알고리즘이 아직 알려지지 않은 문제들입니다. P=NP 문제는 컴퓨터 과학 최대의 미해결 문제입니다.