홈 > 강의소개
알고리즘Ⅱ
신흥철 교수
KAIST 대학원 전산학부 석사과정
KAIST 대학원 전산학부 박사졸업
KAIST 대학원 전산학부 석사과정
KAIST 대학원 전산학부 박사졸업
숙명여자대학교
Microsoft
현) 유니와이즈 전임교수
AI가 이끄는 스마트한 학습 경험, AI 튜터와 함께 더 빠르고, 더 깊게 학습하세요.
긴 강의 내용을 AI가 핵심만 요약하여 복습 시간을 단축시킵니다.
강의에서 가장 중요한 키워드와 개념을 자동으로 추출해 제공합니다.
학습한 내용을 바탕으로 AI가 생성한 퀴즈를 풀며 이해도를 점검합니다.
모르는 부분을 24시간 언제든 AI 튜터에게 질문하고 답변을 받습니다.
총 2개 챕터, 40강으로 구성되어 있습니다.
| 제목 | 강의시간 | 상세내용 |
|---|---|---|
| 5장. 고급 자료구조 | ||
|
[1강] B-트리의 개념
|
0:
35:
06
|
|
|
B-트리 자료구조와 디스크 접근 특성 요약
• 디스크 물리 구조와 접근 시간: 플래터·트랙·섹터·실린더 구조와 Seek Time·Rotational Latency·전송 시간으로 구성된 디스크 접근 특성, 메모리 대비 현저히 느린 순차 접근 매체라는 점과 디스크 접근 횟수 최소화의 중요성 정리 • B-트리 정의와 구조: 최소 차수 T를 갖는 균형 다분기 탐색 트리로서 키·자식 포인터 정렬 규칙, X.n·X.leaf·자식 포인터 배열 구성, 리프 동일 높이 특성, 각 노드의 키/자식 수 범위(루트 예외 포함)와 2-3-4 트리(T=2) 사례 구조 정리 • B-트리 성능 분석과 차수 T 선택: 최악 경우 최소 키 수로부터 높이 상한식 H ≤ log_T((N+1)/2) 유도, T 증가에 따른 트리 높이 감소와 디스크 블록 접근 횟수 감소 효과, 상용 DB에서 블록 크기에 맞춰 T≈100~200을 사용해 수백만 레코드도 높이 3~4 수준으로 유지하는 인덱스 설계 원리 정리 |
||
|
[2강] B-트리의 기본연산
|
0:
52:
59
|
|
|
비트리 기본 연산과 삽입 알고리즘 핵심 정리
• 비트리 기본 구조와 연산 복잡도: 디스크 기반 다분기 균형 탐색트리로, 노드 키/자식 개수 범위(차수 t), 높이 O(log_t n), 검색·삽입 시 디스크 접근 O(log n), CPU 시간 O(t log n) 구조 정리 • 비트리 검색·노드 분할 연산: B-TREE-SEARCH의 노드 내 순차 검색과 자식 포인터 하향 이동 구조, 가득 찬 노드의 중앙 키 승격과 좌·우 분리로 이루어진 SPLIT-CHILD 분할 절차 및 디스크/CPU 비용 • 하향식 삽입 알고리즘: B-TREE-INSERT와 INSERT-NONFULL에서 “내려가며 미리 분할” 전략을 사용해 루트 분할·자식 분할·리프 삽입을 단일 하향 경로에서 처리하고, 모든 리프 높이 동일한 균형 상태 유지 |
||
|
[3강] B-트리에서 키 삭제하기
|
0:
42:
00
|
|
|
B-Tree에서 키 삭제 연산: 경우별 알고리즘 정리
• B-Tree 삭제 조건과 목표: 모든 노드 키 수를 최소 T-1개 이상 유지하기 위해 하향 경로에서 미리 T개 이상 확보하며 한 번의 재귀 하향 과정에서 삭제를 완료하는 전략 정리 • 삭제 경우별 알고리즘: 리프 노드 직접 삭제, 내부 노드에서 선행/후행 키 교체 후 재귀 삭제, 하위 서브트리 경로에서 형제 노드 차용·병합을 활용해 T개 유지하며 진행하는 세 경우의 절차 구조 • 루트 처리와 시간 복잡도: 루트 병합·유일 자식 승격에 따른 트리 높이 감소 조건과 삭제 연산의 디스크 접근·CPU 시간 복잡도 O(log_T N), 삽입 알고리즘과의 대칭적 설계 원리 정리 |
||
|
[4강] 피보나치 힙의 구조
|
0:
15:
41
|
|
|
Fibonacci 힙의 구조와 연산, 잠재비용 함수 개요
• Fibonacci 힙 기본 개념: 여러 개의 최소 힙 트리로 이루어진 forest 구조의 병합 가능 우선순위 큐로, 이진 힙보다 insert·decrease-key·union 연산에서 더 작은 분할 상환 시간 제공 • Fibonacci 힙 연산 및 노드 구조: make-heap·insert·minimum·extract-min·union·decrease-key·delete 7개 연산과 H.n·H.min, parent·child·left·right·degree·mark 필드를 사용하는 루트 리스트·원형 이중 연결 리스트 기반 최소 힙 트리 구조 정의 • 잠재비용 함수와 분할 상환 분석: 루트 개수 T_H와 마크된 노드 수 M_H를 이용해 Φ(H)=T_H+2M_H로 정의하고, 이를 통해 insert·decrease-key·union은 O(1), extract-min·delete는 O(log n) 분할 상환 시간으로 분석하여 Dijkstra 등 알고리즘 최적화에 활용 |
||
|
[5강] 병합 가능한 힙 연산
|
0:
59:
58
|
|
|
피보나치 힙 연산과 최소 노드 추출의 분할상환 분석 핵심 정리
• 피보나치 힙 기본 연산 및 잠재함수: Make-Heap·Find-Min·Insert·Heap-Union의 포인터 기반 구현과 루트 수·마크 수를 이용한 잠재함수 정의를 통해 실제비용과 분할상환 비용이 모두 O(1)이 되도록 설계 • Extract-Min 및 Consolidate 구조: 최소 노드 제거와 자식의 루트 승격 후 같은 차수 루트들을 heap-link로 병합하여 차수가 서로 다른 루트만 남기도록 하는 Consolidate 절차와 루프 불변성·배열 A 사용 구조 정리 • 최대 차수 D(n)와 분할상환 분석: 차수 k 트리의 최소 노드 수 2^k를 이용한 D(n)=O(log n) 도출과 루트 수 변화에 기반한 잠재비용 해석으로 Extract-Min의 분할상환 시간복잡도 O(log n) 증명 |
||
|
[6강] 키 감소시키기와 노드 삭제하기
|
0:
34:
01
|
|
|
피보나치 힙 Decrease-Key와 연속분리(Cascading Cut)의 동작 원리 요약
• Decrease-Key와 Cut: 노드 키 감소 후 최소 힙 특성 위반 시 해당 노드를 부모로부터 cut해 루트 리스트로 이동시키고, 최소 포인터를 갱신하는 연산 구조 • Cascading Cut과 마크필드: 마크필드로 자식 손실 횟수를 기록하여 첫 손실 시 mark=false→true, 두 번째 손실 시 부모도 cut하고 상위로 연쇄 분리하는 메커니즘 • 분할상환 분석과 Delete: 잠재 함수 Φ=t+2m을 사용해 Decrease-Key의 분할상환 비용을 O(1)로 보이고, Delete는 키를 −∞로 Decrease-Key 후 Extract-Min으로 구현되어 O(D(n)) 시간, D(n)=O(log n) 관계로 전체 효율 보장 |
||
|
[7강] 최대 차수의 한계 정하기
|
0:
46:
01
|
|
|
Summary Content:
피보나치 힙 최대 차수의 한계와 피보나치 수 특성 • 피보나치 힙 최대 차수 D(n): 차수 K 노드 서브트리 크기 S_K 정의와 자식 차수 하한(보조정리 19.1)을 이용해 size(x) ≥ S_K 관계 설정 • 피보나치 수·황금비 연계 구조: 피보나치 수 합 공식 F_{k+2}=1+∑_{i=0}^k F_i와 F_{k+2} ≥ φ^k(φ는 황금비)를 사용해 S_K ≥ F_{K+2} ≥ φ^K 도출 • 시간복잡도 결론: n ≥ size(x) ≥ φ^K 관계로부터 최대 차수 D(n) ≤ log_φ n = O(log n)을 얻고, 이를 통해 Extract-Min과 Delete 연산의 분할상환 시간복잡도가 O(log n)임을 정리 |
||
|
[8강] 동적 집합, 기본 방법
|
0:
56:
20
|
|
|
반 엠데보아스 트리와 동적집합 연산 효율화 개요
• 동적집합·우선순위 큐 모델링: 전체집합 U 크기 u와 실제 원소 수 n을 분리하고, Insert/Delete/Member/Min/Max/Successor/Predecessor 연산을 기준으로 힙·레드블랙트리·Fibonacci heap의 시간 복잡도 한계 정리 • 비트벡터·이진트리·클러스터 구조: 비트벡터로 O(1) Insert/Delete/Member와 O(u) Min/Max/Succ/Pred, 비트벡터 위 포화 이진트리로 이들을 O(log u)로 개선, u=2^{2k} 분할과 cluster(x), offset(x), summary 비트벡터로 O(√u) Min/Max/Succ/Pred 구현 • 반 엠데보아스 트리 준비 아이디어: 전체 인덱스 공간을 반복적으로 √u 단위로 분해하고 클러스터 존재 여부만 상위 summary에 유지하는 재귀적 설계로, 비교 기반 log n 하한을 회피해 동적집합 연산을 universe 크기 u 기준 서브로그 시간으로 가속하는 이론적 기반 정리 |
||
|
[9강] 재귀 구조 (1)
|
0:
59:
59
|
|
|
Proto van Emde Boas 트리의 점화식과 비트 기반 클러스터 구조
• Proto van Emde Boas 점화식과 시간복잡도: 우주 크기 U에 대해 T(U)=T(√U)+O(1) 점화식을 세우고 U=2^m, S(m)=T(2^m) 치환으로 S(m)=S(m/2)+1을 얻어 마스터 정리로 T(U)=Θ(log log U) 도출, log U와 log log U 증가 속도 비교로 효율성 해석 • 비트 기반 우주 표현과 인덱스 분할: U=2^K에서 필요한 비트 수를 log₂U로 두고 √U에 대해 비트 수가 절반(K/2)으로 줄어듦을 이용하여 인덱스 x를 high(x)·low(x)로 분해하고 high(x)는 클러스터 번호, low(x)는 클러스터 내 offset으로 사용, x=floor(x/√U)·√U+(x mod √U)와 비트 시프트 관계로 복원 • Proto vEB 계층 구조와 클러스터·Summary: 우주 [0,U-1]를 √U 개 클러스터(각 크기 √U)로 재귀 분할하고, 각 클러스터를 또 하나의 vEB로 구성하며, Summary 구조에 비어 있지 않은 클러스터 정보를 비트 벡터로 기록함으로써 존재 여부·최소/최대·successor 연산을 루트 U 단위로 우주를 줄여가며 O(log log U)에 수행하는 계층적 클러스터 구조 형성 |
||
|
[10강] 재귀 구조 (2)
|
0:
58:
30
|
|
|
프로토 반 van Emde Boas 구조에서 멤버·최소·최대·직후원소 연산 정리
• 반 van Emde Boas 구조(bvEB) 네이밍·구조: universe 크기 u에 따라 클러스터와 summary를 계층적으로 분해하고 high/low 비트 분할과 b,u 표기 규칙으로 각 노드의 위치·역할을 유일하게 식별하는 구조 • 기본 연산 집합(member·minimum·maximum·successor·insert·delete): high/low 분해를 이용한 재귀 호출과 summary·클러스터 간 상호작용으로 멤버십 검사, 최소·최대·직후 원소 탐색, 삽입·삭제를 수행하는 동적 집합 연산 체계 • 시간 복잡도 특성: member는 T(u)=T(√u)+O(1)으로 Θ(log log u), minimum·maximum·insert·delete는 T(u)=2T(√u)+O(1)으로 Θ(log u), successor는 T(u)=2T(√u)+Θ(log u)로 Θ(log u log log u)를 갖는 universe 기반 성능 특성 |
||
|
[11강] 반 엠데 보아스트리 (1)
|
0:
42:
57
|
|
|
반 Van Emde Boas 트리의 집합 크기 완화와 min/max 기반 구조
• 우주 크기 확장과 제곱근 분해: 모든 $u=2^k$에서 상위제곱근·하위제곱근을 정의하고 high(x)/low(x)로 인덱스를 분해해 summary 트리와 cluster 배열 구조를 구성함 • 노드 구조와 min/max 필드: 각 노드는 (u, min, max, summary, cluster[])로 구성되며, 기본 노드(u=2)는 min/max만을 갖고 min 값은 어떤 하위 클러스터에도 중복 저장되지 않도록 해 공집합·원소 수를 상수 시간에 판별함 • 연산과 시간 복잡도: min/max, successor/predecessor, insert/delete에서 클러스터 max·min 비교만으로 재귀 호출을 1회로 줄여 $T(u)=T(\sqrt{u})+O(1)$을 만족하게 하고, 모든 주요 연산을 $O(\log\log u)$ 시간에 수행함 |
||
|
[12강] 반 엠데 보아스트리 (2)
|
0:
59:
28
|
|
|
Van Emde Boas 트리 연산 구조와 시간복잡도 정리
• Van Emde Boas 트리 구조와 표현 방식: 우니버스 분할 클러스터·요약 노드·기본 노드(크기 2)·high/low 분해·min/max 저장 규칙을 통해 각 원소와 비어 있지 않은 클러스터를 계층적으로 표현하는 동적집합 구조 • 동적집합 연산과 알고리즘 구조: member·minimum/maximum·successor·predecessor·insert·delete 연산을 min/max 비교와 high/low 기반 재귀로 설계하고, successor·predecessor에서 max/min 활용, insert/delete에서 empty-tree 처리·min 교체·클러스터/요약 트리 상태 갱신 규칙으로 일관성 유지 • 시간복잡도 분석: 각 레벨에서 상수 시간 연산과 단일 재귀 호출을 유지하여 점화식 T(u)=T(√u)+O(1)로 멤버십·석세서·프레데세서·삽입·삭제 모두 O(log log u) 달성하며, 레벨당 두 번 재귀를 쓰는 프로토 Van Emde Boas 구조(O(log u))와 대비되는 최적화 원리 정리 |
||
|
[13강] 서로 소 집합의 연결 리스트 표현
|
0:
45:
02
|
|
|
서로소 집합 자료구조와 연결 리스트 구현 및 가중치 유니온 개념 정리
• 서로소 집합과 기본 연산: 서로소 집합 정의 및 대표 원소 기반 관리, Make-Set·Union·Find-Set 연산 구조와 무방향 그래프 연결 요소 판별 알고리즘 정리 • 연결 리스트 구현과 단순 유니온 복잡도: 집합 객체(head·tail·집합 포인터)로 표현된 연결 리스트 기반 Union-Find 구조와 포인터 갱신으로 인한 단순 유니온의 Θ(n²) 시간 복잡도 분석 • 가중치 유니온 휴리스틱과 성능: 집합 크기를 가중치로 사용해 항상 작은 집합을 큰 집합에 붙이는 weighted union 규칙과 각 원소 O(log n) 갱신을 통한 전체 연산 O(m + n log n) 시간 복잡도 도출 |
||
|
[14강] 서로소 집합 포리스트
|
0:
32:
23
|
|
|
서로소 집합의 트리 표현과 순위 합병·경로 압축 요약
• 서로소 집합 트리 표현: forest 구조로 각 집합을 트리로 저장하고 make-set, find-set, union을 루트 포인터 기반으로 구현하여 union은 O(1), find-set은 트리 높이에 비례하는 연산으로 정의 • 순위에 의한 합병(Union by Rank): 루트에 rank(높이 상한)를 저장하고 항상 낮은 rank 트리를 높은 rank 트리에 붙이며, rank가 같을 때만 새 루트 rank를 1 증가시켜 트리 높이를 O(log n)으로 유지하고 전체 연산을 O(m log n)에 수행 • 경로 압축(Path Compression)과 복잡도: find-set 수행 시 경로상의 모든 노드 부모를 직접 루트로 갱신하여 트리 높이를 극단적으로 줄이고, 순위 합병과 함께 사용할 때 전체 m개의 연산을 O(m α(n)) 시간(역 아커만 함수 기반, 실제로는 거의 선형 시간)에 처리하는 구현 방법 정리 |
||
| 6장. 그래프 알고리즘 | ||
|
[15강] 그래프의 표현. 너비 우선 검색 (1)
|
0:
52:
22
|
|
|
그래프 표현과 너비 우선 탐색(BFS) 핵심 정리
• 그래프 구조와 표현: 정점·간선 개념, 무방향/방향 그래프, 가중치 그래프, 인접 리스트·인접 행렬 표현 및 희소·밀집 그래프에서의 메모리 특성 정리 • 특수 그래프 및 구조: 트리의 |E|=|V|-1 관계, 신장 트리·최소 신장 트리 개념을 통한 최소 간선 연결 구조 이해 • 너비 우선 탐색(BFS): 색·거리·직전 정점 정보와 큐 기반 절차, BFS 트리와 최단 간선 수 경로 구성, 인접 리스트 기준 시간 복잡도 Θ(|V|+|E|) 분석 |
||
|
[16강] 너비 우선 검색 (2)
|
0:
30:
50
|
|
|
너비우선검색(BFS) 보조정리와 거리 특성 정리 요약
• 최단 경로 거리와 간선 특성: 정점 s에서 v까지 최단 경로 거리 δ(s,v) 정의, 경로 없음 시 δ(s,v)=∞, 임의의 간선 (u,v)에 대해 δ(s,v) ≤ δ(s,u)+1 성질 정리 • BFS 거리 배열과 큐 불변식: BFS에서 v.d ≥ δ(s,v) 관계, 흰색 정점 최초 방문 시만 v.d = u.d+1로 갱신, 큐 Q 내부에서 거리 값이 단조 비감소이며 맨 앞·맨 뒤 정점 거리 차이가 최대 1인 구조와 선삽입 정점 거리 보존 특성 • 증명 방법론: while 루프 반복·인큐/디큐 횟수·거리 단계 등을 귀납 변수로 한 귀납법, BFS 색 변화·거리 갱신 규칙·큐 순서와 충돌을 이용한 모순법으로 보조정리와 따름정리의 거리·큐 관련 불변식 증명 |
||
|
[17강] 너비 우선 검색 (3)
|
0:
45:
45
|
|
|
너비우선검색(BFS) 타당성 증명과 너비우선 트리 특성 정리
• BFS 정확성 성질: 무가중치 그래프에서 최단경로거리 보장·도달 가능한 모든 정점의 완전 탐색·최적 부분 구조를 색(흰색·회색·검은색) 기반 모순 증명으로 정당화 • BFS 트리와 전정점 부분 그래프: 전정점 배열로 정의된 부분 그래프 Gπ가 |Eπ|=|Vπ|-1인 연결 비순환 구조의 트리가 되며, 레벨 순회(큐 기반 거리 레벨 확장)를 통해 출발점으로부터 유일한 단순 최단경로 트리를 형성 • 최단경로 출력 구조: 전정점 v.π를 따라 거슬러 올라가는 재귀 호출로 s→v 최단경로를 정방향으로 출력하며, 경로 길이 k에 대해 시간 복잡도 O(k)를 갖는 단일 경로 기반 출력 알고리즘 정립 |
||
|
[18강] 깊이 우선 검색 (1)
|
0:
35:
24
|
|
|
깊이우선검색(DFS) 알고리즘과 깊이우선 포리스트 정리
• 깊이우선검색(DFS)와 깊이우선 포리스트: 깊이 우선 탐색 절차·BFS와의 비교·여러 시작점에서 형성되는 DFS 트리와 포리스트 구조 정의 • DFS 상태·시간·간선 분류: 색(흰·회·검)과 발견/종료 시간·전역 시간으로 정점 상태 추적, 트리/역행/순행/교차 간선 4분류 및 DFS 트리 간선 집합 Eπ 구성 • DFS 알고리즘과 시간 복잡도: 초기화와 DFS-VISIT 재귀 구조·트리 후위 순회와의 관계·정점/간선 1회 처리에 기반한 O(|V|+|E|) 수행 시간 분석 |
||
|
[19강] 깊이 우선 검색 (2)
|
0:
45:
58
|
|
|
깊이 우선 검색의 과로 구조와 흰색 경로 정리 요약
• DFS 시간 구간과 과로 구조: 각 정점의 발견시간·종료시간으로 형성되는 포함/불포함 구간 구조를 통해 조상·자손·비직계 관계를 판별하고, 자손 구간 중첩 및 과로 정리로 두 정점 구간이 불겹침·포함·포함반대 세 유형만 가짐을 정식화함 • DFS 간선 분류와 흰색 경로 정리: 정점 색(흰색·회색·검은색)과 시간 조건을 이용해 간선을 트리·역행·순행·교차로 분류하고, 흰색 경로 정리로 특정 시점의 흰색 경로 존재 여부와 DFS 트리에서의 자손성(조상–자손 관계) 동치 조건을 제시함 • 무방향 그래프 DFS 구조: 무방향 그래프에서의 DFS는 간선이 트리간선 또는 역행간선으로만 나타나며, 쌍방향 간선 특성과 시간 구간 포함 관계를 통해 순행·교차 간선이 배제되는 구조적 제약을 설명함 |
||
|
[20강] 위상정렬
|
0:
35:
37
|
|
|
위상정렬과 DFS 기반 Topological Sort 알고리즘 정리
• 위상정렬 개념과 DAG 조건: 비순환 방향그래프(DAG)에서 간선 방향(선후관계)을 보존하며 모든 정점을 선형 순서로 나열하는 정렬 개념, 순환 존재 시 위상정렬 불가능 • 진입차수 기반 위상정렬 알고리즘: 진입차수 0 정점을 큐·스택에 삽입 → 선택·출력 → 간선 제거·진입차수 갱신 반복을 통해 다양한 위상 순서를 생성하며, 수행시간은 O(V+E) • DFS 기반 Topological Sort: DFS 종료시간 역순으로 정점을 나열해 위상정렬을 얻으며, DAG에서 역행간선 부재 성질을 이용해 알고리즘의 정확성을 증명하고 전체 시간복잡도는 O(V+E)로 분석함 |
||
|
[21강] 강한 연결요소
|
0:
58:
10
|
|
|
강한 연결 요소와 전치 그래프를 이용한 SCC 알고리즘 핵심 정리
• 강한 연결 요소(SCC)·전치 그래프·SCC 요소 그래프: 상호 도달 가능한 정점 최대 집합 정의, 간선 반전 시 SCC 불변성, SCC 수축 그래프가 DAG가 되는 구조와 성질 정리 • DFS 시간 개념과 보조정리: 검색·종료 시간과 SCC 단위 D(C), F(C) 정의, 서로 다른 SCC 간 간선 방향과 종료 시간 대소 관계, 전치 그래프에서의 간선 방향·종료 시간 불변식 제시 • Kosaraju형 SCC 알고리즘: 원 그래프 DFS로 종료 시간 계산, 전치 그래프 구성, 종료 시간 역순 DFS로 각 트리가 정확히 하나의 SCC가 됨을 귀납적으로 증명하여 알고리즘의 완전성과 정확성 보장 |
||
|
[22강] 최소 신장 트리의 확장
|
0:
57:
13
|
|
|
최소 신장 트리와 절단, 안전간선 개념 정리
• 최소 신장 트리(MST)와 Generic MST 알고리즘 : 신장 트리 정의(정점 동일·간선 |V|-1·연결·비순환)와 가중치 합 최소 조건, 안전간선만을 반복 추가한다는 루프 불변성을 통한 Generic MST 알고리즘의 정당성 구조 • 절단(cut)·교차간선·경량간선·존중(respect) 개념 : 정점 집합을 둘로 나누는 절단, 절단을 가로지르는 교차간선, 그중 가중치가 최소인 경량간선 정의와 절단이 부분집합 A의 간선을 끊지 않을 때 “A를 존중한다”는 조건 정식화 • 경량간선의 안전성 정리와 포리스트 관점 : 절단이 A를 존중할 때 그 절단 위의 경량간선이 항상 안전간선이 됨을 보이는 안전성 정리와, A가 이루는 포리스트의 각 연결요소 사이의 경량간선을 선택하면 Kruskal·Prim 알고리즘의 그리디 선택이 안전함을 보이는 따름정리 정리 |
||
|
[23강] 크루스칼 알고리즘과 프림 알고리즘. 안전성 정리
|
0:
56:
36
|
|
|
최소 신장 트리 알고리즘: Kruskal과 Prim 핵심 정리 요약
• Kruskal 알고리즘과 서로소 집합: 간선 가중치 오름차순 정렬·사이클 미형성 최소 간선 선택·포리스트 병합과 경로 압축/union-by-rank 기반 Disjoint Set으로 MST 구성 및 시간 복잡도 O(|E| log |V|) 정리 • Prim 알고리즘과 우선순위 큐: 단일 정점에서 시작해 key·π 배열과 우선순위 큐(특히 Fibonacci heap)로 절단의 경량 간선을 반복 선택하여 트리를 확장하고 시간 복잡도 O(|E| + |V| log |V|) 분석 • 절단·경량 간선·안전 간선 이론: 절단(cut)을 존중하는 경량 간선이 항상 안전 간선이라는 안전성 정리를 통해 Kruskal·Prim 그리디 선택의 정당성, 두 알고리즘의 구조·자료구조·수행 시간 비교 원리 정리 |
||
|
[24강] 단일 출발지 최단 경로
|
0:
38:
39
|
|
|
단일 출발지 최단경로와 완화(relaxation) 개념 정리
• 단일 출발지 최단경로 문제: 가중 방향 그래프에서 단일 출발점 s로부터 각 정점 v까지의 최단경로 가중치 δ(s,v)를 정의하고, 경로 가중치·최적 부분구조·가중치 순환(특히 음의 가중치 순환의 예외 처리)을 통해 문제 구조를 규정함 • 직전원소 부분 그래프와 최단경로 트리: 각 정점의 직전원소 v.π와 추정거리 v.d를 이용해 직전원소 부분 그래프(V_π,E_π)를 형성하고, 모든 v.d가 δ(s,v)에 수렴했을 때 이를 출발점 s를 루트로 하는 최단경로 트리로 해석함 • 초기화와 완화(relaxation) 특성: Initialize-Single-Source로 v.d를 ∞, s.d=0으로 설정한 뒤 간선 (u,v)에 대한 완화 연산으로 v.d와 v.π를 갱신하며, 삼각부등식·상한·무경로·수렴·경로완화 특성에 의해 알고리즘의 수렴성과 정당성을 보장함 |
||
|
[25강] 벨만-포드 알고리즘
|
0:
44:
47
|
|
|
벨만-포드 알고리즘과 단일 출발지 최단경로 정리 요약
• 단일 출발지 최단경로 문제와 벨만-포드 알고리즘: 가중 방향 그래프에서 한 출발점 s로부터 모든 정점까지의 최단거리 δ(s,v)와 최단경로 트리를 완화 연산 반복으로 구하는 알고리즘 • 알고리즘 구조와 음의 가중치 순환 검출: 정점 수 b에 대해 모든 간선을 b-1번 완화하여 길이 ≤ b-1인 최단경로를 반영하고, 추가 1회 검사에서 v.d > u.d + w(u,v)를 만족하는 간선 존재 여부로 s에서 도달 가능한 음의 가중치 순환 존재를 판단 • 정확성 조건과 도달 가능성 특성: s에서 도달 가능한 음의 가중치 순환이 없으면 알고리즘은 true를 반환하며 모든 정점 v에 대해 v.d = δ(s,v)를 만족하고, v.π로 구성된 부분 그래프는 최단경로 트리가 되며 v.d < ∞는 경로 존재, v.d = ∞는 경로 부재를 의미함 |
||
|
[26강] DAG 단일 출발점 최단 경로
|
0:
29:
12
|
|
|
DAG 단일 출발점 최단경로와 위상정렬, 임계경로 응용 개념 정리
• DAG 단일 출발점 최단경로 알고리즘: 비순환 가중 방향 그래프에서 위상정렬·초기화·위상순 완화를 통해 각 정점 최단거리와 직전원소 기반 최단경로 트리를 Θ(V+E) 시간에 계산하는 알고리즘 • 위상정렬·완화·정당성: DFS/진입차수 0 정점 제거 방식 위상정렬 후 간선 완화 연산(v.d > u.d + w(u,v) 시 거리·직전원소 갱신)을 단 한 번씩 적용해 모든 도달 정점에 대해 v.d = δ(s,v)와 직전원소 부분 그래프 Gπ의 최단경로 트리 성질을 보장하는 원리 • PERT/임계경로 응용: 작업 네트워크를 DAG로 모델링하고 간선 가중치를 부호 반전·거리 초기값을 0/−∞로 설정해 DAG 최단경로 알고리즘을 최장경로 계산에 변형 적용함으로써 프로젝트 전체 기간을 결정하는 임계경로를 산출하는 기법 |
||
|
[27강] 다익스트라 알고리즘
|
0:
34:
32
|
|
|
다익스트라 알고리즘과 최단경로 트리, 정확성 및 시간복잡도 요약
• 다익스트라 알고리즘 개념: 음이 아닌 가중치 방향 그래프에서 단일 출발점 최단경로를 구하며, 집합 S·우선순위 큐 Q·Initialize-Single-Source·Relax 연산으로 동작하고 BFS/Prim과 유사한 점진적 확장 구조를 가짐 • 정확성 및 최단경로 트리: S의 모든 정점 거리가 실제 최단거리라는 루프 불변식을 공리·유지·종료 조건으로 증명하며, 최종 선행자 부분 그래프 Gπ가 각 정점에 대해 s에서의 유일한 최단경로들로 이루어진 최단경로 트리를 형성함 • 시간복잡도와 힙 구조: 우선순위 큐를 피보나치 힙으로 구현 시 Insert·Decrease-Key는 O(1), Extract-Min은 O(log|V|)로 전체 시간복잡도 O(|V|log|V| + |E|)를 이루며, 이진 힙 사용 시 Decrease-Key 비용 증가로 O((|V|+|E|)log|V|)가 됨 |
||
|
[28강] 차이 제약 조건과 최단 경로
|
0:
41:
46
|
|
|
선형계획법과 차이제약조건 시스템, 제약조건 그래프와 최단경로
• 선형계획법과 차이제약조건 시스템: Ax ≤ b 형태의 선형계획 문제 중 각 제약이 x_j - x_i ≤ b_k (행마다 계수 1, -1 두 개만 비영, A_{ij}∈{0,1,-1}, c_i=1)인 특수 시스템 구조 정의 • 차이제약조건 해 구조와 그래프 변환: 해의 상수 이동 불변성(x가 해이면 x + D·1도 해)과 제약 x_j - x_i ≤ b_k를 방향간선 (v_i, v_j), 가중치 b_k로 바꾸고 출발정점 s에서 모든 정점으로 0가중치 간선을 추가한 제약조건 그래프 구성 • 제약조건 그래프, 최단경로, 음의 순환, 알고리즘: s로부터 최단경로 거리 x_i = δ(s, v_i)로 해를 구성하고 음의 가중치 순환 부재를 해의 존재 조건으로 사용하며, 벨만–포드 알고리즘으로 최단경로 및 음의 순환 여부를 판별하고 시간복잡도를 O(n² + nm)으로 분석 |
||
|
[29강] 최단 경로 특성의 증명 (1)
|
0:
32:
01
|
|
|
단일 출발점 최단경로 증명: 삼각부등식~수렴특성
• 삼각부등식·상한 특성·무경로 특성: 최단경로 거리 δ(s,v)와 추정값 v.d의 관계, 경로 유무(∞ 처리), 초기화 후 불변 부등식 구조 정리 • 완화 연산 기본 부등식: RELAX(u,v,w) 수행 시 v.d ≤ u.d + w(u,v) 성립 조건과 경우분석을 통한 거리 갱신 원리 정리 • 수렴 특성: 최단경로 상 선행 정점 u가 정확(u.d = δ(s,u))할 때 (u,v) 완화로 v.d가 δ(s,v)에 도달하고 이후 불변이 되는 수렴·정당성 구조 정리 |
||
|
[30강] 최단 경로 특성의 증명 (2)
|
0:
42:
09
|
|
|
단일출발지 최단경로 알고리즘의 경로 완화와 직전원소 그래프 특성 요약
• 경로 완화 특성(보조정리 24.15) : INITIALIZE‑SINGLE‑SOURCE와 RELAX 반복 시 최단경로 위 간선들을 경로 순서만 지켜 완화하면, 다른 간선 완화가 섞여도 각 정점 거리 추정값이 최단경로 거리로 수렴함 • 직전원소 부분 그래프 트리 성질(보조정리 24.16) : 음의 가중치 순환이 없는 가중 방향 그래프에서 직전원소로 구성한 부분 그래프 Gπ는 RELAX 순서와 무관하게 항상 s를 루트로 하는 비순환 트리이며, 각 정점은 s로 가는 유일한 경로를 가짐 • 최단경로 트리 정리(정리 24.17) : 모든 완화 종료 후 Gπ는 s에서 도달 가능한 모든 정점을 포함하며, Gπ 상의 s‑각 정점 경로가 원 그래프에서의 최단경로가 되므로 s를 루트로 하는 최단경로 트리 구조를 형성함 |
||
|
[31강] 최단 경로와 행렬 곱셈
|
1:
02:
06
|
|
|
모든 쌍 최단경로와 동적 계획법(인접행렬 기반, 행렬곱 아이디어)
• 모든 쌍 최단경로 문제 구조: 가중치 행렬 W와 직전원소 행렬 Π를 사용해 각 정점 쌍의 최단거리와 경로를 정의·표현하고, 음의 순환이 없다는 가정하에서 인접행렬 기반으로 문제를 정식화 • 동적 계획법 기반 최단거리 행렬 L^{(m)}: 간선 수 상한 m을 둔 최단거리 L_{ij}^{(m)}와 점화식 L_{ij}^{(m)} = min_k{L_{ik}^{(m-1)} + w_{kj}}로 L^{(0)}→L^{(n-1)}를 계산하여 모든 쌍 최단거리 행렬을 얻고, Π 행렬로 실제 최단경로를 재구성 • 최소-덧셈 행렬곱과 시간 복잡도: min-plus distance product로 L^{(m)}를 갱신하는 Extend 연산이 O(n^3)이고, m을 1씩 늘리는 순차 확장은 O(n^4), 간선 상한을 두 배씩 키우는 제곱 승확장으로 O(n^3 log n)까지 개선하는 알고리즘 설계 및 분석 |
||
|
[32강] 플로이드-워샬 알고리즘
|
0:
56:
56
|
|
|
플로이드 워셜 알고리즘과 이행적 폐쇄 핵심 정리
• 플로이드 워셜 알고리즘: 중간 정점 집합 {1,…,k}와 점화식 d_{ij}^k = min(d_{ij}^{k-1}, d_{ik}^{k-1}+d_{kj}^{k-1})을 이용해 모든 정점 쌍 최단 거리를 O(n^3)에 계산하는 동적 계획법 알고리즘 • 최단 경로 복원 구조: 직전 정점 행렬 ϕ_{ij}^k를 거리 행렬과 함께 갱신하여 음수 가중치 허용 환경에서 i→j 최단 거리와 실제 경로를 동시에 구성하는 절차 • 이행적 폐쇄(Transitive Closure): 불리언 행렬 T와 점화식 t_{ij}^k = t_{ij}^{k-1} ∨ (t_{ik}^{k-1} ∧ t_{kj}^{k-1})을 사용해 O(n^3)에 그래프에서 임의의 정점 쌍 i→j 경로 존재 여부를 계산하는 플로이드 워셜의 불리언 변형 |
||
|
[33강] 존슨 알고리즘
|
0:
37:
52
|
|
|
존슨 알고리즘과 가중치 재조정을 이용한 모든 쌍 최단경로
• 가중치 재조정과 보존 성질: 정점 잠재함수 h(v)=δ(s,v)로 재가중치 ŵ(u,v)=w(u,v)+h(u)-h(v)를 정의해 모든 간선을 비음수로 만들면서, 음의 가중치 순환 존재 여부와 최단경로 구조(δ̂(u,v)=δ(u,v)+h(u)-h(v))를 보존함 • Johnson 알고리즘 절차: 가상 정점 s 추가 및 0 가중치 간선 연결 → Bellman-Ford로 h(v)=δ(s,v) 계산 및 음의 순환 검출 → ŵ(u,v)=w(u,v)+h(u)-h(v)로 재가중치 후 가상 정점 삭제 → 각 정점에서 Dijkstra 실행해 δ̂(u,v) 계산 → δ(u,v)=δ̂(u,v)+h(v)-h(u)로 원래 최단거리 복원 • 알고리즘 복잡도와 적용 조건: Bellman-Ford 단계 O(VE), Dijkstra 반복 O(VE log V) 수준의 전체 수행시간으로, 음의 간선은 허용하되 음의 순환은 없는 희소 그래프에서 플로이드-워셜 O(V^3)보다 효율적인 모든 쌍 최단경로 알고리즘으로 활용됨 |
||
|
[34강] 플로우 네트워크
|
0:
27:
26
|
|
|
플로우 네트워크와 최대 플로우 기본 개념 정리
• 플로우 네트워크와 제약 구조: 방향 그래프에서 자가 루프·역평행 간선을 배제하고 단일 출발점·단일 도착점을 가지며, 각 간선에 비음수 용량을 부여한 자원 흐름 모델 정의 • 용량·플로우·플로우 보존·플로우 값: 용량 함수와 플로우 함수를 통해 0 ≤ f(u,v) ≤ c(u,v) 제약과 중간 정점에서의 유입=유출 보존 조건을 만족시키고, 출발점 기준 유출량으로 플로우 값을 정의하여 최대 플로우 문제 설정 • 절단·최소 절단과 네트워크 변환: 절단과 절단 용량을 통해 최대 플로우와 최소 절단 관계를 해석하고, 역평행 간선 제거 및 다중 출발점·도착점에 대한 가상 출발점·도착점 추가로 표준 최대 플로우 계산 가능한 네트워크로 변환하는 기법 정리 |
||
|
[35강] 포드 풀커슨 방법 (1)
|
0:
32:
04
|
|
|
Ford-Fulkerson 최대 유량 알고리즘: 잔여 네트워크와 증강경로 개념 정리
• Ford-Fulkerson 방법: 잔여 네트워크에서 증강경로가 존재하는 동안 플로우를 증강하고, 더 이상 증강경로가 없을 때 현재 플로우를 최대 유량으로 확정하는 절차적 최대 유량 계산 방법 • 잔여 용량·잔여 네트워크·증강경로: 잔여 용량은 정·역방향에서 추가 전송·회수가 가능한 유량을 정의하고, 잔여 네트워크는 잔여 용량이 양수인 방향만으로 구성되며, 증강경로는 s–t 간 최소 잔여 용량만큼 플로우를 증가시키는 단순 경로 • 플로우 증강과 경로 선택: 잔여 네트워크에서 정의한 증강 플로우와 증강 함수를 통해 정·역방향 간선을 갱신하며 플로우 보존을 유지하고, 증강경로 선택에 따라 수행 횟수·효율은 달라지지만 적절한 조건에서 최종 최대 유량 값은 동일하게 수렴함 |
||
|
[36강] 포드 풀커슨 방법 (2)
|
0:
46:
12
|
|
|
최대플로우에서 증강함수와 증강경로, 잔여용량 정리 요약
• 플로우 네트워크와 잔여 네트워크: 용량·플로우·용량 제약·플로우 보존으로 정의되는 플로우 네트워크와, 현재 플로우에 대한 정방향·역방향 잔여용량을 간선 가중치로 갖는 잔여 네트워크 구조 정리 • 증강함수·증강경로·경로 플로우: 잔여 네트워크 플로우로부터 정의되는 증강함수 f↑f′의 식과 플로우 조건 만족 증명, 증강경로와 경로의 잔여용량·경로 플로우 정의 및 |f↑f′| = |f| + |f′| = |f| + c_f(p) 값 관계 정리 • Ford–Fulkerson 이론적 근거: 잔여 네트워크에서 증강경로를 찾고 경로의 최소 잔여용량만큼 플로우를 증가시키면 항상 유효한 새 플로우가 되고 값이 정확히 c_f(p)만큼 증가함을 보조정리 26.2·따름정리 26.3으로 정당화함 |
||
|
[37강] 포드 풀커슨 방법 (3)
|
0:
42:
21
|
|
|
최대 플로우와 최소 절단 개념 및 정리 요약
• 플로우 네트워크 절단·절단 용량·순 플로우: 정점 집합 분할을 통한 절단 정의, S→T 간선 용량 합으로 절단 용량 정의, S→T 플로우−T→S 플로우로 순 플로우 정의 및 모든 절단에 대해 순 플로우 값 = 전체 플로우 값 성질 정리 • 절단 용량과 플로우 상한: 임의 플로우 값이 항상 모든 절단 용량을 넘지 못함을 용량 제약과 순 플로우 식으로 증명하고, 최소 절단 용량이 최대 플로우의 상한이 되는 구조 제시 • 최대 플로우–최소 절단 정리: “최대 플로우 = 잔여 네트워크에 증강경로 없음 = 어떤 절단에서 플로우 값이 절단 용량과 같음”의 세 조건 동치성을 통해 최대 플로우 값과 최소 절단 용량이 항상 같음을 보이는 증명 구조 정리 |
||
|
[38강] 포드 풀커슨 방법 (4)
|
0:
28:
10
|
|
|
포드-풀커슨 알고리즘과 수행시간, 최악 사례 분석 요약
• 포드-풀커슨 알고리즘과 잔여 네트워크: 잔여 용량 기반 증강경로 반복 탐색으로 최대 유량 계산, 경로 용량·잔여 용량·증강경로 개념을 통해 유량 조정 구조화 • 최대 유량-최소 컷 정리: 증강경로 미존재 시 유량 값과 최소 컷 용량이 일치함을 통해 최대 유량 도달 판정 및 컷 기반 분석 정리 • 수행시간과 최악 사례: 수행시간 O(|E|·F*) 특성과 경로 선택에 따른 1씩 증가하는 최악 사례를 통해 비효율성 및 Edmonds-Karp 등 개선 알고리즘 필요성 제시 |
||
|
[39강] 포드 풀커슨 방법 (5)
|
0:
53:
11
|
|
|
애드몬드-카프 알고리즘의 최단경로 단조성 및 반복 횟수 분석
• 에드몬드-카프 알고리즘 구조: 잔여 네트워크에서 모든 간선 가중치를 1로 두고 BFS로 최단 증강경로를 선택하여 포드-풀커슨을 구현하며, 이때 각 정점까지의 최단거리(간선 수 기준)는 증강이 진행되어도 감소하지 않는 단조 비감소 성질을 가짐 • 결정적 간선 개념과 반복 상한: 증강경로 상 최소 잔여용량을 갖는 결정적 간선은 증강 후 사라졌다가 역방향 증강으로 재등장할 수 있으며, 동일 간선이 다시 결정적이 될 때마다 관련 정점까지의 최단거리가 최소 2씩 증가하므로 각 간선은 O(V)번만 결정적이 될 수 있고 전체 증강 횟수는 O(VE)로 제한됨 • 시간복잡도 분석: 각 증강 루프마다 BFS 탐색과 경로 상 갱신이 O(E) 시간에 이루어지고, 증강 횟수가 O(VE)이므로 에드몬드-카프 알고리즘의 전체 시간복잡도는 O(VE^2)이며, 이는 최대 유량 값에 의존하는 포드-풀커슨 상한 O(E·|f*|)보다 입력 크기 기준 다항시간 보장을 제공함 |
||
|
[40강] 최대 이분 매칭
|
0:
53:
33
|
|
|
최대플로우와 이분 그래프 최대 매칭의 관계 요약
• 이분 그래프와 매칭 개념: 정점 집합을 L, R로 분할한 이분 그래프에서 한 정점이 최대 하나의 간선만 포함되도록 선택한 간선 집합을 매칭이라 하고, 그 중 간선 수가 최대인 집합을 최대 매칭이라 정의 • 이분 그래프 → 플로우 네트워크 변환과 정수성: 이분 그래프에 소스 s, 싱크 t를 추가해 s→L, L→R, R→t 방향 간선을 두고 모든 간선 용량을 1로 설정하면, 정수 용량 정리에 의해 플로우가 0/1 값을 가져 각 L–R 간선의 플로우 여부가 매칭 포함 여부와 일치 • 최대 매칭–최대 플로우 일치와 알고리즘: 최대 매칭으로부터 s–t 플로우를 구성하고, 반대로 정수 최대 플로우로부터 매칭을 정의하면 두 크기가 항상 같으며, 변환된 네트워크에 Edmond–Karp 알고리즘을 적용해 이분 그래프 최대 매칭을 O(VE²) 시간에 계산 가능 |
||
신흥철 교수님
알고리즘Ⅱ
