홈 > 강의소개
알고리즘 문제풀이Ⅰ
신흥철 교수
KAIST 대학원 전산학부 석사과정
KAIST 대학원 전산학부 박사졸업
KAIST 대학원 전산학부 석사과정
KAIST 대학원 전산학부 박사졸업
숙명여자대학교
Microsoft
현) 유니와이즈 전임교수
AI가 이끄는 스마트한 학습 경험, AI 튜터와 함께 더 빠르고, 더 깊게 학습하세요.
긴 강의 내용을 AI가 핵심만 요약하여 복습 시간을 단축시킵니다.
강의에서 가장 중요한 키워드와 개념을 자동으로 추출해 제공합니다.
학습한 내용을 바탕으로 AI가 생성한 퀴즈를 풀며 이해도를 점검합니다.
모르는 부분을 24시간 언제든 AI 튜터에게 질문하고 답변을 받습니다.
총 4개 챕터, 32강으로 구성되어 있습니다.
| 제목 | 강의시간 | 상세내용 |
|---|---|---|
| 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:
45
|
|
|
이진검색트리와 최소힙, 순회 알고리즘, 비교모델 정렬 하한 핵심 정리
• 이진검색트리와 최소힙 구조 비교: 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) 달성 |
||
신흥철 교수님
알고리즘 문제풀이Ⅰ
