홈 > 강의소개
알고리즘 문제풀이 통합과정
신흥철 교수
KAIST 대학원 전산학부 석사과정
KAIST 대학원 전산학부 박사졸업
KAIST 대학원 전산학부 석사과정
KAIST 대학원 전산학부 박사졸업
숙명여자대학교
Microsoft
현) 유니와이즈 전임교수
AI가 이끄는 스마트한 학습 경험, AI 튜터와 함께 더 빠르고, 더 깊게 학습하세요.
긴 강의 내용을 AI가 핵심만 요약하여 복습 시간을 단축시킵니다.
강의에서 가장 중요한 키워드와 개념을 자동으로 추출해 제공합니다.
학습한 내용을 바탕으로 AI가 생성한 퀴즈를 풀며 이해도를 점검합니다.
모르는 부분을 24시간 언제든 AI 튜터에게 질문하고 답변을 받습니다.
총 6개 챕터, 50강으로 구성되어 있습니다.
| 제목 | 강의시간 | 상세내용 |
|---|---|---|
| 1장. 기초 | ||
|
[1강] 시작하기 (1)
|
0:
54:
56
|
|
|
선택정렬과 탐색, 점화식과 재귀를 통한 알고리즘 분석 핵심 정리
• 기본 정렬·검색 알고리즘: 선택정렬·삽입정렬·선형검색·이진검색의 절차와 루프 불변성 구조, 점화식을 통한 최선·최악·평균 시간복잡도(Big‑O, Big‑Θ, Big‑Ω) 도출 • 알고리즘 타당성 증명: 수학적 귀납법과 루프 불변성 기법을 이용한 반복·재귀 알고리즘의 정확성 증명, 정렬·검색 알고리즘 간 효율 비교 및 로그 시간/제곱 시간 비교 분석 • 재귀와 점화식 해법: 삽입정렬·이진검색의 재귀 정의와 대응 점화식 설정, 전개법을 통한 해 구하기, n·n²·n log n·log n 등 대표 시간복잡도 유형의 구조적 이해 |
||
|
[2강] 시작하기 (2)
|
0:
50:
33
|
|
|
삽입정렬의 이진검색, 혼합 정렬, 역순쌍과 시간복잡도 개념 정리
• 삽입정렬+이진검색 시간복잡도: 탐색 비용은 O(log n)으로 감소하지만 원소 이동 비용이 O(n)을 지배하여 전체 최악 시간복잡도는 여전히 O(n²) 유지 • 병합정렬+삽입정렬 혼합 알고리즘: 길이 k 구간은 삽입정렬로 정렬(O(nk)), 정렬된 n/k 구간은 선택트리 기반 병합으로 O(n log(n/k))에 처리하며, 전체를 O(n log n)으로 유지하는 최적 분기 크기는 k = Θ(log n) • 역순쌍과 시간복잡도: 역순쌍은 i |
||
|
[3강] 함수의 증가 (1)
|
0:
48:
15
|
|
|
함수의 증가와 점근 표기 연습문제 핵심 정리
• 점근 표기 개념 체계: Big-O·Big-Ω·Big-Θ·small-o·small-ω 및 두 변수 Big-O/Ω/Θ 정의를 상수 c, n₀, m₀ 구성 관점에서 정리하고, max·합·상수 이동에 대한 점근 등가 관계(예: max{fₙ,gₙ} = Θ(fₙ+gₙ), (n+a)ᵇ = Θ(nᵇ), 2^{n+1} = Θ(2^n), 2^{2^n} ∉ O(2^n))를 제시함 • 다항식적 한정 판정: f(n) ≤ Cnᵏ 형태의 polynomially bounded 정의를 로그 변환( log f(n) ≤ log C + k log n )으로 해석하고, log n!, ⌈log n⌉, log((⌈log n⌉)!), log((⌈log log n⌉)!)의 성장(Θ(n log n), Θ(log n), Θ(log n·log log n), Θ(log log n·log log log n))을 이용해 다항식적 한정 여부를 구분함 • 로그·반복로그 비교 구조: 반복 로그 log* n 정의(최소 반복 횟수)와 log(log* n), log*(log n)의 구성 차이를 통해 log(log* n) ≪ log*(log n) ≪ log* n의 성장 위계를 정리하고, 로그·팩토리얼·반복로그 조합에서 차수 비교를 통한 점근적 크기 판단 원리를 제시함 |
||
|
[4강] 함수의 증가 (2)
|
0:
44:
04
|
|
|
황금비와 피보나치수, 점근적 증가율 정리 핵심
• 황금비·켤레수·피보나치수 닫힌형 공식: 황금비와 켤레수의 방정식 x²=x+1 성질을 이용해 피보나치 점화식을 Binet formula 형태로 귀납적으로 증명하고, 점화식과 귀납법·루프·재귀 구조의 논리적 동일성 정리 • 로그·지수 변환과 점근적 분석: 밑 변환과 b^{log_a c}=c^{log_a b} 규칙으로 n^{1/ log n}, 4^{log n} 등 복잡한 식을 상수·로그·다항·지수 형태로 환원하여 크기 비교와 성장 차수 분류 수행 • 함수 계층 구조와 상한·하한 개념: 이중지수–지수–팩토리얼–다항–로그–iterated log–상수까지 30개 함수의 점근적 증가 순서를 동치류로 분류하고, 어떤 함수의 big-O도 big-Ω도 되지 않는 짝수·홀수 기반 반례 함수 구성 원리 제시 |
||
|
[5강] 분할정복 (1)
|
0:
57:
04
|
|
|
분할정복 최대 부분배열과 Strassen 행렬곱 핵심 정리
• 최대 부분배열 알고리즘: 모든 원소 음수 시 최댓값 단일 원소 선택, brute force의 Θ(n²) 탐색과 Kadane 선형시간(Θ(n)) 비재귀 알고리즘 구조 비교 • Strassen 행렬 곱셈: 2×2 블록 분할과 7회 재귀 곱셈, 덧셈·뺄셈 Θ(n²) 연산을 결합한 재귀 구조와 점화식 T(n)=7T(n/2)+Θ(n²)의 구현 관점 정리 • Master 정리·3×3 분할 분석: T(n)=kT(n/3)+Θ(n²)에서 k에 따른 세 경우 분류, Strassen보다 빠른 조건 f(n)=o(n^{log₂7})를 만족하는 k≤21 범위 및 small o 정의 정리 |
||
|
[6강] 분할정복 (2)
|
0:
47:
49
|
|
|
점화식 해석과 치환법·마스터 정리·재귀트리 요약
• 점화식 해석 기초: 단순 선형 점화식 전개, 빅-O/빅-Ω/빅-Θ 정의와 치환법(귀납법) 구조를 통한 점근식 증명 • 분할정복 점화식 분석: 마스터 정리 3가지 경우, 저차항 보정이 포함된 치환법, 재귀트리에 의한 깊이·레벨별 비용 분석과 일반 비대칭 분할(α, 1−α)에서 T(n)=Θ(n log n) 도출 • 알고리즘 성능 비교 응용: 재귀트리로 T(n)=T(n/3)+T(2n/3)+cn의 하한/상한 평가, 행렬 곱셈 점화식 T(n)=A T(n/4)+O(n²)에서 n^{log_b a} 지수 비교로 Strassen보다 빠른 조건(A≤48) 도출 |
||
|
[7강] 확률적 분석과 랜덤화된 알고리즘 (1)
|
0:
36:
41
|
|
|
확률적 분석과 랜덤 알고리즘: 바이어스 코인, 고용 문제, 지표확률변수 활용 개념 정리
• 공정한 코인 생성 알고리즘: 바이어스 확률 p 서브루틴을 두 번 호출해 x≠y일 때만 반환하는 방식으로 공정한 코인 구성, 성공 확률 2p(1-p)와 기대 수행시간 1/(2p(1-p)) 도출 • 고용 알고리즘 확률 분석: 순열 모델에서 1번·N번·2번 고용 확률을 조건부 확률로 계산하고, 두 번 고용 확률을 조화수 H_{N-1}/N 형태로 표현 • 지표 확률 변수와 기대값 선형성: 모자 검사 문제의 E[X]=1과 랜덤 순열 inversion 수의 기대값 N(N-1)/4를 지표 변수 정의와 선형성, 대칭성을 이용해 계산하는 방법 정리 |
||
|
[8강] 확률적 분석과 랜덤화된 알고리즘 (2)
|
0:
49:
46
|
|
|
Summary Content:
• 랜덤 아이즈 인 플레이스 알고리즘: i..n 구간 교환과 수정된 초기 조건(선행 무작위 교환)을 통한 루프 불변성 수립으로 모든 순열을 동일 확률로 생성하는 균등 임의 순열 셔플 절차 • 잘못된 셔플·순열 알고리즘 반례: i+1..n 범위 교환, 1..n 전체 범위 반복 교환, 단일 순환 이동(Permute-by-Cyclic) 알고리즘이 생성 가능한 순열 수 축소 또는 순열별 확률 불균등을 초래함을 경우의 수와 확률 계산으로 검증 • 재귀적 균등 임의 표본 추출 알고리즘: Random-Sample(m,n)의 종료 조건·귀납 구조와 조합론적 관계 {n \choose m},{n-1 \choose m-1}를 이용해 각 원소 포함 확률 P(i∈S)=m/n과 크기 m 부분집합들의 균등 분포를 증명하는 m-표본 생성 절차 |
||
| 2장. 정렬과 순서 통계량 | ||
|
[9강] 힙 정렬 (1)
|
0:
57:
35
|
|
|
힙의 높이·원소수·시간복잡도와 증명
• 완전 이진트리 기반 힙 구조: 높이 H의 힙에서 원소수 범위 $2^H \sim 2^{H+1}-1$, 원소수 N에 대한 힙 높이 $h=\lfloor \log N \rfloor$, 리프·내부노드 수 관계(리프 수 $\lceil N/2 \rceil$ 등) 정리 • 최대 힙 성질과 서브트리 구조: 부모 키 ≥ 자식 키 정의, 모든 서브트리 루트의 최대값 성질(모순 증명), 높이 h인 노드 개수 상한 $\left\lceil \dfrac{N}{2^{h+1}} \right\rceil$의 포화트리·완전이진트리·수학적 귀납법 증명 • Max-Heapify 알고리즘과 시간복잡도: 배열 인덱스 기반 자식 계산(2i, 2i+1), 부모–자식 비교·교환을 통한 서브트리 최대 힙 정렬 절차, 재귀 깊이와 힙 높이 분석을 통한 $\Theta(\log N)$ 시간복잡도 도출 및 우선순위 큐·힙 정렬의 이론적 근거 정리 |
||
|
[10강] 힙 정렬 (2)
|
0:
44:
56
|
|
|
힙 정렬과 최대 힙 연산, 빌드 힙 방법 비교 요약
• 힙 정렬(Heap Sort) 및 힙 구조: 완전 이진 트리 기반 최대 힙에서 Build-Max-Heap과 Max-Heapify를 이용해 배열을 정렬하며, 높이 Θ(log n)에 의해 전체 정렬 시간 Θ(n log n)과 비안정 정렬 특성을 가짐 • 최대 힙 연산(Max-Heap Insert, Heap-Increase-Key): 배열 인덱스 기반 부모·자식 관계를 이용해 새 원소 삽입 시 Heap-Increase-Key로 키를 위로 전파하고, 교환 대신 부모 값을 아래로 복사 후 최종 위치에 한 번만 key를 대입하는 방식으로 할당 연산을 최적화함 • 힙 구성 알고리즘(Build-Max-Heap, Build-Max-Heap′): 배열 하향식 Max-Heapify 방식(Build-Max-Heap)과 반복 삽입 기반 방식(Build-Max-Heap′)이 서로 다른 힙을 생성할 수 있으나, 둘 모두 Max-Heap Insert·Heap-Increase-Key 비용 합 분석을 통해 Θ(n log n) 시간 복잡도를 가지며 비교 정렬 하한과 일치함 |
||
|
[11강] 퀵 정렬 (1)
|
0:
49:
01
|
|
|
퀵정렬 최악·평균·최적 시간복잡도와 분할 불균형 분석
• 퀵정렬 최악 시간복잡도: 이미 정렬·역정렬 배열에서 비랜덤 pivot 사용 시 점화식 T(n)=T(n−1)+Θ(n)을 통해 Θ(n²) 수행시간 도출 • 분할 비율·재귀 깊이·랜덤화: 고정 분할 비율 1−α:α에서 최소·최대 재귀 깊이 −log n/logα, −log n/log(1−α)로 근사하고, 랜덤 pivot 선택으로 평균 분할을 보장해 기대 시간복잡도 Θ(n log n) 확보 • 최적 분할·시간복잡도 하한: q와 n−q−1이 같을 때(q=(n−1)/2) T(q)+T(n−q−1)가 최소가 되어 항상 반씩 분할되는 이상적 퀵정렬을 정의하고, 점화식·치환법·미분을 통해 수행시간 하한 Ω(n log n) 증명 |
||
|
[12강] 퀵 정렬 (2)
|
0:
41:
08
|
|
|
퀵정렬 종합문제: 동일 원소 처리와 스택 깊이 분석
• 동일 원소 처리 퀵정렬(Partition′·QuickSort′) : 동일 값 구간을 피벗 블록으로 묶어 세 구간 분할 후 서로 다른 값들만 재귀 정렬하여 평균 수행시간 Θ(n log n) 유지 • 테일 재귀 퀵정렬 구조 : 한쪽 부분배열만 재귀 호출하고 나머지는 while 루프로 반복 처리하여 호출 구조를 단순화하되 정렬 결과와 시간 복잡도는 표준 퀵정렬과 동일하게 유지 • 스택 깊이 분석 및 최적화 : 최악 치우친 분할 시 스택 깊이 Θ(n) 발생, 분할 후 작은 쪽만 재귀·큰 쪽 반복 처리 전략으로 재귀 깊이를 O(log n)으로 제한하여 스택 사용 Θ(log n) 달성 |
||
|
[13강] 선형 시간 정렬 (1)
|
0:
57:
10
|
|
|
선형시간 정렬과 결정트리 하한, 계수·기수정렬 연습문제 정리
• 비교 기반 정렬 하한·부분집합/블록 입력 하한: 결정트리 모형·리프 개수·로그 하한을 이용한 $\Omega(n\log n)$·$\Omega(n\log k)$ 증명 및 부분 집합 입력에 대한 선형시간 비교정렬 불가능성 정리 • 계수정렬·빈도 누적 구조: 계수정렬의 동작 원리·순회 방향과 안정성 관계·누적 카운트 배열을 이용한 구간 빈도 상수시간 질의 기법 정리 • 안정성·기수정렬와 선형시간 정렬 설계: 불안정 정렬의 (키, 인덱스) 튜플 안정화, 기수정렬의 귀납적 정확성과 안정성 필요 조건, 범위 $[0,n^3-1]$ 정수 $n$개를 기수 $n$·3자리 표현으로 $O(n)$에 정렬하는 방법 정리 |
||
|
[14강] 선형 시간 정렬 (2)
|
1:
03:
14
|
|
|
버킷정렬의 최악 수행시간과 비교정렬의 확률적 하한 요약
• 버킷정렬 성능 특성: [0,1) 구간 실수 입력을 버킷에 분배하는 구조로 평균 시간 O(n)을 가지나, 모든 원소가 한 버킷에 몰리고 내부 정렬이 Insertion sort일 때 전체 최악 시간이 Θ(n²)이 됨 • 버킷정렬 최악 시간 개선: 버킷 내부 정렬을 Merge sort 등 O(m log m) 분할정복 정렬로 교체하고, 작은 m 구간에서는 Insertion sort를 쓰는 하이브리드 전략으로 최악 수행시간을 O(n log n)으로 개선함 • 비교정렬 결정트리 하한: 비교정렬을 리프 n!개를 가지는 결정트리로 모델링하고 외부 경로 길이 최소값 d_k = Ω(k log k)를 증명하여 평균 비교 횟수 하한이 Ω(n log n)임을 보이며, 랜덤화 비교정렬도 동등한 결정론적 트리로 환원되어 이 하한을 넘을 수 없음 |
||
|
[15강] 중앙값과 순서 통계량 (1)
|
0:
30:
41
|
|
|
중앙값과 순서 통계량, Select 알고리즘과 퀵정렬 응용 요약
• 순서 통계량 및 두 번째 최소 원소: 비교 결정 트리를 통한 최솟값·후보 집합 구조 분석, 두 번째 최소 원소 탐색의 최악 비교 횟수 상한 n + ⌈log n⌉ - 2 도출 • Select 알고리즘과 그룹 크기: 메디안 오브 메디안 기반 선형시간 선택 알고리즘 구조, 그룹 크기 3·5·7에 따른 점화식과 시간복잡도 비교(3개: O(n log n), 5·7개: O(n)) 및 피벗 품질-비용 트레이드오프 • 중앙값 활용 정렬·선택 알고리즘: 중앙값 기반 피벗 선택으로 퀵정렬 최악 시간 O(n log n) 보장, 중앙값 블랙박스 서브루틴을 이용한 임의 i번째 순서 통계량 선형시간 선택 알고리즘 설계 및 점화식 T(n) 분석 |
||
|
[16강] 중앙값과 순서 통계량 (2)
|
0:
37:
10
|
|
|
Summary Content:
• 두 정렬 배열 중앙값 알고리즘: 두 정렬 배열의 작은 중앙값 위치 조건을 부등식으로 정의하고 이진 탐색을 적용하여 전체 중앙값을 O(log n)에 찾는 알고리즘과 점화식 T(n)=T(n/2)+Θ(1) 분석 • 중앙값과 절댓값 합 최소화: 유전의 y좌표 중앙값(홀수는 단일 중앙값, 짝수는 중앙값 구간)이 수직 거리 절댓값 합을 최소화함을 보이고, 선형시간 selection으로 최적 송유관 위치를 결정하는 구조 • 상위 i개 원소 선택 알고리즘: 전체 정렬, 최대 힙, 선형시간 selection+partition+부분정렬의 복잡도 Θ(N log N), Θ(N + i log N), Θ(N + i log i)를 비교하여 상위 i개 선택의 최적 알고리즘 구조 정리 |
||
| 3장. 자료구조 | ||
|
[17강] 기본 자료구조 (1)
|
0:
49:
11
|
|
|
기본 자료구조 응용: 스택과 큐 구현 및 오버/언더플로우 개념 정리
• 배열 기반 스택·큐 확장 구현: 한 배열로 두 스택 구현, 원형 큐 및 양방향 큐(Deque)의 head·tail 포인터 구조와 오버플로우·언더플로우 판정 조건 정리 • 스택·큐 상호 구현: 두 스택으로 큐 구현, 두 큐로 스택 구현 알고리즘과 보조 구조 활용에 따른 연산 절차 및 순서 유지·역전 메커니즘 정리 • 수행 시간·분할상환 분석: 각 연산의 최악 시간복잡도와 분할상환 분석을 통한 평균 성능, 숨겨진 상수 계수 차이를 고려한 구현 효율성 비교 |
||
|
[18강] 기본 자료구조 (2)
|
0:
49:
51
|
|
|
Summary Content:
• 단순 연결 리스트 스택·큐 구현: 스택은 top 포인터 하나, 큐는 head·tail 포인터 두 개로 LIFO/FIFO 구조를 표현하며 push/pop, enqueue/dequeue 연산을 포인터 갱신으로 상수시간 O(1)에 수행 • 단순 연결 리스트 역순 변환(비재귀): p·q·r 세 포인터로 다음 노드 보존, 링크 방향 반전, 역순 리스트의 head 갱신을 반복하여 모든 노드를 한 번씩 방문하는 O(n) iterative reverse 알고리즘 구성 • 이진트리 순회 알고리즘: 전위·중위·후위 재귀 순회에서 각 노드를 한 번만 방문하여 O(n)에 처리하고, 스택 기반 비재귀 중위순회는 왼쪽 경로 push, nil 시 pop·출력 후 오른쪽 이동 패턴으로 각 노드당 push/pop/print 1회 수행해 O(n) 보장 |
||
|
[19강] 해시 테이블 (1)
|
1:
09:
44
|
|
|
해시 테이블 대용량 배열, 검증순환, 자유리스트, 충돌 기댓값 정리
• 검증순환 직접 주소사전: 대용량 배열 T와 스택 S,S'의 상호 참조 구조로 키 검증순환을 형성하여 초기화·탐색·삽입·삭제를 모두 상수시간에 수행하는 직접 주소사전 구현 방식 • 체인 해싱과 자유리스트: 해시 테이블 슬롯과 양방향 자유리스트를 결합한 체인 해싱 구조에서 체인 헤드 유지, 슬롯 복사 및 포인터 갱신으로 탐색·삽입·삭제를 평균 상수시간에 수행하는 메모리 관리 기법 • 해싱 성능·취약성 분석: 단순 균등 해싱에서 충돌 횟수 기댓값 n(n-1)/(2m) 유도와 랜덤 브러시 검색 평균 시간 분석, 문자열 해시 h(k)=k mod (2^p-1)의 자리 교환 불변성으로 인한 구조적 충돌 발생 문제 정리 |
||
|
[20강] 해시 테이블 (2)
|
0:
45:
28
|
|
|
해시 체이닝에서 최대 체인 길이의 기대값과 저장공간 추정
• 해시 체이닝 모델과 충돌 분포: 균등 랜덤 해싱 가정에서 슬롯별 체인 길이를 이항분포로 정의하고, 특정 슬롯에 K개가 해싱될 확률 Q_K 및 최대 체인 길이 M의 분포 P_K를 설정 • 최대 체인 길이 확률 상계: Union Bound로 P_K ≤ NQ_K를 얻고, 조합식과 스털링 근사로 Q_K ≤ (2/K)^K를 도출한 뒤, K_0 = C·log N / log log N 선택으로 Q_{K_0} ≤ 1/N^3, P_{K_0} ≤ 1/N^2를 만족하도록 상수 C를 설정 • 최대 체인 길이 기대값과 저장공간 추정: E[M] = ∑K P_K를 K_0 기준으로 분할해 E[M] ≤ K_0 + 1을 증명하고, E[M] = O(log N / log log N)을 통해 체이닝 기반 해시 테이블의 최대 체인 길이 기대 상한과 필요한 저장공간 규모를 점근적으로 추정 |
||
|
[21강] 이진 검색 트리 (1)
|
0:
48:
25
|
|
|
이진검색트리와 최소힙, 순회 알고리즘, 비교모델 정렬 하한 핵심 정리
• 이진검색트리와 최소힙 구조 비교: BST는 전역 순서(왼쪽<루트<오른쪽)로 중위순회 시 정렬 결과 제공, 최소힙은 부모≤자식 관계만 보장해 단순 순회만으로 정렬 순서 출력 불가 • 트리 순회와 정렬 하한: 전위·중위·후위·Tree-Minimum+Successor 기반 중위순회는 모든 노드를 한 번씩 방문하므로 Θ(n) 시간, 비교모델에서 BST 구성+중위순회에 의한 정렬은 Ω(nlogn) 하한을 가져 BST 구성 비용이 정렬 복잡도를 지배 • 직전·직후 원소 구조 특성: 두 자식을 가진 노드에서 직전원소는 왼쪽 서브트리 최대 키(오른쪽 자식 없음), 직후원소는 오른쪽 서브트리 최소 키(왼쪽 자식 없음)로 정의되어 삭제 연산 등 BST 조작 알고리즘의 기본 구조 제약 형성 |
||
|
[22강] 이진 검색 트리 (2)
|
0:
39:
58
|
|
|
이진 검색 트리와 기수트리를 이용한 정렬과 시간복잡도 비교
• 이진 검색 트리와 Tree Sort: 삽입·검색 시 비교 횟수 관계(검색 = 삽입 + 1), Tree Sort의 최적/최악 시간복잡도(균형 트리 시 Θ(n log n), 편향 트리 시 Θ(n²)) 및 균형 이진 검색 트리(레드–블랙 트리)의 필요성 정리 • 사전식 순서 정의: 두 문자열의 처음 달라지는 위치에서의 문자 크기 비교(조건 1)와 접두사(prefix) 관계에서 짧은 문자열이 더 작은 것으로 정의하는 두 가지 기준 제시 • 기수트리와 사전식 정렬: 비트 기반 기수트리 구조(0→왼쪽, 1→오른쪽)에서 부모-자식 및 왼쪽-오른쪽 서브트리의 사전식 대소 관계를 이용해, 전체 비트 길이 n에 대해 Θ(n) 시간에 전위 순회로 사전식 정렬을 수행하는 알고리즘 요약 |
||
|
[23강] 레드블랙 트리 (1)
|
0:
45:
36
|
|
|
레드블랙트리 연습문제 핵심 정리와 삽입/회전 성질 요약
• 레드블랙트리 구조·높이 특성: 5가지 기본 특성, 루트 색 완화와 블랙 높이 불변, 적색 노드 병합 시 부모 차수(2~4)와 경로 길이 범위(BH ≤ L ≤ 2BH)로 균형성과 깊이 상한 분석 • 이진검색트리 회전 변환: 임의 BST의 우편형 트리(right spine) 변환과 우회전 횟수 상한 N-1, 두 BST(T1, T2)를 공통 spine을 통해 O(N)번 회전으로 상호 변환 가능함을 증명 • RB-Insert-Fixup 불변식: 삽입 후 회전·색변경이 블랙 높이(특성 5)를 보존함을 서브트리 BH 동형성으로 증명하고, sentinel t.nil은 BLACK이어야 while 조건과 루트 BLACK 불변식이 유지됨을 통해 t.nil.color=RED 주장을 반박 |
||
|
[24강] 레드블랙 트리 (2)
|
0:
51:
19
|
|
|
Summary Content:
영속적 레드블랙 트리와 삭제/삽입 특성 요약 • 레드블랙 트리 보정 특성: RB-DELETE-FIXUP case 1에서 부모는 항상 흑색이어야 하며, RB-INSERT 후 동일 노드 RB-DELETE 시 색상·구조가 달라질 수 있음을 통해 레드블랙 트리의 색·회전 기반 균형 유지 원리 제시 • 영속 BST/레드블랙 트리 구조: 영속 동적집합에서 루트→대상 노드까지 경로상의 노드만 copy-node로 복사하고 나머지 서브트리는 공유하여 삽입·삭제 시 시간·공간 복잡도를 트리 높이 $h$에 비례하도록 유지하는 영속 삽입·삭제 알고리즘 구조 정리 • 부모 포인터 배제와 성능: parent 필드 추가 시 루트 변화마다 전체 서브트리 복사가 필요해 $\Omega(n)$ 비효율이 발생하므로 부모 포인터를 제거하고 탐색 경로를 스택으로 관리하여 영속 레드블랙 트리에서 각 연산을 $O(\log n)$ 시간·공간으로 구현하는 설계 원칙 설명 |
||
|
[25강] 자료구조의 확장 (1)
|
0:
49:
18
|
|
|
순서통계량 트리와 레드블랙 트리 확장 핵심 정리
• 순서통계량 트리와 size 필드: OS-Rank·OS-Select를 이용한 인덱스 기반 탐색, X보다 I번째 뒤 원소 검색, 회전 시 size 국소 갱신 및 배열 역치 개수의 O(n log n) 계산 • 레드블랙 트리의 흑색 높이(black height): 자식 서브트리 기반 흑색 노드 수 필드 유지, 삽입·삭제·회전 시 상수 개 노드만 갱신하여 전체 연산 O(log n) 성능 유지 • 레드블랙 트리의 깊이(depth) 필드: 부모 방향 경로 길이에 의존해 서브트리 이동 시 다수 노드 깊이 재계산이 필요하므로 최악 O(n) 갱신이 발생하여 O(log n) 점근적 성능과 양립 불가능함 |
||
|
[26강] 자료구조의 확장 (2)
|
0:
43:
44
|
|
|
구간 트리와 민갭, 사각형 겹침 검출 알고리즘 핵심 정리
• 구간 트리 최소 low 겹침 탐색: 구간 겹침 조건(x.high ≥ i.low, x.low ≤ i.high) 기반으로 left 서브트리 → 현재 노드 → right 서브트리 중 한 방향만 재귀 탐색하여 겹치는 구간들 중 가장 작은 low를 O(log n)에 탐색하는 구조 • min-gap 지원 동적 집합: 레드블랙트리 각 노드에 min·max·gap 보조 필드를 두고 자식 정보만으로 갱신하여 삽입·삭제·탐색은 O(log n), 전체 집합의 최소 차이값 질의는 root.gap으로 O(1)에 처리하는 자료구조 설계 • 직사각형 겹침 N log N 판별: X좌표 기준 이벤트(왼쪽/오른쪽 변) 정렬 후 스위프 라인으로 진행하며 활성 직사각형의 Y-구간을 구간 트리에 삽입·삭제·겹침 검사하여 직사각형 집합의 겹침 여부를 O(n log n)에 판별하는 알고리즘 구성 |
||
| 4장. 고급 설계 및 분석 기법 | ||
|
[27강] 동적 프로그래밍 (1)
|
0:
38:
44
|
|
|
동적 프로그래밍 예제 심화
• 막대 자르기 동적 계획법: 수행시간 점화식과 2ⁿ 성장 분석, 밀도 기반 그리디 반례, 자르는 비용 c를 포함한 최대수익 점화식, 해(solution) 복원을 위한 값 테이블·선택 테이블 구조 정리 • 피보나치 수 DP와 부분문제 그래프: Fₙ 점화식과 중복계산 제거를 통한 O(n) bottom-up 알고리즘, 정점 수 n+1·간선 수 2n-2인 부분문제 그래프 구조와 시간복잡도 연결 • 행렬 체인 곱 DP 분석: 부분문제 (i,j)와 부분문제 그래프 정의, 정점 수 n(n+1)/2·간선 수 (n³-n)/3 유도, Matrix-Chain-Order 테이블 m[i,j] 참조 횟수 합 R=(n³-n)/3 계산과 O(n³) 시간복잡도 구조 해석 |
||
|
[28강] 동적 프로그래밍 (2)
|
0:
53:
02
|
|
|
동적 계획법 연습문제: 행렬 곱, 막대 자르기, 환전, LCS 메모리 최적화 개념 정리
• 행렬 곱 분할 정복 알고리즘: 카탈란 수 기반 모든 과로 열거와 재귀 Matrix-Chain의 시간 복잡도(지수 시간, O(n·3^{n-1})) 비교 및 DP O(n^3) 필요성 정리 • 최적 부분 구조 반례 사례: 조각 개수 제한이 있는 막대 자르기와 수수료 C_K>0 환전 문제에서 전역 제약으로 인한 부분 문제 비독립성 및 최적 부분 구조 붕괴 원리 • LCS 메모리 최적화: c[i][j]의 3방 의존 구조를 이용한 2행 또는 1행+보조 변수 구현과 공간 복잡도 O(mn)→O(min(m,n)) 감소 기법 정리 |
||
|
[29강] 동적 프로그래밍 (3)
|
0:
39:
35
|
|
|
깔끔한 인쇄 동적 프로그래밍 알고리즘 요약
• 깔끔한 인쇄 문제: 고정폭/가변폭 폰트에서 줄 폭 M 내 단어 배치 시 여분 공간(ex(i,j))을 정의하고, 마지막 줄 제외 각 줄 여분 공간 세제곱 합을 최소화하는 줄 나누기 최적화 문제 • 동적 프로그래밍 구조: 라인 비용 lc(i,j) (초과 시 ∞, 마지막 줄 0, 그 외 ex(i,j)^3)을 사용해 c(j)=min_{1≤i≤j}{c(i−1)+lc(i,j)} 점화식으로 최적 부분 구조를 구현하고, ex[i][j], lc[i][j], c[j], p[j] 배열을 통해 O(n²) 시간·O(n²) 공간에 최적 해 및 줄 경계 복원 • 구현 및 확장: ex[i][j]=ex[i][j−1]−1−L_j 관계로 여분 공간을 효율 계산하고, p[j]를 재귀적으로 추적해 실제 줄을 출력하며, 고정폭의 단어 길이 L_i를 가변폭 폰트의 픽셀 기반 단어 폭 W_i로 치환해 동일 알고리즘을 프로포셔널 폰트로 확장 가능 |
||
|
[30강] 그리디 알고리즘 (1)
|
0:
47:
06
|
|
|
활동선택 문제와 그리디·동적프로그래밍 비교 정리
• 활동선택 문제와 동적 프로그래밍: 구간 활동의 양립 가능 조건을 기반으로 Cij·Vij 점화식과 널 부분문제 정의, O(n³) 시간복잡도를 갖는 최적해 탐색 구조 정리 • 최적 그리디 전략과 반례: 종료시간 오름차순·시작시간 역방향 선택 그리디의 최적성, 최소 길이·최소 겹침 수 그리디 전략이 실패하는 카운터 예제와 그리디 적용 조건 정리 • 변형 문제 확장: 강의실 배정의 인터벌 그래프 색칠 모델과 스위핑 기반 O(n)~O(n log n) 알고리즘, 가치가 있는 활동선택의 최대 가치 동적 프로그래밍 구조 정리 |
||
|
[31강] 그리디 알고리즘 (2)
|
0:
32:
26
|
|
|
0-1 배낭 문제와 그리디 및 분할 가능한 배낭, 최대 수당 문제 요약
• 0-1 배낭 동적 계획법: 부분문제 C(i,w) 정의와 경계 조건, “i번째 물건 포함/비포함” 최대값 점화식으로 O(NW) 테이블 계산 • 그리디 최적화 문제들: 물통(생수 리필)에서 도달 가능한 최원 지점 선택 O(n) 알고리즘과 분할 가능한 배낭의 median+partition 기반 O(n) 해법, 정렬된 두 정수 집합 수당 최대화를 위한 오름차순 매칭 전략 • Huffman 코딩 보조정리 16.2: 네 원소 a,b,x,y의 빈도 비교를 통한 최저 빈도 동치 조건 증명과 Huffman 트리 구성 시 빈도 순서 성질 확인 |
||
|
[32강] 분할상환 분석
|
0:
49:
25
|
|
|
분할상환 분석 응용: 총괴분석·결산법·잠재함수 사례 정리
• 분할상환 분석 기초 개념: 총괴분석·결산법·잠재함수를 사용해 연산 시퀀스의 평균 비용을 상계하고, 특정 위치에서만 큰 비용이 드는 연산·주기적 스택 사본 복사·비트 카운터 Increment/Reset의 연산당 분할상환 비용을 O(1) 또는 O(log n)으로 분석 • 결산법 및 카운터/스택 응용: 스택 Push/Pop 및 주기적 전체 복사, 비트 카운터 Increment/Reset에서 0→1 전환 시 크레딧 적립·1→0 전환 및 Reset·복사 시 크레딧 사용 구조로 전체 N회 연산 비용을 O(N)으로 만드는 크레딧 설계 • 이진 최소힙 잠재함수 분석: 힙 원소 수 N에 대해 잠재함수 Φ(D)=K·N·log N을 정의하고 Insert의 실제 O(log N) 비용을 유지하면서 분할상환 O(log N), Extract-Min의 실제 O(log N) 비용을 잠재함수 감소로 상쇄하여 분할상환 O(1) 달성 |
||
| 5장. 고급 자료구조 | ||
|
[33강] 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로 트리 높이를 로그 규모로 제한해 노드=디스크 블록 매핑 시 수회 디스크 액세스로 기가~테라바이트급 데이터 인덱싱 가능함 |
||
|
[34강] 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 기준 삭제 시 분할 대신 형제 차용·병합·부모 키 포함 병합 규칙과, 기존 키 재삽입 등 구조 변화 없을 때 디스크 리드/라이트 생략 조건 정리 |
||
|
[35강] 서로소 집합의 자료구조 (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 핵심 아이디어 요약 |
||
|
[36강] 서로소 집합의 자료구조 (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장. 그래프 알고리즘 | ||
|
[37강] 기본 그래프 알고리즘 (1)
|
0:
49:
23
|
|
|
그래프의 유니버설 싱크와 연결행렬, BFS 특성 정리 요약
• 유니버설 싱크와 판별 알고리즘: 유니버설 싱크(모든 정점에서 들어오고, 나가는 간선 0인 정점) 정의·유일성·존재 조건과, 인접행렬에서 행·열 제거 규칙을 이용한 O(V) 시간 판별 및 검증 절차 정리 • 방향 그래프 연결행렬과 BBᵀ: 방향 그래프의 연결행렬 B 정의(정점-간선 관계를 -1,0,1로 표현)와 BBᵀ의 대각 성분이 각 정점 차수, 비대각 성분이 정점 쌍 간 간선 수의 음수를 의미함을 구조적으로 해석 • BFS 색 단순화와 인접리스트 순서 영향: BFS에서 화이트/넌-화이트 2상태만으로 방문 관리가 충분함을 보이고, 인접리스트 순서가 최단 거리값(u.d)에는 영향을 주지 않으나 BFS 트리의 부모-자식 구조와 모양에는 영향을 미치는 성질 정리 |
||
|
[38강] 기본 그래프 알고리즘 (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 형태의 전체 시간구간 포함 관계가 필요함을 강조 |
||
|
[39강] 기본 그래프 알고리즘 (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) 시간 수행 |
||
|
[40강] 기본 그래프 알고리즘 (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 등 거리 부등식을 만족해 계층 구조와 최단거리 성질을 규정함 |
||
|
[41강] 최소 신장 트리
|
0:
46:
19
|
|
|
최소 신장트리 연습문제: 절단, 경량 간선, 알고리즘 응용
• 최소 신장트리 이론: 절단과 경량 간선 정리, 최소 가중치 간선 포함 조건, 경량 간선 집합의 한계, 유일한 경량 간선과 MST 유일성 및 역명제 반례 정리 • 가중치 변화와 MST 유지: MST 간선 가중치 감소 시 최적성 보존 증명, 절단 기반 비교와 두 경우 분할(간선 포함/비포함)에 의한 최소성 보장 구조 • MST 알고리즘 복잡도 개선: 정수 가중치 범위가 제한된 경우 Kruskal의 개수 정렬 활용과 Prim의 Van Emde Boas 트리·버킷/해시 구조 적용을 통한 시간 복잡도 감소 기법 |
||
|
[42강] 단일 출발지 최단 경로 (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회 수행을 통한 결과 검증 절차, 최단경로 간선이 경로 순서대로 완화된다는 주장에 대한 반례 그래프 분석 |
||
|
[43강] 단일 출발지 최단 경로 (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로 해 계산 및 음의 가중치 순환에 의한 일관성·언바운디드성 판정 |
||
|
[44강] 단일 출발지 최단 경로 (3)
|
0:
37:
49
|
|
|
벨만-포드와 음의 가중치 순환, 중재이익 탐지 요약
• 벨만-포드와 음의 가중치 순환 판별: 완화 연산과 이전정점 배열(π)의 의미, s.π ≠ nil 조건에 의한 음의 가중치 순환 존재 판정, 음의 순환이 없을 때 |V|-1회 유효 완화로 형성되는 최단경로 트리 구조 정리 • 음의 가중치 순환과 완화 단계 특성: 출발점에서 도달 가능한 음의 가중치 순환 존재 시 무한히 많은 유효 완화 단계 열 구성 원리, 순환 가중치 w(C) < 0에 기반한 d 값의 반복 감소와 수학적 귀납 증명 구조 요약 • 환율 그래프와 중재이익 탐지 알고리즘: 통화를 정점, 환율 r_ij를 간선으로 하는 그래프와 w(i,j) = -log r_ij 변환, 음의 가중치 순환 ↔ 중재이익 사이클 동치성, 벨만-포드 기반 존재 여부 판정 및 실제 환전 순서(사이클) 복원, 전체 시간 복잡도 O(n^3) 정리 |
||
|
[45강] 모든 쌍의 최단 경로 (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*)) 시간복잡도를 도출 |
||
|
[46강] 모든 쌍의 최단 경로 (2)
|
0:
26:
44
|
|
|
플로이드-워셜, 음의 가중치 순환, 존슨 알고리즘 조정 방식 비교 요약
• 플로이드-워셜 알고리즘 최적화: 위첨자 배열 없이 단일 거리 행렬 in-place 갱신으로 모든 단계 거리 갱신을 수행하여 공간 복잡도를 O(n³)에서 O(n²)로 감소시키는 원리 정리 • 음의 가중치 순환 탐지: 플로이드-워셜 최종 거리 행렬의 대각원소 dᵢᵢ 값으로 음의 가중치 순환 존재 여부를 필요충분조건으로 판정하는 기준 및 해석 구조 • 존슨 알고리즘 재가중치 원리: 최소 가중치 일괄 보정의 오류와 h-함수 기반 w'(u,v)=w(u,v)+h(u)-h(v) 재가중치 비교, 임의 출발점 사용 시 실패 원인과 강한 연결 그래프에서의 올바른 동작 조건 정리 |
||
|
[47강] 최대 플로우 (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인지 검사하는 문제로 환원하는 모델링 절차 |
||
|
[48강] 최대 플로우 (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′를 합친 증강플로우는 플로우 보존은 유지하지만 간선 용량을 초과할 수 있어 용량 제약은 일반적으로 만족하지 않음을 설명 |
||
|
[49강] 최대 플로우 (3)
|
0:
53:
44
|
|
|
Summary Content:
• 간선 연결성 및 플로우 네트워크 변환: 무방향 그래프를 용량 1의 방향 플로우 네트워크로 변환하고, 한 소스에서 모든 싱크로의 최대 플로우 값 최소값으로 간선 연결성을 정의·계산함 • 최대 플로우–최소 절단 및 플로우 조정: 간선 연결성과 최대 플로우·최소 절단 용량의 등가 관계를 증명하고, 순환 경로를 따라 역방향 플로우를 제거해도 전체 최대 플로우를 보존하는 플로우 조정 알고리즘을 정리함 • 최소 절단 중 최소 간선수 선택 기법: 각 간선 용량에 작은 보상값을 더하고 정수 스케일링하여, 플로우 알고리즘 한 번으로 최소 용량 절단들 중 교차 간선수가 최소인 절단을 찾는 용량 재가중 방법을 제시함 |
||
|
[50강] 최대 플로우 (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)$ 시간에 새로운 최대 플로우 계산 |
||
신흥철 교수님
알고리즘 문제풀이 통합과정
