홈 > 강의소개
알고리즘 문제풀이Ⅱ
신흥철 교수
KAIST 대학원 전산학부 석사과정
KAIST 대학원 전산학부 박사졸업
KAIST 대학원 전산학부 석사과정
KAIST 대학원 전산학부 박사졸업
숙명여자대학교
Microsoft
현) 유니와이즈 전임교수
AI가 이끄는 스마트한 학습 경험, AI 튜터와 함께 더 빠르고, 더 깊게 학습하세요.
긴 강의 내용을 AI가 핵심만 요약하여 복습 시간을 단축시킵니다.
강의에서 가장 중요한 키워드와 개념을 자동으로 추출해 제공합니다.
학습한 내용을 바탕으로 AI가 생성한 퀴즈를 풀며 이해도를 점검합니다.
모르는 부분을 24시간 언제든 AI 튜터에게 질문하고 답변을 받습니다.
총 2개 챕터, 18강으로 구성되어 있습니다.
| 제목 | 강의시간 | 상세내용 |
|---|---|---|
| 5장. 고급 자료구조 | ||
|
[1강] B-트리 (1)
|
0:
34:
25
|
|
|
B-트리 연습문제 핵심 정리: 최소차수와 키 개수 범위
• B-트리 최소차수 t 개념: 각 노드 키 수[t-1, 2t-1], 자식 수[t, 2t]를 결정하며 t=1은 키 없는 노드로 인해 균형 검색 구조와 AEO 관점의 효율적 인덱싱 목적에 부합하지 않아 t≥2로 제한됨 • 2-3-4 트리(최소차수 2 B-트리) 구조와 연산: 노드당 키 수[1,3], 자식 수[2,4] 범위에서 리프 삽입·탐색 중 선분할(split)과 가운데 키 승격으로 모든 리프를 동일 높이에 유지하며 균일한 탐색·삽입·삭제 성능 확보됨 • 높이 h, 최소차수 t B-트리의 키 개수와 디스크 액세스: 전체 키 수 범위는 최소 2t^h-1, 최대 (2t)^{h+1}-1로 트리 높이를 로그 규모로 제한해 노드=디스크 블록 매핑 시 수회 디스크 액세스로 기가~테라바이트급 데이터 인덱싱 가능함 |
||
|
[2강] B-트리 (2)
|
0:
35:
57
|
|
|
비트리 삽입·삭제·탐색 심화 개념 정리 (최소차수 2·3, 최소키·직전원소, 디스크 I/O 최적화)
• 비트리 구조와 최소차수: 최소차수 t에 따른 노드 키/자식 수 범위(키 t-1~2t-1, 자식 t~2t), 2-3-4 트리(t=2)·t=3 비트리 형태와 균형 유지 조건 정리 • 비트리 연산 알고리즘: 리프 삽입과 국지적 분할 전파, 최소 키 탐색(가장 왼쪽 자식 경로), 주어진 키의 직전 원소 탐색(왼쪽 서브트리 최대값·리프 내부 인접 키·부모 방향 역추적) 절차 정리 • 비트리 삭제와 디스크 I/O 최적화: t=3 기준 삭제 시 분할 대신 형제 차용·병합·부모 키 포함 병합 규칙과, 기존 키 재삽입 등 구조 변화 없을 때 디스크 리드/라이트 생략 조건 정리 |
||
|
[3강] 서로소 집합의 자료구조 (1)
|
0:
29:
31
|
|
|
서로소 집합과 연결요소, 가중치 유니온 상환분석 핵심 정리
• 연결요소와 강한 연결요소: 무방향/방향 그래프에서 연결요소와 강한 연결요소 정의, 무방향 그래프에서 두 개념의 사실상 동일성, connected components 알고리즘으로 최종 연결요소 분할 도출 및 집합-연결요소 대응 관계(대우 증명 포함) 정리 • 서로소 집합과 union-find 연산 분석: make-set, find-set, union 기반 connected components 알고리즘 동작 절차, 두 정점의 동일 집합 ⇔ 동일 연결요소 논리 구조, 그래프에서 find-set 호출 횟수 2E, union 호출 횟수 V−K 도출 및 연산 수 계산 구조 정리 • 가중치 유니온 휴리스틱와 분할 상환 시간복잡도: 작은 트리를 큰 트리에 붙이는 weighted union으로 트리 높이 제어, 연결리스트 기반 make-set·find-set의 O(1) 상환 시간과 union의 O(log n) 상환 시간 증명 구조, 전체 m회 연산 시 O(m log n) 상환 복잡도 도출 및 정리 21.1 핵심 아이디어 요약 |
||
|
[4강] 서로소 집합의 자료구조 (2)
|
0:
46:
00
|
|
|
서로소 집합 자료구조 최적화: 포인터 구조와 수행시간 분석
• 서로소 집합 포인터 구조 최적화: 집합 객체의 head·tail 포인터를 축소·제거하고 원소 rep·next 포인터 재구성으로 FIND-SET·UNION의 점근적 수행시간을 기존 리스트 표현과 동일하게 유지하는 구조 설계 • 순위에 의한 합병 시간 하한 분석: MAKE-SET·UNION·FIND-SET 연산 순서를 균형 이진 트리 형태로 구성하여 union-by-rank의 전체 수행시간 하한을 Ω(m log n)으로 만들고 상한과 함께 Θ(m log n) 복잡도 예시 도출 • PRINT-SET 연산 지원 자료구조: 각 원소에 next 포인터 1개를 추가해 집합별 원형 단순 연결 리스트를 구성함으로써 PRINT-SET을 집합 크기 |S|에 비례하는 O(|S|)에 수행하면서 MAKE-SET·UNION·FIND-SET의 점근적 시간 복잡도를 보존하는 설계 |
||
| 6장. 그래프 알고리즘 | ||
|
[5강] 기본 그래프 알고리즘 (1)
|
0:
49:
23
|
|
|
그래프의 유니버설 싱크와 연결행렬, BFS 특성 정리 요약
• 유니버설 싱크와 판별 알고리즘: 유니버설 싱크(모든 정점에서 들어오고, 나가는 간선 0인 정점) 정의·유일성·존재 조건과, 인접행렬에서 행·열 제거 규칙을 이용한 O(V) 시간 판별 및 검증 절차 정리 • 방향 그래프 연결행렬과 BBᵀ: 방향 그래프의 연결행렬 B 정의(정점-간선 관계를 -1,0,1로 표현)와 BBᵀ의 대각 성분이 각 정점 차수, 비대각 성분이 정점 쌍 간 간선 수의 음수를 의미함을 구조적으로 해석 • BFS 색 단순화와 인접리스트 순서 영향: BFS에서 화이트/넌-화이트 2상태만으로 방문 관리가 충분함을 보이고, 인접리스트 순서가 최단 거리값(u.d)에는 영향을 주지 않으나 BFS 트리의 부모-자식 구조와 모양에는 영향을 미치는 성질 정리 |
||
|
[6강] 기본 그래프 알고리즘 (2)
|
0:
34:
58
|
|
|
그래프 최단경로 트리와 BFS/DFS 성질 연습 문제 요약
• BFS 최단경로 트리와 이분 그래프 판별: 최단경로 간선집합 Eπ 정의, BFS 규칙으로 생성 불가능한 최단경로 트리 구조, 경쟁 관계 그래프의 BFS 기반 이분 그래프 판별 및 시간복잡도 분석 • DFS 상태·메모리 최적화와 간선 유형: DFS 색 배열의 WHITE/비-WHITE 2상태 최소 표현, 불필요한 상태·비트 제거를 통한 메모리 절약 아이디어, 트리·순행·역행·교차 간선과 발견·종료 시간구간 부등식의 대응 관계 정리 • DFS 시간구간과 조상–자손 관계 오해 반례: 경로 존재와 부분적인 시간 부등식(u.d < v.d, v.d < u.f 등)만으로 조상–자손을 단정할 수 없음을 보이는 반례 구성, 조상–자손 판정에는 u.d < v.d < v.f < u.f 형태의 전체 시간구간 포함 관계가 필요함을 강조 |
||
|
[7강] 기본 그래프 알고리즘 (3)
|
0:
46:
17
|
|
|
방향 그래프 DFS·연결 요소·위상정렬·요소그래프 핵심 정리
• 깊이우선탐색(DFS)·DFS 포리스트: 시작 정점 선택에 따른 DFS 트리 구조, 단일 정점 트리 가능성, DFS 트리 개수와 무방향 그래프 연결 요소 수 일치 관계, 역행간선 부재·간선 수 V−1 성질을 이용한 무방향 연결 그래프 사이클 존재 O(V) 판정 • 진입차수 기반 위상정렬(Kahn 알고리즘): 진입차수 배열 계산, 진입차수 0 정점 큐 처리, 모든 정점 출력 시 DAG 위상순서 생성, 일부 정점 미출력·진입차수 미소거 시 순환 존재 판정, 전체 시간복잡도 O(V+E) • Strongly Connected Components·요소그래프(Condensation Graph): SCC 번호 u.cc 부여, SCC 번호 집합 T 정렬로 요소 정점 집합 V* 구성, 상이한 SCC 쌍 (u.cc, v.cc) 집합 S 생성 및 기수정렬·중복 제거로 요소 간선 집합 E* 도출, G*=(V*,E*) DAG 구성과 전체 알고리즘 O(V+E) 시간 수행 |
||
|
[8강] 기본 그래프 알고리즘 (4)
|
0:
46:
16
|
|
|
방향 그래프 최소 간선 등가 그래프와 반연결성, BFS 간선 분류 특징
• 강한 연결요소 보존 최소 간선 그래프: SCC 분해로 요소 그래프를 만든 뒤 각 SCC 내부를 단순 방향순환경로로 축소하고 SCC 사이에는 방향쌍당 1개 간선만 남겨, 강한 연결구조와 요소 그래프를 유지하면서 간선을 최소화하는 O(V+E) 알고리즘 • 반연결(Semi-Connected) 그래프 판별: SCC·요소 그래프 구성 후 위상정렬을 수행해 모든 정점을 지나는 선형 체인 존재 여부를 검사함으로써, 임의 두 정점 사이 일방향 경로 존재 여부(반연결성)를 O(V+E) 시간에 판별하는 절차와 정확성 조건 • BFS 간선 분류와 거리 특성: 무방향·방향 그래프에서 BFS 시 트리/교차/역행 간선만 존재하고 순행 간선은 부재하며, 트리 간선은 v.d = u.d+1, 교차 간선은 u.d ≤ v.d ≤ u.d+1(무방향), 방향 그래프 역행 간선은 0 ≤ v.d ≤ u.d 등 거리 부등식을 만족해 계층 구조와 최단거리 성질을 규정함 |
||
|
[9강] 최소 신장 트리
|
0:
46:
19
|
|
|
최소 신장트리 연습문제: 절단, 경량 간선, 알고리즘 응용
• 최소 신장트리 이론: 절단과 경량 간선 정리, 최소 가중치 간선 포함 조건, 경량 간선 집합의 한계, 유일한 경량 간선과 MST 유일성 및 역명제 반례 정리 • 가중치 변화와 MST 유지: MST 간선 가중치 감소 시 최적성 보존 증명, 절단 기반 비교와 두 경우 분할(간선 포함/비포함)에 의한 최소성 보장 구조 • MST 알고리즘 복잡도 개선: 정수 가중치 범위가 제한된 경우 Kruskal의 개수 정렬 활용과 Prim의 Van Emde Boas 트리·버킷/해시 구조 적용을 통한 시간 복잡도 감소 기법 |
||
|
[10강] 단일 출발지 최단 경로 (1)
|
0:
42:
44
|
|
|
단일 출발지 최단 경로 심화: Bellman-Ford, DAG, Dijkstra 응용
• Bellman-Ford 수렴 상한·중단 조건: 음의 순환이 없는 가중 방향그래프에서 최단경로 상 최대 간선수 m을 이용해 m+1회 이내 완화 수렴과 change 플래그 기반 조기 종료 원리 정리 • 정점 가중 DAG 임계 경로: 정점 분할 또는 가상 출발 정점 추가로 정점 가중을 간선 가중으로 이전한 뒤, 가중치 부호 반전 + DAG Shortest Path로 임계 경로(최장 경로)를 O(V+E) 시간에 찾는 변환 기법 • Dijkstra 알고리즘 정교화: 반복 조건(Q≠∅ vs |Q|>1) 동치성, 거리·부모 배열과 Bellman-Ford 1회 수행을 통한 결과 검증 절차, 최단경로 간선이 경로 순서대로 완화된다는 주장에 대한 반례 그래프 분석 |
||
|
[11강] 단일 출발지 최단 경로 (2)
|
0:
43:
47
|
|
|
최단경로와 신뢰도, 우선순위 큐 변형, 선형계획법과 차이제약조건 요약
• 신뢰도 최대 경로와 Dijkstra 변형: 간선 신뢰도 확률을 로그·부호 변환해 비음수 가중 최단경로 문제로 환원하고 Dijkstra 알고리즘으로 최대 신뢰도 경로 계산 • 배열 기반 우선순위 큐와 Dijkstra 시간복잡도: 가중치 상한 W를 활용한 거리 상한 K=(V-1)W 배열 우선순위 큐 설계로 Insert·Decrease-Key O(1), Extract-Min 포함 전체 시간복잡도 O(E+VW) 달성 • 최단경로의 선형계획법·차이제약조건 표현: 삼각부등식 x_v-x_u≤w(u,v)와 x_s=0, x_t=δ(t) 제약으로 LP 모델 구성하고, 단일변수 제약을 보조변수 x_0와 그래프 간선으로 변환해 Bellman-Ford로 해 계산 및 음의 가중치 순환에 의한 일관성·언바운디드성 판정 |
||
|
[12강] 단일 출발지 최단 경로 (3)
|
0:
37:
49
|
|
|
벨만-포드와 음의 가중치 순환, 중재이익 탐지 요약
• 벨만-포드와 음의 가중치 순환 판별: 완화 연산과 이전정점 배열(π)의 의미, s.π ≠ nil 조건에 의한 음의 가중치 순환 존재 판정, 음의 순환이 없을 때 |V|-1회 유효 완화로 형성되는 최단경로 트리 구조 정리 • 음의 가중치 순환과 완화 단계 특성: 출발점에서 도달 가능한 음의 가중치 순환 존재 시 무한히 많은 유효 완화 단계 열 구성 원리, 순환 가중치 w(C) < 0에 기반한 d 값의 반복 감소와 수학적 귀납 증명 구조 요약 • 환율 그래프와 중재이익 탐지 알고리즘: 통화를 정점, 환율 r_ij를 간선으로 하는 그래프와 w(i,j) = -log r_ij 변환, 음의 가중치 순환 ↔ 중재이익 사이클 동치성, 벨만-포드 기반 존재 여부 판정 및 실제 환전 순서(사이클) 복원, 전체 시간 복잡도 O(n^3) 정리 |
||
|
[13강] 모든 쌍의 최단 경로 (1)
|
0:
57:
53
|
|
|
모든 쌍 최단경로 행렬표현, 단위행렬, 음의 순환 길이
• min–plus 대수와 단위행렬 L0: 최단경로 DP를 min–plus 행렬곱으로 해석하고, 대각 0·비대각 ∞ 구조의 L0가 (+의 항등원 0, min의 항등원 ∞)에 기반한 min–plus 단위행렬임을 정리 • 단일 출발점 최단경로와 벨만–포드 대응: 단위행렬의 한 행으로 만든 단위벡터와 가중치 행렬 W의 min–plus 반복곱으로 SSSP를 표현하고, Initialize-Single-Source와 n-1회 완화 연산이 이 연산과 동형임을 설명 • 음의 가중치 순환 탐지·최소 길이: 대각원소 L^{(m)}[i,i]의 음수 여부로 음의 순환 존재를 판별하고, Fast APSP의 지수적 길이 증가와 대각 검사로 최초 m을 찾은 뒤, (m/2, m] 구간에서 이분 탐색과 Extended Shortest Paths를 사용해 최소 순환 길이와 O(n^3 log max(n, m*)) 시간복잡도를 도출 |
||
|
[14강] 모든 쌍의 최단 경로 (2)
|
0:
26:
44
|
|
|
플로이드-워셜, 음의 가중치 순환, 존슨 알고리즘 조정 방식 비교 요약
• 플로이드-워셜 알고리즘 최적화: 위첨자 배열 없이 단일 거리 행렬 in-place 갱신으로 모든 단계 거리 갱신을 수행하여 공간 복잡도를 O(n³)에서 O(n²)로 감소시키는 원리 정리 • 음의 가중치 순환 탐지: 플로이드-워셜 최종 거리 행렬의 대각원소 dᵢᵢ 값으로 음의 가중치 순환 존재 여부를 필요충분조건으로 판정하는 기준 및 해석 구조 • 존슨 알고리즘 재가중치 원리: 최소 가중치 일괄 보정의 오류와 h-함수 기반 w'(u,v)=w(u,v)+h(u)-h(v) 재가중치 비교, 임의 출발점 사용 시 실패 원인과 강한 연결 그래프에서의 올바른 동작 조건 정리 |
||
|
[15강] 최대 플로우 (1)
|
0:
57:
27
|
|
|
최대 플로우 네트워크 연습문제 핵심 개념 정리와 증명 구조 요약
• 간선 분할과 네트워크 동등성: 간선 (u,v)를 새로운 정점 x를 통해 (u,x),(x,v)로 분할하되 용량을 동일하게 설정하여 용량 제약·플로우 보존·최대 플로우 값을 모두 유지하는 동등 네트워크 구성 원리 • 도달 불가능 정점 제거와 플로우 집합 볼록성: s–t 경로에 사용되지 않는 정점 집합(Y,Z,X)의 간선 플로우를 0으로 두어도 최대 플로우가 보존됨을 보이고, 두 플로우의 볼록 결합 g=αf₁+(1-α)f₂가 다시 플로우가 됨을 통해 플로우 집합이 볼록 집합임을 증명하는 구조 • 최대 플로우 응용 모델링: 도로망을 정점·간선·용량 1의 플로우 네트워크로 표현하고, 두 사람의 간선-분리 경로 존재 여부를 s–t 최대 플로우 값 ≥ 2인지 검사하는 문제로 환원하는 모델링 절차 |
||
|
[16강] 최대 플로우 (2)
|
0:
40:
09
|
|
|
정점 용량을 간선 용량으로 변환하는 플로우 네트워크 동치 구성
• 정점 용량 네트워크의 vertex-splitting 변환: 각 정점을 두 정점(U1,U2)과 내부 간선으로 분할해 정점 용량을 내부 간선 용량으로 표현하고, 원래 간선(U,V)은 (U2,V1)로 재배선하여 정점 용량이 없는 표준 최대플로우 네트워크 G′( |V′| = 2|V|, |E′| = |E|+|V| ) 구성 • 새 플로우 f′와 동치성: 기존 플로우 f를 이용해 f′(U2,V1)=f(U,V), f′(U1,U2)=∑out f(U,·)로 정의하여 모든 간선에서 용량 제약(0 ≤ f′ ≤ c′)과 플로우 보존을 만족하게 하고, 분할된 s1,s2를 통해 G와 G′의 최대플로우 값이 동일함을 증명 • Ford–Fulkerson 보조 성질과 증강플로우: residual network에서 s로 들어가는 간선을 제거해도 증강경로를 단순 경로로만 사용하므로 최대플로우가 불변이며, 주어진 플로우 f와 residual 플로우 f′를 합친 증강플로우는 플로우 보존은 유지하지만 간선 용량을 초과할 수 있어 용량 제약은 일반적으로 만족하지 않음을 설명 |
||
|
[17강] 최대 플로우 (3)
|
0:
53:
44
|
|
|
Summary Content:
• 간선 연결성 및 플로우 네트워크 변환: 무방향 그래프를 용량 1의 방향 플로우 네트워크로 변환하고, 한 소스에서 모든 싱크로의 최대 플로우 값 최소값으로 간선 연결성을 정의·계산함 • 최대 플로우–최소 절단 및 플로우 조정: 간선 연결성과 최대 플로우·최소 절단 용량의 등가 관계를 증명하고, 순환 경로를 따라 역방향 플로우를 제거해도 전체 최대 플로우를 보존하는 플로우 조정 알고리즘을 정리함 • 최소 절단 중 최소 간선수 선택 기법: 각 간선 용량에 작은 보상값을 더하고 정수 스케일링하여, 플로우 알고리즘 한 번으로 최소 용량 절단들 중 교차 간선수가 최소인 절단을 찾는 용량 재가중 방법을 제시함 |
||
|
[18강] 최대 플로우 (4)
|
0:
28:
10
|
|
|
증강경로 길이 상한과 최대 플로우 갱신 알고리즘 요약
• 이분 그래프 플로우 네트워크 증강경로 상한: $S-L-R-\cdots-T$ 형태 단순경로 구조를 이용해 증강경로 정점 수를 $2\min\{|L|,|R|\}+2$, 간선 수를 $2\min\{|L|,|R|\}+1$로 상한 설정 • 최대 플로우 갱신(용량 1 증가): 정수 용량 네트워크에서 기존 최대 플로우와 잔여 네트워크를 기반으로 변경 간선 반영 후 증강경로를 1회 탐색해, 최소 컷 교차 간선 여부에 따라 최대 플로우를 0 또는 1만큼 조정 ($O(V+E)$) • 최대 플로우 갱신(용량 1 감소): 변경 간선의 현재 플로우 값($f(u,v)=0$ 또는 $>0$)과 잔여 네트워크 상 대체 경로 존재 여부에 따라 플로우 보존 위반을 국소적으로 보정하거나 $S\to T$ 경로 전체에서 1 단위 감소시켜, $O(V+E)$ 시간에 새로운 최대 플로우 계산 |
||
신흥철 교수님
알고리즘 문제풀이Ⅱ
