홈 > 강의소개
알고리즘 통합과정
신흥철 교수
KAIST 대학원 전산학부 석사과정
KAIST 대학원 전산학부 박사졸업
KAIST 대학원 전산학부 석사과정
KAIST 대학원 전산학부 박사졸업
숙명여자대학교
Microsoft
현) 유니와이즈 전임교수
AI가 이끄는 스마트한 학습 경험, AI 튜터와 함께 더 빠르고, 더 깊게 학습하세요.
긴 강의 내용을 AI가 핵심만 요약하여 복습 시간을 단축시킵니다.
강의에서 가장 중요한 키워드와 개념을 자동으로 추출해 제공합니다.
학습한 내용을 바탕으로 AI가 생성한 퀴즈를 풀며 이해도를 점검합니다.
모르는 부분을 24시간 언제든 AI 튜터에게 질문하고 답변을 받습니다.
총 7개 챕터, 145강으로 구성되어 있습니다.
| 제목 | 강의시간 | 상세내용 |
|---|---|---|
| 1장. 기초 | ||
|
[1강] 알고리즘의 역할
|
0:
10:
02
|
|
|
Summary Content: 알고리즘의 정의와 특성, 성능 측정과 성능 분석 개념 정리• 알고리즘 기본 개념: 입력을 출력으로 변환하는 명확·유한·유효한 단계적 절차 정의와 입력·출력 구조 정리 • 알고리즘 품질 평가: correctness(타당성) 증명과 efficiency(효율성) 분석의 두 관점 및 품질 비교 기준 제시 • 성능 평가 방법: 환경 의존적 성능 측정과 입력 크기 기반 시간 복잡도 중심 성능 분석의 개념·차이·한계 정리
|
||
|
[2강] 삽입 정렬. 알고리즘의 분석
|
0:
51:
35
|
|
|
알고리즘 타당성과 수행시간 분석 – 삽입정렬을 중심으로• 삽입정렬 알고리즘 구조: 배열 A[1..n]에서 앞부분 A[1..j−1]을 정렬구간으로 유지하며 key = A[j]를 적절한 위치에 삽입하고 while 루프로 원소를 이동시키는 절차 정리• 루프 불변식과 타당성 증명: 외부 루프에 대해 “각 반복 시작 시 A[1..j−1]은 정렬되어 있음”을 불변식으로 두고 초기·유지·종료 3단계로 수학적 귀납법 구조와 대응시켜 알고리즘 정당성 검증• 수행시간 분석과 시간복잡도: RAM 모델에서 연산 횟수를 기반으로 T(n)을 정의하고 for·while 루프별 반복 횟수를 합산하여 삽입정렬의 최선 Θ(n), 평균 Θ(n²), 최악 Θ(n²) 시간복잡도 특성 도출
|
||
|
[3강] 알고리즘의 설계 (1)
|
0:
33:
49
|
|
|
분할정복과 병합정렬 Merge 알고리즘 설계 핵심 정리• 분할정복과 병합정렬 구조: 분할–정복–결합 재귀 구조로 문제를 점화식과 종료 조건으로 정의하고, 입력을 크기 1까지 분할 후 Merge 절차로 정렬된 부분 배열을 하나의 정렬된 배열로 결합하는 알고리즘 설계 기법• Merge 알고리즘과 센티널: 정렬된 두 부분 배열을 보조 배열 L, R로 복사하고 각 끝에 센티널(무한대)을 추가한 뒤, 인덱스 비교를 통해 항상 더 작은 값을 선택하여 병합함으로써 끝 인덱스 검사 비용을 제거하고 선형 시간 O(n)에 정렬 병합을 수행하는 절차• 루프 불변식과 시간 분석: A[p..k-1]이 항상 전체 중 가장 작은 원소들의 정렬 구간이 되도록 초기·유지·종료 조건을 검증해 Merge의 타당성을 증명하고, 복사 루프와 병합 루프의 수행 횟수 합을 점근적 표기법으로 분석해 Merge는 O(n), 전체 병합정렬은 O(n log n) 시간 복잡도를 갖는다는 결론 도출
|
||
|
[4강] 알고리즘의 설계 (2)
|
0:
40:
13
|
|
|
병합정렬과 분할정복, 시간복잡도 분석 핵심 정리• Merge Sort 정렬 알고리즘: 분할–정복–결합 구조로 배열을 재귀적으로 반으로 나누고 병합하여 정렬하며, 병합 단계 비용이 각 레벨마다 Θ(n)으로 균일하게 발생함 • 분할정복 점화식과 시간복잡도 분석: 일반형 점화식 T(n)=aT(n/b)+D(n)+C(n)과 재귀트리·Master 정리를 사용해 Merge Sort의 T(n)=2T(n/2)+Θ(n)을 Θ(n log n)으로 해석하고, n=2^k 가정이 점근표기에서 일반성을 해치지 않음을 정리함 • 알고리즘 효율성 비교 및 하이브리드 전략: Θ(n log n) 정렬과 Θ(n²) 정렬(삽입정렬)의 성장 차이를 비교해 대규모 입력에서의 우수성을 설명하고, 작은 구간에 Insertion Sort를 섞어 상수 오버헤드를 줄이는 실무적 하이브리드 구현 전략을 제시함
|
||
|
[5강] 점근적 표기
|
0:
40:
48
|
|
|
점근적 표기 Big-Theta, Big-O, Big-Omega 및 리틀 o, 리틀 오메가 정리• 점근적 표기 개념과 전제 조건: 알고리즘 수행시간을 양의 함수로 가정하고 입력 크기 증가에 따른 증가 차수만 분석하며, 다항식의 계수·상수·저차항을 무시하고 최고차항 기준으로 시간 복잡도를 표현함• Big-Theta·Big-O·Big-Omega와 리틀 o·리틀 오메가: 상수배 상·하한으로 정의되는 함수 집합(Θ, O, Ω)과 극한 비율 0·∞로 엄격한 크기 차이를 나타내는 집합(o, ω)을 통해 시간 복잡도 상한·하한·정확한 차수를 구조적으로 비교함• 점근적 표기의 성질과 크기 비교: 집합 관계로서의 추이성·반사성·대칭성/역대칭성과 삼분법적 크기 비교를 이용해 다항식 등의 복잡도 계층을 정리하고, 상한·하한 관계가 성립하지 않는 특이 함수 사례까지 포함해 이론적 구조를 이해함
|
||
|
[6강] 표준 표기법과 함수
|
0:
47:
47
|
|
|
Summary Content:피보나치 수, 로그스타, 함수 반복과 알고리즘 복잡도 개념 정리• 점근적 성장 비교: 조화급수(Θ(log n)), 단조성·내림·올림 함수, 다항식·지수·로그함수, 계승과 스털링 근사를 통한 성장 순서(2^n ≪ n! ≪ n^n) 및 시간복잡도 계층 구조 정리• 함수 반복과 로그 스타: 함수 합성 반복 f^(i)(n) 개념, 밑 2 로그 반복 적용 횟수로 정의되는 log* n 의 극도로 느린 성장 특성과 알고리즘 복잡도 표현에서의 활용• 피보나치 수열과 알고리즘: 피보나치 수열 정의와 황금비 수렴 성질, 재귀·동적 계획법·반복·행렬 분할정복을 이용한 피보나치 계산 알고리즘의 시간·공간 복잡도 비교 (O(2^n), O(n), O(log n))
|
||
|
[7강] 최대 부분 배열 문제
|
0:
45:
18
|
|
|
분할정복과 최대 부분 배열 문제 핵심 개념 정리• 분할정복 알고리즘: 문제를 분할·정복·결합하는 재귀적 설계 기법으로, 점화식·재귀 트리·마스터 정리를 통해 시간 복잡도 분석• 최대 부분 배열 문제: 주식 최대 차익을 인접 날짜 간 변동가 배열의 최대 연속 부분합으로 환원한 문제로, 모든 구간을 직접 탐색하지 않고 구조적으로 최댓값 탐색• Maximum Subarray 분할정복 알고리즘: 배열을 반으로 분할해 왼쪽 최대·오른쪽 최대·중간을 가로지르는 cross subarray 최대합을 계산하고, 각 레벨 Θ(n)·총 Θ(n log n) 시간 복잡도 달성
|
||
|
[8강] 스트라센 알고리즘
|
0:
25:
32
|
|
|
분할정복을 이용한 행렬 곱셈과 Strassen 알고리즘 요약• 행렬 곱셈과 단순 알고리즘: 정사각 행렬 곱셈 정의·구조·3중 루프 기반 점화식 분석을 통해 연산량과 시간복잡도 Θ(n³) 도출• 분할정복 행렬 곱셈: 블록 행렬 분할·부분행렬 곱셈 8회·덧셈 비용을 포함한 점화식 T(n)=8T(n/2)+Θ(n²) 설정과 Θ(n³) 한계 분석• Strassen 행렬 곱셈 알고리즘: 부분행렬 곱셈 7회·보조 행렬 S₁~S₁₀·P₁~P₇ 구성으로 T(n)=7T(n/2)+Θ(n²), 시간복잡도 O(n^{log₂7})≈O(n^{2.807}) 및 이론적 이점과 실제 성능 비교
|
||
|
[9강] 점화식을 풀기 위한 치환법
|
0:
28:
23
|
|
|
분할정복 알고리즘 점화식과 치환법 핵심 정리 • 분할정복 점화식 분석: 분할정복 알고리즘 수행시간을 점화식으로 표현하고 치환법·재귀트리·마스터정리로 Big-O 상한을 도출하는 기본 구조 정리 • 치환법 절차와 보정 기법: 해의 형태 추측 → 수학적 귀납법으로 상한 증명 → 상수·경계조건 조정 → 실패 시 $cn-d$ 등 강화된 귀납 가정과 재추측을 통한 보정 방법 정리 • 특수 형태 점화식 처리: $T(n)=2T(n/2)+n$, $T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+2$, $T(n)=2T(\sqrt{n})+\log n$ 등을 통해 $O(n\log n)$, $O(n)$, $O(\log n\log\log n)$을 얻는 치환·변수변환·상수 선택 패턴 정리
|
||
|
[10강] 점화식을 풀기위한 재귀 트리 방법
|
0:
32:
30
|
|
|
분할정복 점화식의 재귀트리·치환법 해석 핵심 정리• 점화식 해석 기본 개념: 분할정복 알고리즘 수행시간을 점화식으로 표현하고, 재귀트리 방법과 치환법(추정 후 증명·수학적 귀납법)을 사용해 시간복잡도의 점근차수와 상한을 분석하는 절차 정리• 재귀트리 분석 구조: $T(n)=3T(n/4)+\Theta(n^2)$에서 레벨별 노드 수·입력 크기·비용 일반식을 통해 등비수열 합과 리프 비용을 계산하여 $\Theta(n^2)$ 도출, $T(n)=T(n/3)+T(2n/3)+\Theta(n)$에서 레벨별 총 비용과 트리 높이 추정으로 $O(n\log n)$ 유도• 치환법 검증 전략: 재귀트리로 얻은 해를 $T(n)\le d\cdot g(n)$ 형태로 가정하고 귀납 가정을 점화식에 대입해 계수 비교로 상수 범위를 찾음으로써 $T(n)=3T(n/4)+\Theta(n^2)$의 $O(n^2)$와 $T(n)=T(n/3)+T(2n/3)+\Theta(n)$의 $O(n\log n)$을 형식적으로 증명하고, 마스터 정리와의 연결 기반 마련
|
||
|
[11강] 점화식을 풀기위한 마스터 방법
|
1:
01:
31
|
|
|
분할정복 점화식의 마스터 정리와 비용 분석 핵심 정리• 마스터 정리 기본 구조: 분할정복 점화식 $T(n)=aT(n/b)+f(n)$에서 리프 총비용 $n^{\log_b a}$와 결합비용 $f(n)$의 점근적 크기 비교를 통해 세 경우(1: 리프 지배, 2: 모든 레벨 동급, 3: 루트 지배+정규 조건)로 해를 분류• 정규 조건과 확장형 2′: 3번 경우에서 $a f(n/b)\le c f(n)$, $c<1$인 정규 조건을 통해 루트 지배를 보장하며, $f(n)=\Theta(n^{\log_b a}(\log n)^k)$에서는 확장형 2′를 적용해 $T(n)=\Theta(n^{\log_b a}(\log n)^{k+1})$로 일반화• 적용 및 예제 분석: Strassen 알고리즘, 병합정렬 등 대표 점화식에 마스터 정리·2′·반복대입을 적용해 $T(n)$의 점근형을 도출하고, 다항식 $f(n)$에서 정규 조건 자동 충족과 진동 항 포함 시 적용 불가 사례를 구조적으로 구분
|
||
|
[12강] 고용 문제. 지표 확률 변수
|
0:
43:
30
|
|
|
알고리즘 비용 분석: 고용 문제의 확률적 분석과 랜덤화 알고리즘 개념• 고용 문제 비용 구조: 면접비용 c_i n과 고용비용 c_h m으로 구성되며 c_h ≫ c_i 가정하에 고용 횟수 m의 기대값을 통해 평균 비용을 분석• 확률적 분석과 랜덤화 알고리즘: 입력 순서를 균등 임의 순열로 가정한 평균 수행시간 분석과, 난수 사용으로 무작위 동작을 갖는 랜덤화 알고리즘의 기대 수행시간 분석 구분• 지표확률변수와 기대 고용 비용: 지표확률변수와 E[I_A]=P(A), 기대값 선형성을 이용해 고용 횟수의 기대값 E[X]=H_n≈ln n을 도출하고 평균 고용 비용이 c_h ln n 규모임을 정리
|
||
|
[13강] 랜덤화된 알고리즘
|
0:
45:
50
|
|
|
Summary Content:랜덤화된 Hiring Assistant 알고리즘과 균등 순열 생성 원리 요약• 확률적 분석과 랜덤화 알고리즘: 입력 분포를 가정하는 확률적 분석과, 난수로 입력을 재배열해 자체 확률 구조를 만드는 랜덤화 알고리즘의 차이·관계 및 Hiring Assistant에서 기대 고용비용이 $\mathbb{E}[H]=\Theta(\ln n)$ 형태로 일치함 정리• 균등 순열 생성 알고리즘: Permit-by-Sorting(우선순위 배열 P와 정렬, Counting Sort 적용 시 $\Theta(n)$)과 in-place 셔플(Fisher–Yates, 반복적 swap) 두 방식의 알고리즘 구조·시간 복잡도·모든 순열이 동일 확률 $1/n!$이 되는 균등 순열성 증명 절차(곱셈법칙·k-순열 수·루프 불변성·수학적 귀납법) 체계화• 랜덤화 Hiring Assistant 분석 구조: 입력을 균등 순열로 만드는 전처리 셔플 후 결정적 Hiring Assistant를 적용하는 모델에서 최악 입력의 고정성 소멸, “평균 고용비용 = 기대 고용비용” 대응 관계, 고용 횟수 기대값과 고용 1회당 비용 곱으로 표현되는 전체 기대 고용비용 AEO식으로 정리
|
||
| 2장. 정렬과 순서 통계량 | ||
|
[14강] 힙. 힙 특성 유지하기
|
0:
50:
35
|
|
|
힙 자료구조와 최대 힙 유지 알고리즘 핵심 정리• 힙과 완전 이진 트리 구조: 완전 이진 트리·포화 이진 트리 정의, 깊이·높이 개념, 자식 1개 노드 특성 등 힙의 트리 구조 정리 • 힙 배열 표현과 높이 관계: 1-based 배열 인덱스의 parent/left/right 공식, heap_size 개념, 노드 수와 높이 k=⌊log n⌋ 관계 정리 • 최대/최소 힙과 Max-Heapify: 최대 힙·최소 힙 정의와 루트 값 의미, Max-Heapify 절차와 재귀 구조, 시간 복잡도 O(log n) 분석
|
||
|
[15강] 힙 만들기
|
0:
45:
30
|
|
|
최대 힙(buid-max-heap) 구성 원리와 시간 복잡도 요약• 최대 힙과 Max-Heapify·Build-Max-Heap 관계: 완전 이진 트리 배열 표현에서 리프·비단말 노드 인덱스(리프 ⌈n/2⌉개, 비단말 1~⌊n/2⌋)를 이용해 비단말 노드에만 Max-Heapify를 역순 적용해 전체 최대 힙 생성• Build-Max-Heap 알고리즘 타당성: 루프 불변식 “반복 시작 시 A[i+1..n]의 각 원소는 최대 힙 서브트리의 루트”를 설정하고 초기·유지·종료 조건을 통해 전체 배열이 최대 힙 특성을 만족함을 증명• 힙 높이와 시간 복잡도: 높이 k=⌊log₂n⌋인 완전 이진 트리에서 Max-Heapify 한 번은 O(log n)이고, 레벨별(또는 높이별) 노드 수·하강 깊이를 합산한 급수 Σ(h/2^h)가 상수에 수렴해 Build-Max-Heap 전체 수행 시간은 O(n)으로 도출됨
|
||
|
[16강] 힙 정렬 알고리즘. 우선 순위 큐
|
0:
29:
04
|
|
|
힙 정렬과 최대 우선순위 큐 동작 원리 요약• 힙 정렬·시간복잡도: BUILD-MAX-HEAP과 MAX-HEAPIFY로 Max-Heap 구성 후 최대 원소를 배열 뒤로 이동해 정렬하며, BUILD-MAX-HEAP Θ(n), MAX-HEAPIFY O(log n)에 기반해 전체 시간복잡도 O(n log n) 정리 • 최대 우선순위 큐 연산: Max-Heap 기반으로 HEAP-MAXIMUM, HEAP-EXTRACT-MAX, HEAP-INCREASE-KEY, HEAP-INSERT 연산의 정의·절차·시간복잡도(O(1), O(log n)) 및 삽입·삭제 시 위/아래 방향 재구성 원리 설명 • 힙 인덱스·구현 구조: 1-based 인덱스 전제에서 parent, left, right 관계와 0번 인덱스 미사용 설계, Max-Heap 특성(부모 ≥ 자식)을 유지하며 Extract-Max, Increase-Key, Insert가 트리 높이에 비례해 동작하는 구조 제시
|
||
|
[17강] 퀵 정렬 (1)
|
0:
52:
48
|
|
|
퀵 정렬과 Lomuto 파티션의 개념과 타당성 정리• 정렬 알고리즘·퀵 정렬 성능 특성: 단순 정렬 vs 분할정복 정렬 분류, 퀵 정렬의 분할정복 구조와 평균 Θ(n log n)·최악 Θ(n²) 시간 복잡도 및 병합/힙 정렬과의 성능 비교• 파티션 알고리즘 구조(Lomuto·Hoare): 피벗과 배열 구간 정의, Lomuto 파티션의 i·j 인덱스 역할과 “pivot 이하 / pivot 초과 / 미처리” 구간 유지, Hoare 파티션과의 인덱스 이동 방식·경계 검사 복잡도 비교• Lomuto 파티션 정당성·시간 분석: 한 번의 파티션이 Θ(n)임을 보이는 수행시간 분석과 loop 불변성(초기화·유지·종료)을 통한 “피벗 기준 정확한 분할” 정당성 증명 및 이를 이용한 퀵 정렬 correctness 확립
|
||
|
[18강] 퀵 정렬 (2)
|
0:
47:
38
|
|
|
퀵정렬 성능 분석과 랜덤화 퀵정렬 평균 시간 복잡도 요약• 퀵정렬 시간 복잡도 구조: 분할 균형도에 따른 점화식(최악 T(n)=T(n-1)+Θ(n), 균등·적당한 불균등 분할 T(n)=2T(n/2)+Θ(n))으로 최악 Θ(n²), 일반적 경우 Θ(n log n) 성능 분석• 랜덤화 퀵정렬 개념과 최악 케이스: 구간 내 임의 인덱스를 피벗으로 선택해 분할 패턴을 랜덤화하고도 점화식 T(n)=T(q)+T(n-q-1)+Θ(n)에서 치환법으로 최악 시간 복잡도 상한 Θ(n²) 유지 구조 제시• 비교 횟수 기반 평균 시간 복잡도: 지표확률변수 X_{ij}와 P(X_{ij}=1)=2/(j-i+1)을 이용해 전체 비교 횟수 기대값 E[X]=Θ(n log n) 도출, 조화급수-로그 관계로 랜덤화 퀵정렬 평균 시간 복잡도 Θ(n log n) 증명
|
||
|
[19강] 정렬의 하한. 계수 정렬
|
0:
59:
18
|
|
|
비교정렬 하한과 개수정렬·안정성 개념 정리• 비교정렬 하한과 결정트리 모델: 결정트리에서 리프 수 ≥ n!·높이 h가 log(n!) = Θ(n log n) 이상이므로 모든 비교정렬의 최악 비교 횟수는 Ω(n log n)이며 비교 기반 정렬의 최적 시간복잡도는 Θ(n log n)임 • 개수정렬(Counting Sort): 유한 정수 범위 키에 대해 빈도 배열 C·누적합·역순 채우기 절차로 Θ(n + k) 시간과 O(n + k) 메모리로 선형시간 정렬을 수행하며 k = O(n)일 때 효율적임 • 정렬의 안정성(Stability): 같은 키의 상대적 순서를 보존하는 성질로 삽입정렬·병합정렬·개수정렬은 안정적이고 힙정렬·퀵정렬은 비안정적이며, 특히 기수정렬에서 올바른 다단계 정렬을 위해 필수 조건임
|
||
|
[20강] 기수 정렬. 버킷 정렬
|
0:
50:
56
|
|
|
기수정렬과 버킷정렬의 원리와 시간복잡도 요약• 기수정렬(radix sort) 개념·시간복잡도: 자릿수별 안정 정렬 반복으로 전체 순서를 구성하며 계수정렬 기반으로 Θ(d(n+k)) ≈ Θ(dn) 선형 시간 달성, 비트 단위 표현 시 b·r·2^r 관계로 복잡도 표현• 버킷정렬(bucket sort) 개념·정확성·평균 시간: [0,1) 구간 균등·독립 분포 가정하에 n개 버킷에 배치 후 버킷 내 삽입정렬과 순차 연결로 정렬을 보장하며 기대 시간복잡도 Θ(n) 선형 시간 도출• 비교 기반 정렬과 선형 시간 정렬 관계: 결정트리 하한으로 비교정렬은 Ω(n log n)에 제한되지만 계수정렬·기수정렬·버킷정렬은 값 범위·분포·추가 메모리 활용으로 비교 연산 하한을 회피해 선형 시간 정렬 구현
|
||
|
[21강] 중앙값과 순서 통계량 (1)
|
1:
01:
32
|
|
|
순서 통계량과 선택 알고리즘• 순서 통계량·선택 문제: i번째 순서 통계량 정의, 최소값·최대값·중앙값 관계, 비교 기반 선택 문제의 시간 복잡도 하한 Ω(n) 정리• 최소·최대 및 정수 연산: 최소·최대 탐색의 비교 횟수 하한 n-1, 최소·최대 동시 계산 알고리즘의 O(n)·약 3/2 n 비교 상한, floor/ceiling 함수의 기본 성질과 부등식 활용• Randomized Select 분석: QuickSort식 분할을 이용한 선택 알고리즘 구조, 최악 시간 Θ(n²) 점화식과 기대시간 E[T(n)] 분석, 지표 확률변수 기반 평균 선형 시간 Θ(n) 도출 원리
|
||
|
[22강] 중앙값과 순서 통계량 (2)
|
0:
50:
44
|
|
|
선택 알고리즘의 최악 시간 복잡도 개선: Median-of-Medians와 점화식 분석• Median-of-Medians 선택 문제 구조: I번째 순서통계량을 찾기 위해 5개 단위 그룹핑·부분 정렬·각 그룹 중앙값 추출·중앙값들의 중앙값을 피벗으로 선택·partition 후 한쪽 부분 배열만 재귀 호출하는 선형 시간 선택 알고리즘 설계• 피벗 품질 보장 분석: 5개 그룹 중앙값 구조를 이용해 피벗 x보다 큰·작은 원소 개수의 하한을 ≥(3/10)n−c로 도출하고, partition 이후 재귀로 남는 부분 배열 크기를 ≤(7/10)n+c로 상한 설정하여 극단적 1 vs (n−1) 분할을 구조적으로 차단• 점화식과 복잡도 증명: T(n) ≤ T(n/5) + T(7n/10 + c) + an 점화식을 세운 뒤 치원법(guess & induction)으로 T(n) ≤ Cn을 만족하는 C,n₀를 구성하여 최악의 경우 시간 복잡도 T(n)=Θ(n)임을 증명하고, 선택 문제의 하한 Ω(n)과 일치시켜 정확한 Big-Theta 결론 확립
|
||
| 3장. 자료구조 | ||
|
[23강] 기본 자료구조 (1)
|
0:
53:
43
|
|
|
자료구조 기초: 동적 집합, 스택, 큐, 연결리스트 핵심 정리• 자료구조 구조 구분: 물리적 구조(배열·리스트)와 논리적 구조(스택·큐·힙·트리·그래프)로 구분하고, 선형/비선형 구조와 구현 관계를 통해 데이터 조직 방식 정의 • 동적 집합과 사전(dictionary) 연산: 키 기반 동적 집합에서 Search·Minimum·Maximum·Successor·Predecessor 등의 질의 연산과 Insert·Delete 변경 연산을 통해 원소를 검색·삽입·삭제하는 구조 설계 • 선형 구조 구현(스택·큐·연결리스트·센티넬): 배열 기반 LIFO 스택과 FIFO 순환 큐의 인덱스(head·tail·stack_top) 관리, 단순/양방향/원형 연결리스트의 검색·삽입·삭제 알고리즘과 센티넬 노드를 이용한 경계 조건 제거 및 코드 단순화
|
||
|
[24강] 기본 자료구조 (2)
|
0:
31:
05
|
|
|
연결 리스트의 배열 구현과 동적 메모리 관리, 일반 트리 표현 핵심 정리• 배열 기반 연결 리스트 구현: 다중 배열(next[], key[], previous[])과 단일 배열 인덱스를 포인터처럼 사용해 노드 필드를 구성하고, 다양한 노드 길이와 다수 리스트를 단일 배열 세트에서 관리하는 구조 • Free list와 메모리 관리: free 포인터가 가리키는 빈 노드 연결 리스트를 기반으로 Allocate Object / Free Object 알고리즘을 수행해 시스템 호출 없이 내부 메모리 풀을 O(1) 시간에 할당·반납하는 기법 • 트리 구조 표현: 이진 트리는 [키, 부모 포인터, 왼쪽 자식, 오른쪽 자식] 필드로 표현하고, 일반 N-ary 트리는 Left-Child Right-Sibling(왼자식-오른형제) 구조로 자식·형제 관계를 이진 트리와 동일한 포인터 수로 표현하는 방법
|
||
|
[25강] 직접 주소 테이블. 해시 테이블
|
0:
54:
56
|
|
|
해시 테이블과 직접 주소 테이블, 체이닝 핵심 정리 (자료구조)• 직접 주소 테이블과 해시 테이블: 키 집합 전체를 인덱스로 사용하는 직접 주소 테이블의 O(1) 연산과 높은 메모리 사용 대비, 해시 함수를 통해 제한된 크기 m 테이블에 키를 매핑해 공간 효율을 높이는 해시 테이블 구조 및 기본 연산(Search/Insert/Delete) 비교• 해시 함수·충돌·체이닝: 결정론적 해시 함수 h: U → {0,…,m-1} 정의, 서로 다른 키가 같은 슬롯에 매핑되는 충돌(collision) 개념, 각 슬롯을 버킷으로 보고 이중연결리스트로 여러 원소를 저장하는 체이닝 구조와 삽입·삭제·검색 절차 및 최악 경우 특성• 단순균등 해싱·적재율·성능 분석: 단순균등 해싱 가정(모든 키가 m개 슬롯에 균등·독립적으로 분포)과 적재율 α = n/m 정의를 통해 버킷 평균 길이 E[n_j] = α 도출, 체이닝에서 검색 실패·성공의 평균 시간 복잡도가 모두 Θ(1 + α)가 되어 α를 상수로 유지할 때 평균 상수 시간 연산이 가능함을 분석
|
||
|
[26강] 해시 함수
|
0:
20:
26
|
|
|
체인링 기반 해시함수 설계와 나누기·곱하기 방법 핵심 정리• 체인링 해시 테이블 구조: 체인링을 사용하는 해시 테이블에서 충돌 최소화를 위해 키 문자 추출·분포 균등성을 고려한 해시함수 설계 원리 정리 • 나누기 방법 해시함수: h(k)=k mod m 구조, 테이블 크기 m의 소수·2의 거듭제곱과 먼 홀수 선택 기준, 적재율 α=n/m과 평균 검색 시간(체인 길이)에 미치는 영향 정리 • 곱하기 방법 해시함수: h(k)=⌊m·{ka}⌋ 구조, 황금비 켤레 계열 상수 a 선택, 정수 연산 구현을 위한 w비트·p비트 개념과 m=2^p 테이블 설계 원리 및 크누스 제안 상수 활용 정리
|
||
|
[27강] 개방 주소화 방법 (1)
|
0:
36:
36
|
|
|
개방주소법과 선형·2차·중복조사 해싱의 군집 문제• 개방주소 해싱 구조: 모든 원소를 테이블 내부에 저장하고 조사함수 h(k,i)로 충돌을 해결하며, 적재율 α<1 유지·포화 시 재해싱과 DELETED 마크 기반 삭제 처리• 선형·2차 조사와 군집: 선형조사 h(k,i)=(h′(k)+i) mod M에서 1차 군집(연속 채움 구간 확대), 2차조사 h(k,i)=(h′(k)+c₁i+c₂i²) mod M에서 같은 초기 위치 키 간 2차 군집 발생• 중복 해싱과 설계 조건: 중복 해싱 h(k,i)=(h₁(k)+i·h₂(k)) mod M으로 키별 상이한 보폭을 사용해 1차·2차 군집을 완화하며, h₂(k)와 M을 서로소가 되도록 선택해 조사 경로가 테이블 전 범위를 순환하도록 설계
|
||
|
[28강] 개방 주소화 방법 (2)
|
0:
46:
34
|
|
|
개방주소법 해싱에서 실패·성공 검색의 평균 조사 횟수 분석• 개방주소법 해싱 기본 가정: 균등 해싱과 적재율 α<1에서 실패 검색·삽입·성공 검색의 기대 조사 횟수를 확률변수와 꼬리합, 상계 기법으로 분석• 실패 검색·삽입 연산 분석: 사건 X≥i와 조건부 확률 곱을 α^{i-1}로 상계하여 실패·삽입의 평균 조사 횟수 상한을 1/(1-α)로 도출하고, 적재율 변화에 따른 O(1) 시간 보장 조건 제시• 성공 검색 분석: 각 삽입 단계 적재율 i/m에서의 조사 횟수 m/(m-i)를 평균해 ∑1/(m-i)를 적분·로그로 근사하여 성공 검색 평균 조사 횟수 상한 1/α·ln(1/(1-α))을 도출하고, 실패 검색 상한과 비교해 성능 특성 정리
|
||
|
[29강] 이진 검색 트리 (1)
|
0:
45:
00
|
|
|
이진 검색 트리의 정의와 질의 연산 정리• 이진 검색 트리(BST) 정의·구조: 각 노드에서 왼쪽 서브트리 키 ≤ 현재 키 ≤ 오른쪽 서브트리 키가 재귀적으로 유지되며, 노드는 키·데이터·왼쪽/오른쪽 자식 포인터·부모 포인터로 구성됨 • 트리 순회 알고리즘: 중위(inorder: L,V,R)·전위(preorder: V,L,R)·후위(postorder: L,R,V) 순회로 모든 노드를 한 번씩 방문하며, 점화식 T(N)=T(k)+T(N-k-1)+d로 Θ(N) 시간에 수행됨 • BST 질의 연산과 복잡도: 검색(search)·최소값(minimum)·최대값(maximum)·직후원소(successor)·직전원소(predecessor)는 한 경로만 따라 내려가거나 올라가므로 높이 H에 대해 O(H) 시간에 수행됨
|
||
|
[30강] 이진 검색 트리 (2)
|
0:
34:
36
|
|
|
이진검색트리 삽입과 삭제 연산 알고리즘 정리• 이진검색트리 삽입 연산: 루트에서 키 비교를 반복해 적절한 리프(NIL) 위치를 찾은 뒤 새 노드를 부모의 왼쪽/오른쪽 자식으로 연결하며, 높이에 비례한 O(h) 시간에 수행됨• 이진검색트리 삭제 연산: 삭제 노드의 자식 수(0·1개 vs 2개)에 따라 서브트리 교체 또는 오른쪽 서브트리의 직후원소(successor)를 이용한 대체로 처리하며, 높이에 비례한 O(h) 시간에 수행됨• 트랜스플란트(Transplant) 알고리즘: 서브트리 루트 U를 V로 교체하며 부모-자식 포인터만 수정하는 보조 연산으로, 루트 교체 포함 각종 삭제 경우에서 공통적으로 사용되고 O(1) 시간에 수행됨
|
||
|
[31강] 레드블랙 트리의 특성. 회전
|
0:
40:
35
|
|
|
레드블랙트리 특성과 높이 분석, 회전 연산 정리 • 레드블랙트리 기본 개념: 이진 검색트리 편향 문제 해결을 위한 색 정보 기반 균형 트리 구조와 5가지 색상 특성, 흑색 높이 정의 및 NIL(센티넬) 노드 사용 원리 정리 • 높이 상한 및 연산 복잡도: 흑색 높이 보조정리와 적색‑연속 금지 특성을 이용한 최대 높이 $h \le 2\log n + 1$ 증명, 이를 통한 탐색·삽입·삭제 등 주요 연산의 $O(\log n)$ 시간 보장 구조 • 회전 연산 구조: 레드블랙 특성 복구를 위한 색 변경과 회전 개념, 좌회전·우회전의 포인터 갱신 절차와 중위 순서 보존, 좌·우 대칭 관계 및 삽입·삭제 시 적용 방식 정리
|
||
|
[32강] 삽입 (1)
|
0:
37:
16
|
|
|
레드블랙 트리 삽입과 조정: 색변경과 회전 규칙 정리• 레드블랙 트리 삽입 절차: BST 방식으로 위치 탐색 후 새 노드를 적색으로 삽입하고, 루트 색·부모-자식 적색 인접 여부 등 레드블랙 특성 위반 가능성 점검• 삽입 후 조정 케이스: 삼촌이 적색인 경우 색변경(부모·삼촌 흑색, 조부모 적색) 반복으로 흑색 높이 보존, 삼촌이 흑색인 경우 좌·우회전과 부모·조부모 색 교환으로 키 순서·특성 4·5 동시 복원• 삽입 알고리즘 구조와 복잡도: 삽입 탐색 단계와 위로 올라가는 fixup 단계로 구성되며, 색변경·회전 연산을 트리 높이 O(log n) 내에서 수행해 균형 유지 및 전체 삽입 연산을 O(log n)에 보장
|
||
|
[33강] 삽입 (2)
|
0:
39:
42
|
|
|
레드블랙 트리 삽입 조정 알고리즘의 케이스와 타당성 증명 개요• 레드블랙 트리 삽입 조정 구조: 루트 흑색 강제와 “부모가 적색인 동안” 반복 루프를 기반으로, 부모·조부모·삼촌의 위치 및 색에 따른 대칭적 케이스 분기(케이스 1·2·3)로 삽입 후 위반 가능 특성만 국소적으로 복구하는 구조• 삽입 조정 케이스 분석: 삼촌 적색 시 색변경 후 상위로 전파(케이스 1), 삼촌 흑색·‘꺾인’ 구조에서 1차 회전으로 직선형 변환(케이스 2), 직선형 구조에서 2차 회전과 최종 색 변경으로 적색-적색 위반 제거 및 흑색 높이 보존(케이스 3)• 타당성 및 수행시간: “현재 노드 적색, 루트 흑색(필요 시), 위반은 특성 2 또는 4 중 하나만”이라는 루프 불변성을 초기·유지·종료 조건으로 증명하여 레드블랙 특성(1~5) 회복을 보장하고, BST 삽입 O(log n) + 색변경·회전(상수 시간, 최대 2회)으로 전체 삽입 시간 O(log n) 유지
|
||
|
[34강] 삭제
|
1:
08:
53
|
|
|
레드블랙트리 삭제와 삭제 후 조정 알고리즘 정리• 레드블랙트리 삭제 구조: 이진검색트리 삭제(트랜스플랜트, 직후노드 교체)의 A,B,C,D 케이스를 그대로 사용하면서 Y, X, Y_original_color로 색 관리 및 특성 2·4·5 위반 여부를 판정하는 삭제 절차• 여분의 흑색과 위반 모델링: Y_original_color가 흑색일 때 흑색 높이 감소를 X의 여분 흑색(이중 흑색 포함) 상태로 환원하여 특성 5 위반을 특성 1 형식 위반으로 변환하고, 루트·적색+흑색 종료 조건을 기준으로 처리하는 불변식 구조• 삭제 후 조정 케이스 1~4: while 루프에서 X의 부모·형제·형제 자식 색 조합에 따라 케이스 1(형제 적색 전처리) → 2(여분 흑색 상향 전파) → 3(케이스 4 형태로 변형) → 4(여분 흑색 최종 흡수)로 회전·색변경을 수행하여 레드블랙 특성 2·4·5를 복원하고 전체 연산을 O(log n)에 유지하는 균형 유지 알고리즘
|
||
|
[35강] 동적 순서 통계량
|
0:
44:
08
|
|
|
레드블랙 트리를 이용한 동적 순서 통계 트리 개념과 연산 정리• 동적 순서 통계 트리(Order-Statistic Tree) 구조: 레드블랙 트리에 size 필드를 추가해 각 노드 서브트리 크기를 유지하고, 인오더 순위를 기준으로 i번째 원소와 원소의 순위를 다루는 균형 이진 검색 트리 확장 개념 • 핵심 연산 알고리즘: size(X)=size(X.left)+size(X.right)+1 정의 기반으로 i번째 원소 찾기(Select)와 원소 X의 순위 구하기(Rank)를 루트에서 리프·조상 방향 경로 탐색만으로 수행하는 O(log n) 순서 통계 연산 절차 • 갱신 및 시간 복잡도: 삽입·삭제 시 경로 상 조상 노드의 size 증감과 회전 시 관련 노드의 size 재계산만 수행하며, 레드블랙 특성 복원과 함께 검색·삽입·삭제·Select·Rank 모든 연산을 O(log n)에 보장하는 동적 순서 통계 자료구조 특징
|
||
|
[36강] 자료구조의 확장 기법. 구간 트리
|
1:
00:
39
|
|
|
자료구조 확장 기법과 구간트리(Interval Tree) 정리• 자료구조 확장 일반 원리: 레드블랙트리 등 기본 구조 선택 후 확장필드 F 설계, F가 노드 자신·좌우 자식 정보만으로 결정되도록 정의하여 삽입·삭제 시 루트까지 상향 갱신만으로도 전체 시간 복잡도 O(log n) 유지• 동적 순서 통계량과 레드블랙트리 확장: 노드에 서브트리 크기 size 등 확장필드를 추가해 Select·Rank 등 새로운 연산을 정의하고, 정리 14.2 조건 하에서 삽입·삭제·회전 과정에서 확장필드 유지 비용을 O(log n)으로 보장• 구간트리와 Interval-Search: 각 노드가 [low, high] 구간과 max(서브트리 최대 high)를 저장하는 레드블랙트리 기반 구조로, 왼쪽 서브트리의 max와 겹침 조건을 이용해 탐색 방향을 결정하는 Interval-Search 알고리즘과 그 루프 불변성·타당성 증명 정리
|
||
| 4장. 고급 설계 및 분석 기법 | ||
|
[37강] 동적 프로그래밍. 막대 자르기
|
0:
57:
54
|
|
|
동적 프로그래밍과 막대 자르기 문제 핵심 정리• 동적 프로그래밍 핵심 개념: 최적 부분 구조·중복 부분 문제 조건에서 지수 시간 재귀를 다항 시간 알고리즘으로 변환하고, 분할정복·Greedy와의 부분 문제 구조·선택 시점 차이 정리 • 막대 자르기 최적화 모델: 가격 배열에 기반한 최대 수익 점화식 \(r_n = \max_{1 \le i \le n}(p_i + r_{n-i})\) 정의, 나이브 재귀의 \(\Theta(2^n)\) 수행시간 분석 및 부분 문제 그래프 관점 정리 • 동적 프로그래밍 구현 구조: 탑다운 메모이제이션과 바텀업 테이블 방식으로 막대 자르기 문제를 \(O(n^2)\)에 해결하고, 추가 배열 \(s_j\)를 이용해 최적 자르기 패턴을 해 재구성 절차로 복원하는 방법 정리
|
||
|
[38강] 행렬-체인 곱셈
|
1:
06:
48
|
|
|
행렬체인 곱셈 동적 프로그래밍 개념과 점화식 정리• 행렬체인 곱셈 문제 정의: 행렬 차원 배열 p를 이용해 곱셈 순서(괄호 묶기)를 결정하고 스칼라 곱셈 횟수를 최소화하는 최적화 문제 구조 정리• 동적 프로그래밍 모델: 최적 부분 구조에 기반한 부분문제 m[i,j]와 점화식 m[i,j] = min_{i ≤ k < j}{ m[i,k] + m[k+1,j] + p_{i-1}p_kp_j } 설정, 경계조건 m[i,i]=0 및 상향식 테이블 채우기 절차 정리• 알고리즘 구현 요소: m,s 2차원 테이블 구성과 체인 길이 기반 계산 순서, 부분문제 수 O(n²)와 k 순회를 통한 전체 시간복잡도 O(n³), s[i,j]를 이용한 최적 괄호 묶기 복원 방법 정리
|
||
|
[39강] 동적 프로그래밍의 요소
|
0:
48:
07
|
|
|
동적 프로그래밍의 두 핵심: 최적 부분 구조와 중복 부분 문제• 동적 프로그래밍 핵심 개념: 최적 부분 구조·부분 문제 독립성·중복 부분 문제를 전제로 막대 자르기·행렬 체인 곱셈·최단경로에서 지수 시간을 O(n³) 다항 시간으로 감소시키는 방법 정리 • 최적 부분 구조와 예외: 잘라내고-붙이기와 모순 증명으로 전체 최적해 = 부분 최적해들의 조합 조건을 정식화하고, 최단경로는 충족하나 정점 공유와 사이클 제약으로 최장경로는 불충족함을 분석 • 중복 부분 문제와 알고리즘 구조: 재귀 점화식의 지수적 호출 패턴을 표 기반 메모이제이션(탑다운)과 상향식 DP(바텀업)로 O(n²)개 부분 문제 × O(n) 선택 구조로 변환하여 시간·공간 복잡도 O(n³), O(n²) 체계화
|
||
|
[40강] 최장 공통 부분 시퀀스
|
0:
53:
06
|
|
|
최장 공통 부분 시퀀스(LCS) 동적 프로그래밍 정리 핵심• LCS 기본 개념: 부분 시퀀스·공통 부분 시퀀스·LCS 정의와 접두사 개념을 통해 최적 부분 구조와 중복 부분 문제를 가지는 동적 프로그래밍 대상 문제로 정식화• LCS 점화식과 테이블 구조: c[i,j]를 이용한 세 가지 점화식(기저, 마지막 문자 동일, 마지막 문자 상이)과 (m+1)×(n+1) DP 테이블, b[i,j] 방향 배열(↖, ↑, ←) 설계를 통해 길이 계산을 O(mn) 시간에 수행• LCS 복원 알고리즘과 복잡도: 방향 테이블을 재귀적으로 따라가며 LCS 문자열을 정순으로 복원하는 Print-LCS 절차를 구성하고, 전체 알고리즘의 시간 복잡도를 테이블 계산 O(mn)과 복원 O(m+n)으로 분석
|
||
|
[41강] 최적 이진 검색 트리
|
0:
58:
42
|
|
|
최적 이진 검색 트리와 동적 프로그래밍 요약• 최적 이진 검색 트리 문제 정의: 실제 키·가상 키에 대한 검색 확률 분포(p_i, q_i)에 기반해 기대 검색 비용 E[T]를 최소화하는 이진 검색 트리 구조 설계• 최적 부분 구조와 점화식: 구간 (i,j)의 부분 문제 비용 E[i,j], 확률 합 W[i,j] 정의 후 E[i,j] = min_{i≤r≤j}{E[i,r-1]+E[r+1,j]+W[i,j]}, 경계조건 E[i,i-1]=q_{i-1}로 최적 부분 구조와 재귀식 수립• 동적 계획 알고리즘: E[i,j], W[i,j], root[i,j] 2차원 테이블을 j≥i-1 삼각 영역에서 간격 l 기준으로 확장하며 채우고, root 테이블 역추적으로 최적 트리 구조 복원
|
||
|
[42강] 활동 선택 문제
|
0:
51:
51
|
|
|
그리디 알고리즘과 활동 선택 문제 핵심 정리• 그리디 알고리즘과 동적 프로그래밍 비교: 국소 최적 선택과 단일 부분 문제 구조 vs 모든 부분 문제 탐색과 테이블 기반 최적 부분 구조 활용, 적용 가능 조건과 한계 정리• 활동 선택 문제 수학적 모델: 시작·종료 시간으로 정의된 활동 집합, 양립 가능 조건과 [s_i, f_i) 구간 표현, 최적 부분 구조와 c_ij 점화식 기반 동적 프로그래밍 해석• 활동 선택 문제 그리디 해법: 종료 시간 기준 정렬 후 가장 빨리 끝나는 활동을 반복 선택, 2차원 부분 문제를 1차원으로 축소하는 그리디 선택의 안전성 증명과 재귀·반복 알고리즘 절차 정리
|
||
|
[43강] 그리디 방법의 요소들
|
0:
27:
01
|
|
|
그리디 알고리즘 핵심 개념과 동적 프로그래밍·배낭문제 비교• 그리디 알고리즘 설계 원리: 그리디 선택 특성·최적 부분 구조 정의, 선택-부분문제 1개 생성 구조, 수학적 기납법·루프 불변식 기반 타당성 증명 및 시간복잡도 분석• 대표 그리디 알고리즘과 배낭 문제: Dijkstra 최단경로의 국소 최선 선택 구조, 0-1 Knapsack·분할 가능한 Knapsack의 최적 부분 구조 비교, 분할 가능한 배낭의 단위가치 정렬 그리디 해법(O(n log n))• 그리디 vs 동적 프로그래밍 적용 기준: 그리디 선택의 안전성 + 최적 부분 구조가 동시 성립할 때만 그리디 사용, 성립하지 않는 0-1 Knapsack에서는 중복 부분 문제를 테이블로 해결하는 동적 프로그래밍 적용 기준 정리
|
||
|
[44강] 허프만 코드
|
1:
03:
36
|
|
|
그리디 알고리즘 허프만 코드와 프리픽스 코드 핵심 정리 요약• 허프먼 코드와 프리픽스 코드: 문자 빈도 기반 가변 길이 프리픽스 이진 코드로 전체 비트 수 B(T)=∑c.frequency·dT(c)를 최소화하는 비손실 압축 방식• 허프먼 트리 구조와 생성 알고리즘: 모든 내부 노드가 자식 2개를 갖는 완전 이진트리로 표현되며, 최소 힙에서 매 단계 빈도 최소 2개 노드를 병합해 루트까지 구성• 그리디 선택·최적 부분 구조 정당성: 최소 빈도 두 문자를 형제 리프로 선택해도 항상 최적 트리가 존재하고, 이 둘을 합친 가상 문자 집합의 최적 트리를 확장하면 전체 최적 프리픽스 코드가 되어 허프먼 알고리즘의 최적성 보장
|
||
|
[45강] 분할 상환 분석. 총계 분석
|
0:
39:
10
|
|
|
분할상환 분석과 총계분석 핵심 정리 (스택·이진 카운터 사례)• 분할상환 분석 개념: 연산 시퀀스 전체 비용 T(n)을 기준으로 연산당 평균 비용(분할상환 비용)을 평가하는 비확률적 시간복잡도 분석 방법• 총계분석 원리와 스택 연산: n번의 push/pop/multipop 시 전체 pop 횟수가 push 횟수를 넘지 않음을 이용해 총 수행시간을 O(n)으로 두고, 세 연산 모두 분할상환 비용 O(1)로 도출• 이진 카운터 increment 총계분석: 각 비트의 반전 횟수 합을 Σ⌊n/2^i⌋ < 2n으로 상계하여 n번 increment의 총 수행시간 O(n), 연산당 분할상환 비용 O(1)로 정리
|
||
|
[46강] 결산 방법. 잠재 비용 방법
|
0:
42:
23
|
|
|
분할상환 분석 결산 방법과 잠재비용 방법 비교 정리• 분할상환 분석과 결산 방법: 연산 시퀀스 평균 비용 상한 분석, 실제 비용보다 큰 분할상환 비용과 객체별 크레딧 설계를 통해 총계 분석과 동일한 O(n) 상한 도출• 잠재비용 방법과 잠재함수: 자료구조 상태에 대한 잠재함수 Φ(D)을 두고 \(\hat{c}_i = c_i + \Phi(D_i)-\Phi(D_{i-1})\)로 분할상환 비용 정의, 망원합으로 \(\sum \hat{c}_i \ge \sum c_i\) 보장• 대표 사례 및 상한: 스택 연산(푸시 2, 팝·멀티팝 0)과 이진 카운터 증가(비트 설정·반전 상수 비용)에서 결산·잠재비용 방법 모두 n번 연산 총비용 O(n), k비트 카운터의 임의 초기 상태에서도 실제 비용 상한 2n + k = O(n) 정리
|
||
|
[47강] 동적 테이블 (1)
|
0:
43:
28
|
|
|
동적 테이블과 분할상환 분석(총계·결산·잠재비용 방법)• 동적 테이블과 확장 전략: 배열 기반 동적 테이블에서 적재율과 2배 확장 규칙을 통해 삽입·삭제를 상수 시간 수준으로 지원하는 구조 및 동작 원리 정리• 분할상환 분석 기법: 동적 테이블 삽입 연산에 대해 총계 분석·결산(은행가) 방법·잠재비용 방법을 사용해 전체 n번 연산 비용을 3n 이하로 제한하고 연산당 분할상환 비용이 상수(3)임을 증명• 세 방법의 비교: 세 분할상환 분석 기법의 정의·계산 절차·해석을 비교하여 동적 테이블의 2배 확장 전략이 분할상환적으로 O(1) 삽입 시간을 보장함을 커리큘럼 구조로 정리
|
||
|
[48강] 동적 테이블 (2)
|
0:
45:
20
|
|
|
동적 테이블 확장·축소의 분할상환 분석과 적재율 기준• 동적 테이블 적재율 관리 전략: 1/2 기준 축소 시 삽입·삭제 교대 패턴에서 빈번한 확장·축소로 총비용 Θ(n²) 발생 구조 분석• 1/4 미만 축소 정책과 잠재비용 함수: 적재율 1/4 미만에서만 1/2 축소하고, α≥1/2 구간 Φ=2T_num−T_size, α<1/2 구간 Φ=½T_size−T_num을 사용해 확장·축소 복사 비용을 크레딧으로 상쇄• 삽입·삭제 분할상환 비용과 전체 복잡도: 삽입 연산 분할상환 상한 3, 삭제 연산 상한 2를 증명하고, N번 연산 전체 시간 복잡도가 Θ(N)임을 보이는 분할상환 분석 커리큘럼 구성
|
||
| 5장. 고급 자료구조 | ||
|
[49강] 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 수준으로 유지하는 인덱스 설계 원리 정리
|
||
|
[50강] 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에서 “내려가며 미리 분할” 전략을 사용해 루트 분할·자식 분할·리프 삽입을 단일 하향 경로에서 처리하고, 모든 리프 높이 동일한 균형 상태 유지
|
||
|
[51강] B-트리에서 키 삭제하기
|
0:
42:
00
|
|
|
B-Tree에서 키 삭제 연산: 경우별 알고리즘 정리• B-Tree 삭제 조건과 목표: 모든 노드 키 수를 최소 T-1개 이상 유지하기 위해 하향 경로에서 미리 T개 이상 확보하며 한 번의 재귀 하향 과정에서 삭제를 완료하는 전략 정리• 삭제 경우별 알고리즘: 리프 노드 직접 삭제, 내부 노드에서 선행/후행 키 교체 후 재귀 삭제, 하위 서브트리 경로에서 형제 노드 차용·병합을 활용해 T개 유지하며 진행하는 세 경우의 절차 구조• 루트 처리와 시간 복잡도: 루트 병합·유일 자식 승격에 따른 트리 높이 감소 조건과 삭제 연산의 디스크 접근·CPU 시간 복잡도 O(log_T N), 삽입 알고리즘과의 대칭적 설계 원리 정리
|
||
|
[52강] 피보나치 힙의 구조
|
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 등 알고리즘 최적화에 활용
|
||
|
[53강] 병합 가능한 힙 연산
|
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) 증명
|
||
|
[54강] 키 감소시키기와 노드 삭제하기
|
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) 관계로 전체 효율 보장
|
||
|
[55강] 최대 차수의 한계 정하기
|
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)임을 정리
|
||
|
[56강] 동적 집합, 기본 방법
|
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 기준 서브로그 시간으로 가속하는 이론적 기반 정리
|
||
|
[57강] 재귀 구조 (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)에 수행하는 계층적 클러스터 구조 형성
|
||
|
[58강] 재귀 구조 (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 기반 성능 특성
|
||
|
[59강] 반 엠데 보아스트리 (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)$ 시간에 수행함
|
||
|
[60강] 반 엠데 보아스트리 (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))와 대비되는 최적화 원리 정리
|
||
|
[61강] 서로 소 집합의 연결 리스트 표현
|
0:
45:
02
|
|
|
서로소 집합 자료구조와 연결 리스트 구현 및 가중치 유니온 개념 정리• 서로소 집합과 기본 연산: 서로소 집합 정의 및 대표 원소 기반 관리, Make-Set·Union·Find-Set 연산 구조와 무방향 그래프 연결 요소 판별 알고리즘 정리• 연결 리스트 구현과 단순 유니온 복잡도: 집합 객체(head·tail·집합 포인터)로 표현된 연결 리스트 기반 Union-Find 구조와 포인터 갱신으로 인한 단순 유니온의 Θ(n²) 시간 복잡도 분석• 가중치 유니온 휴리스틱과 성능: 집합 크기를 가중치로 사용해 항상 작은 집합을 큰 집합에 붙이는 weighted union 규칙과 각 원소 O(log n) 갱신을 통한 전체 연산 O(m + n log n) 시간 복잡도 도출
|
||
|
[62강] 서로소 집합 포리스트
|
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장, 그래프 알고리즘 | ||
|
[63강] 그래프의 표현. 너비 우선 검색 (1)
|
0:
52:
22
|
|
|
그래프 표현과 너비 우선 탐색(BFS) 핵심 정리• 그래프 구조와 표현: 정점·간선 개념, 무방향/방향 그래프, 가중치 그래프, 인접 리스트·인접 행렬 표현 및 희소·밀집 그래프에서의 메모리 특성 정리• 특수 그래프 및 구조: 트리의 |E|=|V|-1 관계, 신장 트리·최소 신장 트리 개념을 통한 최소 간선 연결 구조 이해• 너비 우선 탐색(BFS): 색·거리·직전 정점 정보와 큐 기반 절차, BFS 트리와 최단 간선 수 경로 구성, 인접 리스트 기준 시간 복잡도 Θ(|V|+|E|) 분석
|
||
|
[64강] 너비 우선 검색 (2)
|
0:
42:
44
|
|
|
너비우선검색(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 색 변화·거리 갱신 규칙·큐 순서와 충돌을 이용한 모순법으로 보조정리와 따름정리의 거리·큐 관련 불변식 증명
|
||
|
[65강] 너비 우선 검색 (3)
|
0:
45:
45
|
|
|
너비우선검색(BFS) 타당성 증명과 너비우선 트리 특성 정리 • BFS 정확성 성질: 무가중치 그래프에서 최단경로거리 보장·도달 가능한 모든 정점의 완전 탐색·최적 부분 구조를 색(흰색·회색·검은색) 기반 모순 증명으로 정당화 • BFS 트리와 전정점 부분 그래프: 전정점 배열로 정의된 부분 그래프 Gπ가 |Eπ|=|Vπ|-1인 연결 비순환 구조의 트리가 되며, 레벨 순회(큐 기반 거리 레벨 확장)를 통해 출발점으로부터 유일한 단순 최단경로 트리를 형성 • 최단경로 출력 구조: 전정점 v.π를 따라 거슬러 올라가는 재귀 호출로 s→v 최단경로를 정방향으로 출력하며, 경로 길이 k에 대해 시간 복잡도 O(k)를 갖는 단일 경로 기반 출력 알고리즘 정립
|
||
|
[66강] 깊이 우선 검색 (1)
|
0:
35:
24
|
|
|
깊이우선검색(DFS) 알고리즘과 깊이우선 포리스트 정리• 깊이우선검색(DFS)와 깊이우선 포리스트: 깊이 우선 탐색 절차·BFS와의 비교·여러 시작점에서 형성되는 DFS 트리와 포리스트 구조 정의• DFS 상태·시간·간선 분류: 색(흰·회·검)과 발견/종료 시간·전역 시간으로 정점 상태 추적, 트리/역행/순행/교차 간선 4분류 및 DFS 트리 간선 집합 Eπ 구성• DFS 알고리즘과 시간 복잡도: 초기화와 DFS-VISIT 재귀 구조·트리 후위 순회와의 관계·정점/간선 1회 처리에 기반한 O(|V|+|E|) 수행 시간 분석
|
||
|
[67강] 깊이 우선 검색 (2)
|
0:
45:
58
|
|
|
깊이 우선 검색의 과로 구조와 흰색 경로 정리 요약• DFS 시간 구간과 과로 구조: 각 정점의 발견시간·종료시간으로 형성되는 포함/불포함 구간 구조를 통해 조상·자손·비직계 관계를 판별하고, 자손 구간 중첩 및 과로 정리로 두 정점 구간이 불겹침·포함·포함반대 세 유형만 가짐을 정식화함 • DFS 간선 분류와 흰색 경로 정리: 정점 색(흰색·회색·검은색)과 시간 조건을 이용해 간선을 트리·역행·순행·교차로 분류하고, 흰색 경로 정리로 특정 시점의 흰색 경로 존재 여부와 DFS 트리에서의 자손성(조상–자손 관계) 동치 조건을 제시함 • 무방향 그래프 DFS 구조: 무방향 그래프에서의 DFS는 간선이 트리간선 또는 역행간선으로만 나타나며, 쌍방향 간선 특성과 시간 구간 포함 관계를 통해 순행·교차 간선이 배제되는 구조적 제약을 설명함
|
||
|
[68강] 위상정렬
|
0:
35:
37
|
|
|
위상정렬과 DFS 기반 Topological Sort 알고리즘 정리 • 위상정렬 개념과 DAG 조건: 비순환 방향그래프(DAG)에서 간선 방향(선후관계)을 보존하며 모든 정점을 선형 순서로 나열하는 정렬 개념, 순환 존재 시 위상정렬 불가능 • 진입차수 기반 위상정렬 알고리즘: 진입차수 0 정점을 큐·스택에 삽입 → 선택·출력 → 간선 제거·진입차수 갱신 반복을 통해 다양한 위상 순서를 생성하며, 수행시간은 O(V+E) • DFS 기반 Topological Sort: DFS 종료시간 역순으로 정점을 나열해 위상정렬을 얻으며, DAG에서 역행간선 부재 성질을 이용해 알고리즘의 정확성을 증명하고 전체 시간복잡도는 O(V+E)로 분석함
|
||
|
[69강] 강한 연결요소
|
0:
58:
10
|
|
|
강한 연결 요소와 전치 그래프를 이용한 SCC 알고리즘 핵심 정리• 강한 연결 요소(SCC)·전치 그래프·SCC 요소 그래프: 상호 도달 가능한 정점 최대 집합 정의, 간선 반전 시 SCC 불변성, SCC 수축 그래프가 DAG가 되는 구조와 성질 정리 • DFS 시간 개념과 보조정리: 검색·종료 시간과 SCC 단위 D(C), F(C) 정의, 서로 다른 SCC 간 간선 방향과 종료 시간 대소 관계, 전치 그래프에서의 간선 방향·종료 시간 불변식 제시 • Kosaraju형 SCC 알고리즘: 원 그래프 DFS로 종료 시간 계산, 전치 그래프 구성, 종료 시간 역순 DFS로 각 트리가 정확히 하나의 SCC가 됨을 귀납적으로 증명하여 알고리즘의 완전성과 정확성 보장
|
||
|
[70강] 최소 신장 트리의 확장
|
0:
57:
13
|
|
|
최소 신장 트리와 절단, 안전간선 개념 정리• 최소 신장 트리(MST)와 Generic MST 알고리즘 : 신장 트리 정의(정점 동일·간선 |V|-1·연결·비순환)와 가중치 합 최소 조건, 안전간선만을 반복 추가한다는 루프 불변성을 통한 Generic MST 알고리즘의 정당성 구조• 절단(cut)·교차간선·경량간선·존중(respect) 개념 : 정점 집합을 둘로 나누는 절단, 절단을 가로지르는 교차간선, 그중 가중치가 최소인 경량간선 정의와 절단이 부분집합 A의 간선을 끊지 않을 때 “A를 존중한다”는 조건 정식화• 경량간선의 안전성 정리와 포리스트 관점 : 절단이 A를 존중할 때 그 절단 위의 경량간선이 항상 안전간선이 됨을 보이는 안전성 정리와, A가 이루는 포리스트의 각 연결요소 사이의 경량간선을 선택하면 Kruskal·Prim 알고리즘의 그리디 선택이 안전함을 보이는 따름정리 정리
|
||
|
[71강] 크루스칼 알고리즘과 프림 알고리즘. 안전성 정리
|
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 그리디 선택의 정당성, 두 알고리즘의 구조·자료구조·수행 시간 비교 원리 정리
|
||
|
[72강] 단일 출발지 최단 경로
|
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.π를 갱신하며, 삼각부등식·상한·무경로·수렴·경로완화 특성에 의해 알고리즘의 수렴성과 정당성을 보장함
|
||
|
[73강] 벨만-포드 알고리즘
|
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 = ∞는 경로 부재를 의미함
|
||
|
[74강] 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 최단경로 알고리즘을 최장경로 계산에 변형 적용함으로써 프로젝트 전체 기간을 결정하는 임계경로를 산출하는 기법
|
||
|
[75강] 다익스트라 알고리즘
|
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|)가 됨
|
||
|
[76강] 차이 제약 조건과 최단 경로
|
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)으로 분석
|
||
|
[77강] 최단 경로 특성의 증명 (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)에 도달하고 이후 불변이 되는 수렴·정당성 구조 정리
|
||
|
[78강] 최단 경로 특성의 증명 (2)
|
0:
42:
09
|
|
|
단일출발지 최단경로 알고리즘의 경로 완화와 직전원소 그래프 특성 요약• 경로 완화 특성(보조정리 24.15) : INITIALIZE‑SINGLE‑SOURCE와 RELAX 반복 시 최단경로 위 간선들을 경로 순서만 지켜 완화하면, 다른 간선 완화가 섞여도 각 정점 거리 추정값이 최단경로 거리로 수렴함• 직전원소 부분 그래프 트리 성질(보조정리 24.16) : 음의 가중치 순환이 없는 가중 방향 그래프에서 직전원소로 구성한 부분 그래프 Gπ는 RELAX 순서와 무관하게 항상 s를 루트로 하는 비순환 트리이며, 각 정점은 s로 가는 유일한 경로를 가짐• 최단경로 트리 정리(정리 24.17) : 모든 완화 종료 후 Gπ는 s에서 도달 가능한 모든 정점을 포함하며, Gπ 상의 s‑각 정점 경로가 원 그래프에서의 최단경로가 되므로 s를 루트로 하는 최단경로 트리 구조를 형성함
|
||
|
[79강] 최단 경로와 행렬 곱셈
|
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)까지 개선하는 알고리즘 설계 및 분석
|
||
|
[80강] 플로이드-워샬 알고리즘
|
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 경로 존재 여부를 계산하는 플로이드 워셜의 불리언 변형
|
||
|
[81강] 존슨 알고리즘
|
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)보다 효율적인 모든 쌍 최단경로 알고리즘으로 활용됨
|
||
|
[82강] 플로우 네트워크
|
0:
27:
26
|
|
|
플로우 네트워크와 최대 플로우 기본 개념 정리• 플로우 네트워크와 제약 구조: 방향 그래프에서 자가 루프·역평행 간선을 배제하고 단일 출발점·단일 도착점을 가지며, 각 간선에 비음수 용량을 부여한 자원 흐름 모델 정의• 용량·플로우·플로우 보존·플로우 값: 용량 함수와 플로우 함수를 통해 0 ≤ f(u,v) ≤ c(u,v) 제약과 중간 정점에서의 유입=유출 보존 조건을 만족시키고, 출발점 기준 유출량으로 플로우 값을 정의하여 최대 플로우 문제 설정• 절단·최소 절단과 네트워크 변환: 절단과 절단 용량을 통해 최대 플로우와 최소 절단 관계를 해석하고, 역평행 간선 제거 및 다중 출발점·도착점에 대한 가상 출발점·도착점 추가로 표준 최대 플로우 계산 가능한 네트워크로 변환하는 기법 정리
|
||
|
[83강] 포드 풀커슨 방법 (1)
|
0:
32:
04
|
|
|
Ford-Fulkerson 최대 유량 알고리즘: 잔여 네트워크와 증강경로 개념 정리• Ford-Fulkerson 방법: 잔여 네트워크에서 증강경로가 존재하는 동안 플로우를 증강하고, 더 이상 증강경로가 없을 때 현재 플로우를 최대 유량으로 확정하는 절차적 최대 유량 계산 방법• 잔여 용량·잔여 네트워크·증강경로: 잔여 용량은 정·역방향에서 추가 전송·회수가 가능한 유량을 정의하고, 잔여 네트워크는 잔여 용량이 양수인 방향만으로 구성되며, 증강경로는 s–t 간 최소 잔여 용량만큼 플로우를 증가시키는 단순 경로• 플로우 증강과 경로 선택: 잔여 네트워크에서 정의한 증강 플로우와 증강 함수를 통해 정·역방향 간선을 갱신하며 플로우 보존을 유지하고, 증강경로 선택에 따라 수행 횟수·효율은 달라지지만 적절한 조건에서 최종 최대 유량 값은 동일하게 수렴함
|
||
|
[84강] 포드 풀커슨 방법 (2)
|
0:
46:
12
|
|
|
최대플로우에서 증강함수와 증강경로, 잔여용량 정리 요약• 플로우 네트워크와 잔여 네트워크: 용량·플로우·용량 제약·플로우 보존으로 정의되는 플로우 네트워크와, 현재 플로우에 대한 정방향·역방향 잔여용량을 간선 가중치로 갖는 잔여 네트워크 구조 정리• 증강함수·증강경로·경로 플로우: 잔여 네트워크 플로우로부터 정의되는 증강함수 f↑f′의 식과 플로우 조건 만족 증명, 증강경로와 경로의 잔여용량·경로 플로우 정의 및 |f↑f′| = |f| + |f′| = |f| + c_f(p) 값 관계 정리• Ford–Fulkerson 이론적 근거: 잔여 네트워크에서 증강경로를 찾고 경로의 최소 잔여용량만큼 플로우를 증가시키면 항상 유효한 새 플로우가 되고 값이 정확히 c_f(p)만큼 증가함을 보조정리 26.2·따름정리 26.3으로 정당화함
|
||
|
[85강] 포드 풀커슨 방법 (3)
|
0:
42:
21
|
|
|
최대 플로우와 최소 절단 개념 및 정리 요약• 플로우 네트워크 절단·절단 용량·순 플로우: 정점 집합 분할을 통한 절단 정의, S→T 간선 용량 합으로 절단 용량 정의, S→T 플로우−T→S 플로우로 순 플로우 정의 및 모든 절단에 대해 순 플로우 값 = 전체 플로우 값 성질 정리• 절단 용량과 플로우 상한: 임의 플로우 값이 항상 모든 절단 용량을 넘지 못함을 용량 제약과 순 플로우 식으로 증명하고, 최소 절단 용량이 최대 플로우의 상한이 되는 구조 제시• 최대 플로우–최소 절단 정리: “최대 플로우 = 잔여 네트워크에 증강경로 없음 = 어떤 절단에서 플로우 값이 절단 용량과 같음”의 세 조건 동치성을 통해 최대 플로우 값과 최소 절단 용량이 항상 같음을 보이는 증명 구조 정리
|
||
|
[86강] 포드 풀커슨 방법 (4)
|
0:
28:
10
|
|
|
포드-풀커슨 알고리즘과 수행시간, 최악 사례 분석 요약 • 포드-풀커슨 알고리즘과 잔여 네트워크: 잔여 용량 기반 증강경로 반복 탐색으로 최대 유량 계산, 경로 용량·잔여 용량·증강경로 개념을 통해 유량 조정 구조화 • 최대 유량-최소 컷 정리: 증강경로 미존재 시 유량 값과 최소 컷 용량이 일치함을 통해 최대 유량 도달 판정 및 컷 기반 분석 정리 • 수행시간과 최악 사례: 수행시간 O(|E|·F*) 특성과 경로 선택에 따른 1씩 증가하는 최악 사례를 통해 비효율성 및 Edmonds-Karp 등 개선 알고리즘 필요성 제시
|
||
|
[87강] 포드 풀커슨 방법 (5)
|
0:
53:
11
|
|
|
애드몬드-카프 알고리즘의 최단경로 단조성 및 반복 횟수 분석• 에드몬드-카프 알고리즘 구조: 잔여 네트워크에서 모든 간선 가중치를 1로 두고 BFS로 최단 증강경로를 선택하여 포드-풀커슨을 구현하며, 이때 각 정점까지의 최단거리(간선 수 기준)는 증강이 진행되어도 감소하지 않는 단조 비감소 성질을 가짐• 결정적 간선 개념과 반복 상한: 증강경로 상 최소 잔여용량을 갖는 결정적 간선은 증강 후 사라졌다가 역방향 증강으로 재등장할 수 있으며, 동일 간선이 다시 결정적이 될 때마다 관련 정점까지의 최단거리가 최소 2씩 증가하므로 각 간선은 O(V)번만 결정적이 될 수 있고 전체 증강 횟수는 O(VE)로 제한됨• 시간복잡도 분석: 각 증강 루프마다 BFS 탐색과 경로 상 갱신이 O(E) 시간에 이루어지고, 증강 횟수가 O(VE)이므로 에드몬드-카프 알고리즘의 전체 시간복잡도는 O(VE^2)이며, 이는 최대 유량 값에 의존하는 포드-풀커슨 상한 O(E·|f*|)보다 입력 크기 기준 다항시간 보장을 제공함
|
||
|
[88강] 최대 이분 매칭
|
0:
53:
53
|
|
|
최대플로우와 이분 그래프 최대 매칭의 관계 요약• 이분 그래프와 매칭 개념: 정점 집합을 L, R로 분할한 이분 그래프에서 한 정점이 최대 하나의 간선만 포함되도록 선택한 간선 집합을 매칭이라 하고, 그 중 간선 수가 최대인 집합을 최대 매칭이라 정의• 이분 그래프 → 플로우 네트워크 변환과 정수성: 이분 그래프에 소스 s, 싱크 t를 추가해 s→L, L→R, R→t 방향 간선을 두고 모든 간선 용량을 1로 설정하면, 정수 용량 정리에 의해 플로우가 0/1 값을 가져 각 L–R 간선의 플로우 여부가 매칭 포함 여부와 일치• 최대 매칭–최대 플로우 일치와 알고리즘: 최대 매칭으로부터 s–t 플로우를 구성하고, 반대로 정수 최대 플로우로부터 매칭을 정의하면 두 크기가 항상 같으며, 변환된 네트워크에 Edmond–Karp 알고리즘을 적용해 이분 그래프 최대 매칭을 O(VE²) 시간에 계산 가능
|
||
| 7장. 알고리즘 분야의 중요한 토픽 | ||
|
[89강] 동적 멀티스레딩의 기본 (1)
|
0:
37:
35
|
|
|
멀티코어 병렬 컴퓨팅과 동적 멀티스레딩 기초 개념 정리• 병렬 컴퓨터 기본 개념: 프로세스·프로세서·스레드의 정의와 차이, 공유 메모리·분산 메모리 모델 구조와 결정성·비결정성 및 동기화·통신 비용 이슈 정리 • 동적 멀티스레딩 모델: 정적 스레딩 vs 동적 스레딩 비교, 운영체제·동시성 플랫폼·병렬 컴파일러에 의한 스레드 스케줄링·부하분산·중첩 병렬성·병렬 루프 관리 원리 • 동시성 키워드와 Fibonacci 예제: parallel·spawn·sync 키워드로 직렬 코드를 병렬화하는 구조, 재귀 Fibonacci 알고리즘의 재귀트리·중복 계산·시간복잡도 T(n)=Θ(Fₙ)=Θ(φⁿ) 분석 및 동적 프로그래밍·반복법 비교
|
||
|
[90강] 동적 멀티스레딩의 기본 (2)
|
0:
55:
03
|
|
|
멀티스레드 피보나치와 계산 DAG의 작업·범위·병렬성• 동적 멀티스레딩 피보나치와 중첩된 병렬성: spawn·sync 기반 재귀 알고리즘 구조, 계산 DAG의 정점·간선(생성·연속·호출·리턴)과 순차적 안정성을 통한 병렬 실행 모델 정식화 • 작업(work)·범위(span)·법칙들: 계산 DAG 전체 정점 수를 작업, 임계경로를 범위로 정의하고, 작업법칙 T_P ≥ T₁/P, 범위법칙 T_P ≥ T_∞로 수행시간 하한과 속도 향상 상한 분석 • 병렬성·속도 향상·병렬 완화성: 병렬성 T₁/T_∞로 효율적 프로세서 수 평가, 속도 향상 S_P = T₁/T_P와 완전 선형 속도 향상 조건 정리, 병렬 완화성으로 프로세서 수 대비 활용 가능 병렬도 판단
|
||
|
[91강] 동적 멀티스레딩의 기본 (3)
|
0:
44:
19
|
|
|
동적 멀티스레딩 그리디 스케줄러와 수행시간 상한, 병렬성 분석• 동적 멀티스레딩 성능 기초: 작업법칙·범위법칙·병렬성( T1, T∞, T1/T∞ ) 정의와 최상의 수행시간 조건, 속도 향상과 완화성 관계 정리• 그리디 스케줄러 이론: 중앙화 온라인 스케줄러 모델, 완전/불완전 단계 개념, 정리 27.1( TP ≤ T1/P + T∞ )과 정리 27.2( TP ≤ 2TP* ) 증명 구조 및 근사 최적 성능 보장• 멀티스레드 알고리즘 분석: Fibonacci 멀티스레드 알고리즘의 작업 T1(n)=Θ(φⁿ), 범위 T∞(n)=Θ(n), 병렬성 Θ(φⁿ/n) 도출과 높은 병렬성이 만드는 선형 속도 향상 가능성 분석
|
||
|
[92강] 동적 멀티스레딩의 기본 (4)
|
0:
51:
04
|
|
|
동적 멀티스레딩과 행렬 곱셈 병렬 알고리즘 핵심 정리• 동적 멀티스레딩 모델: spawn·sync·parallel 명령을 통한 중첩 병렬성 구성, parallel for의 분할정복 변환, 행렬–벡터 곱에서 작업 T1=Θ(n²), 범위 T∞=Θ(n), 병렬성 Θ(n) 분석• 경쟁 조건과 동기화: 공유 메모리 동시 쓰기에서 발생하는 race condition과 deterministic race 개념, x=x+1 예제를 통한 기계어 수준 경쟁, lock·critical section·세마포어·뮤텍스를 통한 mutual exclusion 구현• 프로세서 수와 병렬 최적화: T_P ≥ T1/P + T∞ 관계를 활용한 체스 예제 분석, 작업(T1)·범위(T∞) 트레이드오프, 목표 프로세서 수에 따른 병렬 알고리즘 구조 및 동기화 전략 설계 원칙 정리
|
||
|
[93강] 멀티스레드 행렬의 곱셈
|
0:
52:
20
|
|
|
동적 멀티스레딩 행렬곱셈과 분할정복·Strassen 분석 요약• 기본 행렬곱셈 멀티스레딩: 3중 루프 기반 $c_{ij}=\sum_k a_{ik}b_{kj}$ 계산을 동적 멀티스레딩으로 구현하여 작업 $T_1=\Theta(n^3)$, 범위 $T_\infty=\Theta(n)$, 병렬성 $\Theta(n^2)$ 분석 • 분할정복 행렬곱셈: $2\times2$ 블록 분할과 재귀 점화 $T(n)=8T(n/2)+\Theta(n^2)$로 작업 $T_1=\Theta(n^3)$, 범위 $T_\infty=\Theta((\log n)^2)$, 병렬성 $\Theta\!\left(\frac{n^3}{(\log n)^2}\right)$ 도출 • Strassen 멀티스레딩: 블록곱을 7개로 줄이는 재귀식 $T_1(n)=7T_1(n/2)+\Theta(n^2)$와 행렬 덧셈·뺄셈의 병렬화로 작업 $T_1=\Theta(n^{\log_2 7})$, 범위 $T_\infty=\Theta((\log n)^2)$, 병렬성 $\Theta\!\left(\frac{n^{\log_2 7}}{(\log n)^2}\right)$ 비교 분석
|
||
|
[94강] 멀티스레드 병합 정렬
|
0:
54:
01
|
|
|
멀티스레드 병합정렬과 병렬 병합 알고리즘 분석 요약• 알고리즘 분석·복잡도 개념: 멀티스레드 병합정렬의 정확성·수행시간을 점근적 표기(Big-Oh/Theta), 마스터 정리, 대입법으로 해석하고 작업(Work)·범위(Span)·병렬성 관계 정의• 멀티스레드 병합·머지 구조: 중앙 원소 선택·이분 탐색을 이용한 분할정복 병합으로 두 정렬 배열을 병렬 병합하고, 머지 작업 Θ(n)·범위 Θ(log²n)·병렬성 Θ(n/log²n) 확보• 완전 멀티스레드 병합정렬 성능 분석: 전체 정렬 작업 Θ(n log n), 범위 Θ(log³n), 병렬성 Θ(n/log²n)을 도출하고, 임계 크기(threshold) 설정·스레드 오버헤드 고려한 실무용 하이브리드 구현 전략 정리
|
||
|
[95강] 선형 연립방정식의 해 (1)
|
0:
41:
49
|
|
|
선형연립방정식과 가우스 소거, LUP 분해 개념 정리• 선형연립방정식과 정규행렬: 선형연립방정식을 $AX=B$로 표현하고, 역행렬이 존재하는 정규행렬과 단위행렬 개념을 통해 해의 존재·유일성 및 $X=A^{-1}B$ 구조 정리• 가우스 소거법과 LU/LUP 분해: 가우스 소거의 행 연산을 행렬 관점에서 해석하여 $A$를 단위행렬 또는 삼각행렬 곱 $A=LU$, $PA=LU$로 분해하는 절차와 목적(여러 $B$에 대한 효율적 해법) 정리• 삼각행렬, 순열행렬, 전진·후진대입 알고리즘: 하위·상위 삼각행렬과 순열행렬 $P$의 구조를 정의하고, $LY=PB$, $UX=Y$ 형태의 전진대입·후진대입 일반식 및 $L,U,P$를 이용한 선형시스템 해법 알고리즘 개요 정리
|
||
|
[96강] 선형 연립방정식의 해 (2)
|
0:
55:
21
|
|
|
LU분할과 LUP분할, 가우스 소거법 알고리즘 구조 요약• LU분할과 단위 삼각행렬: 계수 행렬 A를 단위 하위 삼각행렬 L과 상위 삼각행렬 U로 분해하여 가우스 소거와 동일 연산 구조로 전진 대입·후진 대입을 통해 연립방정식을 효율적으로 푸는 방법• 보조 행렬(Schur complement)과 알고리즘 구조: 피벗을 기준으로 A를 블록으로 분할해 $A' - VW^T/a_{11}$ 형태의 Schur 보조 행렬을 정의하고, 이를 점화식·분할정복 구조로 갱신하여 전체 LU분해를 $O(n^3)$ 연산량으로 수행하는 알고리즘• LUP분할과 피벗팅: 피벗이 0이거나 매우 작을 때 행을 교환하는 순열 행렬 P를 도입해 $PA=LU$로 분해하고, 각 열에서 절대값 최대 원소를 피벗으로 선택하는 partial pivoting을 통해 수치 안정성과 분해 가능성을 보장하며, $PA=LU$, $LY=PB$, $UX=Y$ 절차로 해를 구하는 구조
|
||
|
[97강] 역행렬
|
1:
00:
11
|
|
|
역행렬 계산과 행렬 곱셈의 수행시간 관계 정리 요약• 역행렬과 연립방정식, LUP분할: 역행렬을 AX = I, AX_i = e_i 형태 연립방정식 풀이로 해석하고 LUP분해 기반 역행렬·선형계 해법의 계산 복잡도 구조 정리• 행렬 곱셈·역행렬 계산 복잡도 정리: 특수 블록행렬 구성(정리 28.1)과 분할정복·Schur 보조행렬(정리 28.2)을 통해 행렬 곱셈 시간 M(n)과 역행렬 계산 시간 T(n)이 Θ(M(n))으로 점근적으로 동치임을 증명• 양의 정부 대칭·일반 정규행렬 역행렬 알고리즘: 양의 정부 대칭행렬의 블록 분해와 Schur 보조행렬 S를 이용한 재귀 역행렬 알고리즘, A^T A를 통한 일반 정규행렬 역행렬 A^{-1} = (A^T A)^{-1}A^T 구성 및 LU/LUP 분할 기반 선형계 해법의 이론·실무 효율 비교
|
||
|
[98강] 양으로 정의된 대칭 행렬과 최소-제곱 근사 (1)
|
0:
43:
17
|
|
|
양의 정부호 대칭행렬과 선두 부분 행렬·Schur 보조행렬 특성• 양의 정부호 대칭행렬: 모든 0이 아닌 벡터 x에 대해 xᵀAx>0을 만족하는 대칭행렬로, 정규행렬(역행렬 존재)이며 LU 분해에서 피벗팅 없이도 0으로 나누는 문제가 발생하지 않음 • 선두 부분 행렬(Leading principal submatrix): 대칭행렬 A의 상단 k개 행·열로 이루어진 부분행렬 Aₖ으로, A가 양의 정부호 대칭행렬이면 모든 Aₖ도 양의 정부호 대칭행렬이 되어 각 단계의 피벗이 양수임 • Schur 보조행렬(Schur complement): 블록 분할 A = [[Aₖ, Bᵀ],[B, C]]에서 S = C − Aₖ⁻¹BᵀB로 정의되는 보조행렬로, A와 Aₖ가 양의 정부호 대칭행렬이면 S도 양의 정부호 대칭행렬이 되어 블록 역행렬·LU 분해 알고리즘의 정당성을 보장함
|
||
|
[99강] 양으로 정의된 대칭 행렬과 최소-제곱 근사 (2)
|
0:
32:
34
|
|
|
최소제곱근사값과 양의 정부호 대칭행렬, LU분할 요약• 최소제곱근사값과 정규방정식: 데이터 점에 대한 다항식 근사를 설계행렬 A와 계수벡터 c로 표현하고, 오차벡터 η = A c − y의 2-노름 제곱을 최소화하여 정규방정식 AᵀA c = Aᵀy 및 가상역 A⁺ = (AᵀA)⁻¹Aᵀ을 통한 최소제곱해 c = A⁺y 도출• 양의 정부호 대칭행렬 성질: 정규행렬 A에 대해 AᵀA가 대칭·양의 정부호·비특이 행렬이 되어 모든 비자명 x에 대해 xᵀAᵀA x = ‖Ax‖² > 0을 만족하고, 피벗이 0이 되지 않아 역행렬 존재와 안정적 분해 가능• LU/LUP분해와 해법 구조: 일반 연립방정식 A x = b에는 부분 피벗을 포함한 LUP분해가 필요하지만, 최소제곱에서 얻는 AᵀA c = Aᵀy는 양의 정부호 대칭행렬이므로 LU 또는 Cholesky 분해와 전진·후진대입만으로 c를 계산하며, 예시로 5개 점에 대한 2차 최소제곱곡선 f(x) = 0.214 x² − 0.757 x + 1.2 구성
|
||
|
[100강] 선형 계획법
|
0:
35:
20
|
|
|
선형계획법과 정치 캠페인 예제의 수학적 모형화 핵심 정리• 선형계획 모형 구조: 선형 목적함수·선형제약조건·의미 아닌 제약조건으로 의사결정 문제를 수학적으로 표현하고 가능영역·최적해·목표값 개념으로 해를 정의하는 방법론• 기하학적·알고리즘적 해석: 2차원에서는 제약의 교집합인 볼록 다각형 가능영역과 목적함수 직선의 교점을 통해 정점에서 최적해를 찾고, 고차원에서는 볼록 다면체 정점들을 심플렉스 방법으로 탐색하여 최적해를 도출하는 절차• 응용 및 모형화 사례: 정치 캠페인 득표·비용 최소화, 승무원 편성, 자원 배분·채굴 등에서 변수 정의, 목적함수 설정, 집단·자원 제약식을 선형식으로 구성해 전략·정책 결정을 지원하는 응용 구조
|
||
|
[101강] 정규형과 이완형
|
0:
59:
57
|
|
|
선형계획법 정규형과 이완형, 심플렉스 준비 개념 정리• 정규형 선형계획법: 최대화 목적함수·모든 제약식 ≤ 형식·모든 변수 의미 아닌 조건(x≥0) 구조와 비정규형을 정규형으로 바꾸기 위한 동치 변환(목적함수 부호 변환, 자유변수의 양·음 분리, 등식·≥ 제약의 ≤ 부등식 변환) 정리 • 이완형(slack form) 구조: 정규형 부등식 제약에 이완 변수 추가로 등식+의미 아닌 조건으로 변환, 이완 변수의 여유분(slack) 의미·변수 개수 증가(n→n+m)·정규형 계수와 이완형 계수의 부호 관계(a'_{ij} = -a_{ij}) 정리 • 심플렉스 알고리즘 준비 개념: 기본 변수와 기본 아닌 변수의 구분, 인덱스 집합 B·N 정의와 크기(|B|=m, |N|=n), 이완형 상태 표현 튜플(N,B,A,b,c,v)의 구조와 피벗 연산을 통한 최적해 탐색 기반 정리
|
||
|
[102강] 문제의 선형 계획법 구성
|
0:
41:
06
|
|
|
최단경로·최대플로우·최소비용·다중상품 플로우의 선형계획법 구성 요약• 최단경로 선형계획 표현: 정점별 거리변수 d_v와 제약 d_v ≤ d_u + w(u,v), d_s = 0을 사용해 음의 순환이 없는 그래프에서 d_t 최대화를 통해 최단경로 길이 도출• 최대플로우·최소비용 플로우 선형계획 표현: 간선별 플로우 f(u,v)를 두고 용량 제약, 플로우 보존, (필요 시) 지정 플로우량 제약을 포함하여 플로우 값 최대화 또는 ∑ a(u,v)f(u,v) 최소화로 네트워크 흐름 최적화• 다중상품 플로우 선형계획 표현: 상품별 플로우 변수 f_i(u,v), 총 플로우 ∑_i f_i(u,v) ≤ c(u,v)와 상품별 플로우 보존·요구량 제약을 통해 여러 상품이 간선을 공유하는 네트워크에서 실현가능성·비용최적 배치 모델링
|
||
|
[103강] 심플렉스 알고리즘 (1)
|
0:
57:
56
|
|
|
심플렉스 알고리즘 예제와 피벗 연산 원리 요약(최적해 도달 과정 중심)• 정규형 선형계획과 이완형·기본해: 정규형을 이완형으로 변환하고 이완변수를 기본변수로 두어 초기 기본해를 구성, 목적함수를 기본/비기본 변수 분해 표현• 진입·진출변수 선택과 피벗 절차: 목적함수에서 양의 계수 기본아닌변수를 진입변수로 선택, 최소비율 규칙으로 진출변수 결정 후 피벗으로 기본/비기본 집합 교환 및 계수·우변·목적값 갱신• 피벗 일반식·최적성·보조정리 29.2: 피벗 후 새로운 A,B,c 갱신식과 기본해 계산식 정식화, 모든 기본아닌변수 0·갱신된 기본변수 값의 타당성 증명, 목적함수 계수 비양수이면 최적해 및 이완변수의 slack 의미 확립
|
||
|
[104강] 심플렉스 알고리즘 (2)
|
0:
52:
32
|
|
|
선형계획법 심플렉스 알고리즘의 공식화와 타당성 검증 요약• 심플렉스 알고리즘 구조: 표준형 선형계획에서 기본/비기본 변수와 이완형 표현을 사용해 피벗 연산으로 목적함수 값을 단계적으로 증가시키며, (N,B,A,b,c,v) 6-튜플 상태 전이를 통해 가능한 기본해·최적해·언바운디드 상태를 탐색하는 알고리즘• 가능해·기본해·언바운디드 개념 및 판정: b_i ≥ 0과 x_j ≥ 0을 만족하는 기본해를 가능한 기본해로 정의하고, c_j ≤ 0이면 현재 기본해를 최적해로 종료하며, 진입 변수에 대해 a_{ie} > 0 인 제약이 없어 증가한계가 무한대가 되면 목적함수 상계 부재(unbounded)를 판정하는 절차• 피벗 연산과 타당성(루프 불변성) 증명: 진입·진출 변수 교환과 등식 치환을 통해 이완형의 동등성을 유지하며 b_i ≥ 0 조건과 기본해 가능성을 귀납적으로 보존하는 루프 불변성을 설정해, 종료 시 알고리즘이 최적해 또는 언바운디드 판정을 올바르게 반환함을 보이는 타당성 검증 구조
|
||
|
[105강] 심플렉스 알고리즘 (3)
|
0:
31:
43
|
|
|
심플렉스 알고리즘 종료 조건과 순환 방지 요약• 심플렉스 알고리즘 종료성 구조: 목적함수 증분식·피벗 연산·목표값 비감소 조건을 통해 유한 반복 내 종료 여부와 사이클링 발생 메커니즘 정리• 이완형 유일성과 개수: 선형식 계수 유일성 보조정리로 기본변수 집합당 이완형의 유일성을 증명하고, 가능한 이완형 개수를 조합식 𝑪(n+m, m) 으로 한정하여 순환 발생 조건을 규명• 피벗 선택 규칙과 종료 형태: b_ℓ=0 피벗 회피 및 최소 인덱스 규칙으로 순환을 방지하고, 심플렉스 알고리즘이 최대 𝑪(n+m, m) 회 반복 이내에 언바운디드 판정 또는 유한 최적해 반환 두 형태 중 하나로 종료함을 정리
|
||
|
[106강] 쌍대성
|
1:
02:
16
|
|
|
선형계획법 정규형과 쌍대형, 심플렉스 최적해의 쌍대성 검증 개념 정리• 정규형·쌍대형 선형계획법 구조: 최대화 정규형과 최소화 쌍대형의 목적함수·제약식·변수 대응(변수↔제약식, A 전치, b_i↔c_j, ≤↔≥)을 통한 쌍대 모형 구성 원리• 약한 쌍대정리와 최적해 동치성: 모든 가능한 해에 대해 c^T x ≤ b^T y 관계 성립 및 c^T x = b^T y 성립 시 정규형·쌍대형이 동시에 최적해가 됨을 보이는 증명 구조• 심플렉스 최종 이완형과 쌍대해 구성: 최종 이완형에서 기본 아닌 이완변수 계수 c_{n+i}'를 이용한 y_i = -c_{n+i}' 정의, Ay ≥ c·y ≥ 0 검증, b^T y = 정규형 최적값 일치로 쌍대 최적해 판정 과정
|
||
|
[107강] 초기 가능한 기본 해
|
0:
56:
10
|
|
|
Summary Content:선형계획법 가능 여부와 보조선형계획법 및 Initialized Simplex 정리 요약• 정규형 선형계획법과 가능성 판정: 모든 제약을 ≤, 변수 비음수로 두고 초기 기본해 존재 여부와 가능 영역 유무, 목적함수의 한계 존재 여부(Feasible·Infeasible·Unbounded)로 문제 상태를 분류함 • 보조선형계획법(LAUX): 음수 b_i로 초기 기본해가 불가능할 때 x₀를 도입해 -x₀ 최대화를 구성하고, LAUX의 최적값이 0일 필요충분조건(0 ↔ 원래 문제 가능)을 이용해 가능한 초기 이완형을 만들고 x₀를 제거해 원래 문제로 복원함 • Initialized Simplex 알고리즘: min b_i ≥ 0이면 바로 기존 이완형을 사용하고, min b_i < 0이면 LAUX를 구성해 첫 피벗 후 심플렉스를 수행하여 x₀=0 가능 여부로 Infeasible를 판정하고, 가능 이완형에 대해서는 일반 심플렉스로 Unbounded 또는 유한 최적해를 도출함
|
||
|
[108강] 다항식의 표현
|
0:
57:
24
|
|
|
다항식 곱셈과 고속 푸리에 변환 개요 정리• 다항식과 표현 방식: 차수·차수한계, 컨볼루션 구조의 다항식 곱셈(Θ(n²)), 계수표현·점값표현 및 점계산·보간과 유일성 정리(반더몬드 행렬) 정리• 계수↔점값 변환 복잡도: Horner 방법에 의한 점계산 Θ(n²), 일반 보간 Θ(n³) 한계와 이를 극복하기 위한 복소수 단위근 선택·DFT 관점의 계수↔점값 변환 구조 제시• FFT 기반 고속 곱셈: 2n차 복소수 단위근을 이용한 DFT/역 DFT 계산(각 Θ(n log n)), 점값 영역 성분별 곱셈(Θ(n))으로 전체 다항식 곱셈 복잡도를 Θ(n log n)으로 감소시키는 정리 30.2의 절차적 틀 정리
|
||
|
[109강] DFT와 FFT (1)
|
0:
59:
11
|
|
|
복소 단위근과 이산 푸리에 변환(DFT) 기초 정리 요약• 복소수 극좌표와 단위근: 복소수의 극좌표·오일러 공식 기반으로 단위원 위 n번째 단위근 ωₙᵏ = e^{2πik/n} 정의, 지수의 모듈러 n 산술과 곱셈·제곱의 각도 해석 정리• 단위근 구조와 보조정리: 단위근 집합의 군 구조, 짝수 n에서의 제곱·대칭·부호 반대 관계, ω_{dn}^{dk} = ω_n^k 및 단위근 합 Σ_{j=0}^{n-1}ωₙ^{kj}=0 (k≢0 mod n) 등 FFT에 필요한 핵심 보조정리 정리• DFT 정의와 FFT 연결: DFT를 y_k = Σ_{j=0}^{n-1} a_j ωₙ^{kj}, 행렬 Fₙ을 통한 y = Fₙa로 정의하고, n=2^k 가정·패딩 및 단위근 대칭 성질을 이용해 분할정복 고속푸리에변환(FFT)로 다항식 곱셈을 Θ(n log n)에 수행하는 기반 제시
|
||
|
[110강] DFT와 FFT (2)
|
0:
51:
58
|
|
|
고속 푸리에 변환 FFT와 다항식 곱셈, 역변환 보간법 요약• FFT와 다항식 분할정복 구조: 계수형 다항식을 짝수/홀수 인덱스 분할과 복소수 단위근의 제곱·대칭 성질을 이용해 점값 표현으로 변환하는 재귀 FFT 알고리즘과 수행시간 $O(n\log n)$ 구조 정리• DFT 행렬과 역 DFT(보간법): DFT 행렬 $B_n$의 엔트리 구조와 역행렬 $B_n^{-1}$의 형태를 통해 점값 표현에서 계수 복원을 수행하는 역 DFT 공식을 행렬 관점에서 정식화• 컨볼루션 정리와 FFT 기반 다항식 곱셈: 다항식 계수 컨볼루션과 FFT·역 FFT를 이용한 점별 곱셈 절차를 연결하여 전체 다항식 곱셈을 $O(n^2)$에서 $O(n\log n)$으로 개선하는 알고리즘 구조 정리
|
||
|
[111강] 효율적인 FFT의 구현
|
0:
30:
22
|
|
|
FFT 반복 알고리즘과 비트 역순, 병렬화 개념 정리• 반복형 FFT 구조: 재귀 FFT를 반복 루프 기반 구조로 변환하여 스택 오버헤드 제거, 나비 연산을 기본 단위로 사용하는 단계별 DFT 구성• 비트 역순 재배열과 인덱싱: 인덱스를 이진수로 표현 후 비트 역순으로 재배열하여 iterative FFT의 메모리 상 데이터 순서 정렬 및 단계별 블록(2^s) 인덱스 체계 확립• 시간·병렬 복잡도 분석: 비트 역순 재배열과 단계별 나비 연산을 합쳐 Θ(n log n) 시간 복잡도 도출, 병렬화 시 Work = Θ(n log n), Span = Θ(log n)으로 높은 병렬 효율 확보
|
||
|
[112강] 기초 정수론
|
0:
53:
35
|
|
|
정수론 알고리즘: 나눗셈, 모듈로, 최대공약수 기초 정리• 정수론 기본 개념: 나누어짐과 약수·배수 표기(D∣A), 인자·공약수·최대공약수·서로소 정의 및 범위, 소수·합성수 분류와 소수의 약수 구조 정리 • 나눗셈 정리와 모듈로 구조: a = qn + r의 유일한 표현, 모듈로 연산 a mod n 정의, 동치류 [a]ₙ과 동치 b ≡ a (mod n), 기본 대표자 집합 Gₙ = {0,…,n−1}을 통한 정수 집합 분할 구조 정리 • 최대공약수와 선형결합·소인수분해: gcd(a,b)의 공약수 성질과 범위, 베주 정리(gcd(a,b)=ax+by) 및 선형결합 최소 양수 특성, 배수에 대한 gcd 성질(gcd(an,bn)=n·gcd(a,b)), 소수가 곱을 나누는 성질과 유일 인수분해 정리(N=∏Pᵢ^{eᵢ}) 및 RSA 등 암호 이론의 기반 개념 정리
|
||
|
[113강] 최대공약수
|
1:
06:
55
|
|
|
유클리드 알고리즘과 확장 유클리드 알고리즘, 수행시간 분석 핵심 정리• 최대공약수 구조와 유클리드 알고리즘: 자연수의 유일 소인수분해와 지수의 최솟값 규칙으로 gcd 구조를 정의하고, 나눗셈 정리 기반 재귀식 gcd(A,B)=gcd(B,A mod B)와 그 정당성을 선형결합·공약수 보존 성질로 증명함 • 유클리드 알고리즘 수행시간 분석: 피보나치 수열과 보조정리, 레이머 정리를 사용해 재귀 호출 횟수를 입력 크기에 대한 Θ(log max(A,B))로 상한·하한 분석하고 최악·평균 시간복잡도 구조를 정리함 • 확장 유클리드 알고리즘과 베주 항등식: 베주 항등식 Ax+By=gcd(A,B)를 만족하는 정수해 계산을 위해 기본 유클리드 재귀 구조에 계수 갱신식 x=y′, y=x′−y′⌊A/B⌋을 도입하고, 베이스 케이스와 역추적 절차로 베주 계수 산출 과정을 정리함
|
||
|
[114강] 모듈로 연산 (1)
|
0:
53:
54
|
|
|
Summary Content:모듈러 연산과 군, 덧셈군·곱셈군, 오일러 파이 함수 개념 정리• 군과 아벨군: 닫힘성·항등원·역원·결합법칙(군), 교환법칙(아벨군)을 만족하는 대수 구조 정의 및 유한군 개념 정리• 모듈러 덧셈군·곱셈군: $G_n$과 $G_n^\*$의 정의, 서로소 조건·zero divisor 제거 이유, 역원·나눗셈(역원 곱셈)과 Extended Euclidean Algorithm을 통한 모듈러 역원 계산 구조 정리• 오일러 파이 함수: $\varphi(n)=|G_n^\*|$로서 $n$과 서로소인 정수의 개수, 소인수 분해 기반 일반 공식과 소수 $p$에 대한 $\varphi(p)=p-1$ 계산 원리 정리
|
||
|
[115강] 모듈로 연산 (2)
|
1:
02:
15
|
|
|
유한군에서의 서브군, 라그랑주 정리, 원소의 차수 개념 정리• 서브군과 판정 조건: 군의 부분집합이 닫힘·항등원 포함·역원 존재·결합법칙을 만족할 때 서브군이 되며, 유한군에서는 닫힘과 항등원 포함만으로도 역원 존재가 따라옴 • 라그랑주 정리와 진 서브군: 유한군의 임의의 서브군 크기는 군 크기의 약수이고, 진 서브군의 크기는 군 크기의 1/2 이하이며, 각 서브군은 코셋 분할을 통해 군 전체를 분해함 • 생성 서브군·원소의 차수·주기성: 한 원소가 만드는 생성 서브군의 원소 개수가 그 원소의 차수와 같고, 해당 수열은 차수 길이의 주기를 가지며, 이로부터 ord(A) | |S| 및 A^{|S|}=e (또는 |S|·A가 항등원) 성질과 지수의 모듈러 동치 관계가 도출됨
|
||
|
[116강] 모듈로 선형 방정식의 해
|
1:
03:
57
|
|
|
모듈러 선형방정식의 해, 존재 조건과 해의 개수·구하는 알고리즘• 모듈러 선형방정식 구조: 방정식 ax ≡ b (mod n)의 집합·서브군 표현, d = gcd(a,n)일 때 생성 서브군 원소가 0,d,2d,…,(n/d−1)d 꼴이 되는 구조 정리• 해 존재 조건·개수: ax ≡ b (mod n)의 해 존재 필요충분조건 d ∣ b, 해 존재 시 서로 다른 해의 개수 d개, 해의 일반형 x_i ≡ x_0 + i·(n/d) (mod n), i=0,…,d−1의 주기 구조 정리• Extended Euclid 알고리즘과 역원: extended Euclid로 ax′+ny′=d에서 x_0 ≡ x′·(b/d) (mod n)으로 한 해 및 모든 해를 구하는 절차, gcd(a,n)=1일 때 유일해와 모듈러 역원 ax ≡ 1 (mod n)의 존재·계산 방법 정리
|
||
|
[117강] 중국인의 나머지 정리
|
0:
39:
33
|
|
|
중국인의 나머지 정리와 구조 정리 개념 요약• 중국인의 나머지 정리: 서로소인 모듈러 집합 {N_i}에 대해 나머지 조건 A ≡ A_i (mod N_i)의 해 존재·유일성과 0 ≤ A < N에서의 표현 보장, N = ∏N_i에서의 정수 구조 기술 • 구조 동형·구성 알고리즘: 사상 A ↦ (A mod N_1,…,A mod N_k)을 통한 𝕫_N ≅ 𝕫_{N_1} × … × 𝕫_{N_k} 동형, M_i = N/N_i와 곱셈역을 이용한 C_i 구성 및 A ≡ Σ A_i C_i (mod N) 복원 알고리즘 정리 • 연산 보존·응용: 덧셈·곱셈의 좌표별 보존으로 큰 모듈러 연산을 작은 모듈러 연산으로 분할·병렬화하고, 수론·암호·알고리즘 설계에서 효율적 계산 구조 제공
|
||
|
[118강] 원소의 거듭제곱
|
1:
07:
11
|
|
|
원소 거듭제곱과 오일러·페르마 정리, 모듈러 지수 알고리즘 개요• 모듈러 곱셈군 구조와 정리: 곱셈군 \(G_n^*\), 원소의 오더(order), 오일러 파이 함수 \(\varphi(n)\), 라그랑주 정리에 기반한 오일러 정리와 페르마의 소정리 관계 정리• 순환군과 이산대수: 원시근과 순환군 구조, 이산로그(인덱스) 정의, \(g^x\equiv g^y\pmod n \Leftrightarrow x\equiv y\pmod{\varphi(n)}\) 지수 비교 정리 및 RSA 등 공개키 암호의 이론적 기반• 합성수 판정과 모듈러 지수 알고리즘: trivial/non-trivial 제곱근을 이용한 합성수 판정 아이디어와 인수분해 연계, 이진 지수 표현을 이용한 반복제곱 기반 모듈러 지수(modular exponentiation) 알고리즘 구조·시간복잡도·루프 불변식 이해
|
||
|
[119강] RSA 공개키 암호 시스템
|
0:
48:
29
|
|
|
RSA 공개키 암호 시스템의 원리와 수학적 정확성 개요 • 공개키 암호 시스템·전자서명 구조: 공개키·비밀키 역함수 관계를 이용한 메시지 암·복호화, 전자서명·검증 및 서명·암호화 결합을 통한 기밀성·인증·무결성·부인 방지 확보 방식 정리 • RSA 수학적 구조: 두 큰 소수 p, q 선택과 n = pq, 오일러 파이함수 φ(n) = (p-1)(q-1), 공개지수 e와 비밀지수 d( ed ≡ 1 mod φ(n) )를 이용한 C = M^e mod n, M = C^d mod n 역함수 구성 • RSA 정확성·안전성 근거: 오일러 정리·페르마의 소정리·중국인의 나머지 정리를 통한 M^{ed} ≡ M (mod n) 정확성 증명과, 큰 정수 소인수분해 계산 복잡도 및 비밀키 관리·키 길이·구현 이슈에 기반한 안전성·한계 정리
|
||
|
[120강] 스트링 매칭 문제. 단순 스트링 매칭 알고리즘
|
0:
38:
36
|
|
|
문자열 패턴 매칭 기본 개념과 단순 스트링 매칭 알고리즘 정리• 스트링 매칭 문제와 형식적 모델: 텍스트 T, 패턴 P, 알파벳 집합 Σ, 문자열 집합 Σ*, 문자열 길이 |x|, Shift S 개념을 이용해 패턴의 모든 발생 위치를 찾는 문제 구조 정의• 문자열 구조와 이론 요소: 접두부·접미부, 부분 문자열 P_k, 중복 접미부 보조정리, 문자열 비교 연산 모델을 통해 KMP 등 선형 시간 알고리즘의 전처리·부분 일치 길이 계산 이론 기반 정리• 스트링 매칭 알고리즘 분류와 복잡도: 단순 스트링 매칭의 전처리 부재·모든 Shift 직접 비교·최악 시간복잡도 Θ(NM) 특징과 Rabin-Karp, Finite Automata, KMP, Boyer-Moore 등 전처리·이력 정보 활용 기반 선형 시간 급 알고리즘 개관
|
||
|
[121강] 라빈-카프 스트링 매칭
|
0:
41:
58
|
|
|
라빈 카프 문자열 매칭 알고리즘과 Horner 법칙, 모듈러 연산 핵심 정리• 라빈 카프 알고리즘 핵심 개념: 문자열을 D진수 정수(또는 모듈러 값)로 표현하고 Horner 법칙과 슬라이딩 윈도우로 각 위치 해시를 상수 시간에 갱신하여 패턴 매칭을 수행하는 알고리즘 구조• 모듈러 연산과 가짜 적중: 큰 정수 폭발을 방지하기 위해 소수 Q에 대한 모듈러 연산을 사용하고, 해시 값이 같을 때만 실제 문자열 비교로 가짜 적중(false hit)과 유효 매칭을 판별하는 검증 절차• 수행시간 및 한계: 전처리 Θ(m), 평균적 매칭 O(n), 최악 O(nm) 복잡도를 가지며, 문자 집합 크기에 따라 D와 Q 선택이 성능에 큰 영향을 주어 ASCII/알파누메릭에는 유리하지만 대규모 유니코드 환경에서는 비효율적이라는 적용 한계가 존재함
|
||
|
[122강] 유한 오토마타를 이용한 스트링 매칭 (1)
|
1:
03:
56
|
|
|
유한 오토마타 기반 스트링 매칭 핵심 정리 및 전이함수 개념 정리 • 유한 오토마타와 상태 의미: 유한 오토마타 M = (Q, Σ, δ, q₀, F) 구조와 시작·종결 상태를 정의하고, 상태 q를 “텍스트 접미부와 패턴 접두부의 최대 일치 길이 q”로 해석하는 스트링 매칭용 상태 설계 개념 정리 • 접두부 길이 함수와 최종 상태 함수: 접두부 길이 함수 σ(x)를 “x의 접미부이자 패턴 P의 접두부인 부분 중 최장 길이”로 정의하고, 최종 상태 함수 φ(T)를 시작 상태에서 스트링 T를 처리한 도달 상태로 두며, 상태 번호를 통해 φ(x)와 σ(x)를 1:1로 대응시키는 구조 제시 • 전이함수와 오토마타 매칭 절차: 패턴 길이 m에 대해 Q={0,…,m}, F={m}으로 두고 δ(q,a)=σ(P_q a) 관계로 전이함수를 정의하여 O(m|Σ|) 전처리로 전이 테이블을 구성하고, 텍스트를 한 번 스캔하며 δ를 반복 적용해 accepting state 도달 여부로 패턴 매칭을 판정하는 알고리즘 구조 설명
|
||
|
[123강] 유한 오토마타를 이용한 스트링 매칭 (2)
|
1:
09:
58
|
|
|
Finite Automata 기반 패턴 매칭 알고리즘과 전이함수 정리• Finite Automata 패턴 매칭 알고리즘 구조: 상태 전이함수 δ와 상태 번호를 통해 패턴 접두부 매칭 길이를 상태로 표현하고, 텍스트를 1패스 O(n)으로 스캔하며 종료 상태 도달 시 패턴 발생 위치를 검출하는 절차• 시그마 함수·보조정리·정리 32.4: 시그마 함수 σ(X)를 “텍스트 접미부와 패턴 접두부 최대 일치 길이”로 정의하고, 보조정리 2·3과 정리 32.4를 통해 σ, 상태 함수 Φ, 전이함수 δ 사이의 동치 관계와 오토마타 매칭 알고리즘의 올바름을 논리적으로 증명하는 이론적 근거• 전이함수 구성 알고리즘과 복잡도·KMP 연결: 각 상태 q와 문자 a에 대해 P_q a의 접미부와 패턴 접두부 최대 일치 길이 k를 구해 δ(q,a)=k로 테이블화하는 알고리즘, 이 과정의 시간·공간 복잡도 및 큰 알파벳에서의 한계를 분석하고 이를 개선하는 KMP 알고리즘의 실패 함수 개념으로 연결하는 내용
|
||
|
[124강] 크누스-모리스-프랫 알고리즘
|
0:
58:
05
|
|
|
KMP 알고리즘과 접두부 함수 개념 정리• KMP 알고리즘과 유한 오토마타 패턴 매칭: 전이함수 대신 패턴 기반 접두부 함수(π 함수)를 사용해 전처리 비용과 메모리를 줄이면서도 매칭 단계는 선형 시간으로 수행하는 문자열 패턴 매칭 알고리즘 구조 정리• 접두부 함수(π 함수): 부분 문자열 P[1..i]의 접미부이면서 동시에 전체 패턴 P의 접두부인 부분 문자열 중 가장 긴 길이를 저장해 불일치 시 최소 shift를 결정하고 패턴 재비교를 줄이는 핵심 테이블 정의·의미·선형 시간 계산 절차 정리• KMP 전처리·매칭 알고리즘과 복잡도: π 테이블 O(m) 전처리와 이를 활용한 텍스트 매칭 O(n) 절차, q 갱신 규칙과 shift 원리, 그리고 유한 오토마타 방식과의 전처리 시간·공간 복잡도 비교를 통한 전체 성능 O(m+n), 메모리 O(m) 구조 정리
|
||
|
[125강] 보이어-무어 알고리즘
|
0:
41:
42
|
|
|
보이어-무어 알고리즘과 휴리스틱 패턴 매칭 정리• 보이어-무어 알고리즘 구조: 패턴의 끝에서 시작하는 역방향 비교와 문자 집합 기반 점프 테이블을 이용해 평균 비교 횟수를 줄이는 문자열 패턴 매칭 기법• 점프 테이블 및 수행시간: 각 문자에 대해 패턴 끝으로부터의 최소 거리를 저장한 점프 테이블로 쉬프트 길이를 결정하며, 최악 시간 복잡도는 O(MN), 평균적으로는 선형 이하에 가까운 효율 달성• 휴리스틱 패턴 매칭: 불일치 문자 휴리스틱(bad-character)과 일치 접미부 휴리스틱(good-suffix)을 결합해 두 쉬프트 값 중 더 큰 값을 선택함으로써 실질적 점프 폭을 최대화하고 영어 등 소규모 문자 집합에서 특히 높은 성능 확보
|
||
|
[126강] 선분의 특징
|
0:
52:
47
|
|
|
컴퓨테이셔널 지오메트리: 선분, 벡터곱, 방향 판단과 교차 판정 요약• 2D 벡터·선분 기초 개념: 선분의 볼록 조합 표현, 방향선분 정의, 2D 벡터곱/행렬식으로 면적과 시계·반시계·공선 판정 구조 이해• 방향·회전 판정 원리: 기준점 이동 후 벡터곱 부호로 기준 선분 대비 방향, 세 점의 좌·우회전(직진 포함) 판정 및 Convex Hull 등 알고리즘의 기본 연산 정리• 선분 교차 알고리즘: Direction·OnSegment 함수와 벡터곱 부호·좌표 범위 조건을 이용한 일반 교차·경계 교차(끝점 포함) SegmentIntersection 절차 통합 정리
|
||
|
[127강] 선분의 교차성 결정
|
0:
58:
51
|
|
|
선분 교차성 결정 알고리즘과 스위핑 구조 요약• 선분 교차성 판정 문제와 스위핑 구조: 수직선분·다중 교차 배제 전제에서 검사선·사건점·검사선 상태 개념을 사용해 선분 교차 여부를 효율적으로 판정하는 문제 구조와 정의• 검사선 상태 자료구조와 인접 선분 관리: 사건점에서 검사선을 지나는 선분들을 y-좌표 기준 전체 순서로 유지하고, 레드블랙트리(삽입·삭제·Above·Below 연산 O(log n))로 인접 선분 쌍만 비교하여 교차 후보를 관리하는 절차• Any Segment Intersect 알고리즘과 성능·정당성: 끝점 정렬 규칙(동일 x에서 왼쪽 끝점·작은 y 우선), 시작·끝 사건 처리 시 인접 쌍 교차 검사, 가장 왼쪽·아래 교차점을 이용한 코렉트니스 증명과 전체 시간 복잡도 O(n log n) 분석
|
||
|
[128강] 볼록 껍질의 발견
|
0:
57:
31
|
|
|
계산기하학 볼록 다각형과 Convex Hull, Graham Scan과 Jarvis March• 볼록 다각형·Convex Hull 개념: 다각형·볼록/오목 다각형 정의와 성질, 점 집합을 포함하는 최소 볼록 다각형(Convex Hull)의 수학적 정의와 문제 설정• Graham Scan 알고리즘: 기준점 선택과 편각 정렬, 스택과 벡터 외적을 이용한 좌·우회전 판정, 루프 불변식 기반 정확성 증명과 전체 시간 복잡도 O(n log n)• Jarvis March 알고리즘: Gift Wrapping 방식의 단계별 다음 정점 선택 절차, 오른쪽·왼쪽 체인 구성, Hull 정점 수 h에 따른 시간 복잡도 O(nh)와 Graham Scan과의 성능 비교
|
||
|
[129강] 가장 가까운 점들의 쌍 구하기
|
0:
39:
16
|
|
|
최근접 점 쌍 문제와 분할정복 알고리즘의 최적화• 최근접 점 쌍 문제와 분할정복 구조: 유클리드 거리 기준 최근접 점 쌍 탐색을 위해 점 집합을 X좌표로 반씩 분할·재귀(점 3개 이하 기저), 교차 쌍 보정을 포함한 결합 단계로 전체 최소 거리 계산• 시간복잡도 최적화와 사전 정렬·Split: 초기 1회 X·Y좌표 사전 정렬 후 재귀 단계마다 정렬 없이 X배열 분할과 Y배열 Split만으로 부분 배열 구성해 점화식 T(n)=2T(n/2)+O(n) 확보, 마스터 정리로 O(n log n) 달성• 델타 띠와 7개 비교 원리: 부분문제 최소거리 δ를 기준으로 폭 2δ 수직 띠 내 Y정렬 후보만 추려 각 점당 상수(최대 7개) 이웃 거리만 비교함으로써 교차 쌍까지 정확히 탐색하면서 각 단계 O(n) 결합 보장
|
||
|
[130강] NP-완비문제
|
0:
41:
19
|
|
|
NP 완비성, P와 NP, 결정문제와 환원 개념 정리• 계산복잡도 클래스(P, NP, NP 완비) 정의: P는 다항시간에 해를 구할 수 있는 결정문제 집합, NP는 해 후보를 다항시간에 검증 가능한 결정문제 집합, NP 완비는 NP에 속하면서 NP 중 가장 어려운 대표 문제 집합으로 그래프 경로 문제(최단경로·오일러 경로 vs 최장 경로·해밀토니안 순환)와 논리식 만족성(2-SAT/P, 3-SAT/NP 완비) 등의 전형적 예시 포함• 결정문제·최적화 문제 구분: 결정문제는 예/아니오 형태 답을 갖는 문제로 P·NP·NP 완비를 정의할 때의 표준 형식이며, 최단경로 길이 최소화 등 값을 요구하는 최적화 문제와 대응 관계를 가지며, 대응 결정문제가 어렵다면 최적화 문제는 적어도 그만큼 어렵다고 간주함• 환원과 NP 완비 증명 구조: 문제의 입력 사례를 다항시간에 다른 문제의 사례로 변환하여 답이 항상 보존되도록 하는 다항시간 환원 개념을 사용하고, 이미 NP 완비로 알려진 결정문제에서 새 결정문제로 환원함으로써 새 문제가 NP 문제이면서 기존 NP 완비 문제들만큼 어렵다는 것을 보여 NP 완비성·NP-hard성을 증명함
|
||
|
[131강] 다항 시간
|
1:
02:
16
|
|
|
다항시간 알고리즘과 P복잡도 클래스 핵심 정리• 다항시간 알고리즘·P복잡도 클래스: 입력 이진 인코딩 길이 기준 시간복잡도 O(n^k) 알고리즘, 다항식 닫힘성과 서브루틴 합성을 전제로 한 “현실적 계산 가능” 결정문제 집합 P 정의• 추상적 문제·인코딩·언어: 추상적 문제를 사례–해 이항관계로 보고 이를 이진 문자열로 인코딩한 구체적 문제·언어 L⊆{0,1}*로 표현하며, 결정문제를 yes 인스턴스 이진 문자열 집합(형식 언어)과 1–0 출력 관계로 동치화• 인코딩 불변성·결정 vs 받아들임: 서로 다항식적으로 변환 가능한 인코딩들 사이에서 P 소속 여부가 보존됨을 보조정리로 정립하고, 다항시간에 언어를 받아들이는 알고리즘과 다항시간에 언어를 결정하는 알고리즘이 동일한 클래스 P를 정의함을 증명·정식화
|
||
|
[132강] 다항 시간 확인
|
0:
56:
10
|
|
|
복잡성 이론에서 P와 NP, 해밀토니안 순환 확인 문제 요약• 복잡성 클래스 P와 NP: P는 다항 시간 결정 가능한 언어 집합, NP는 다항 시간 확인(증명서 기반 검증) 가능한 언어 집합으로, 형식 언어·이진 인코딩·확인 알고리즘 A(x,y)를 통해 정의되며 P ⊆ NP 관계를 가짐 • 해밀토니안 순환 문제와 NP: 그래프의 해밀토니안 순환 존재 여부 결정은 지수 시간 복잡도를 가지는 반면, 주어진 정점 순열이 해밀토니안 순환인지 확인하는 과정은 다항 시간에 가능하여 해당 언어가 대표적인 NP 언어로 분류됨 • co-NP와 포함 관계: 언어의 여집합이 NP에 속하는 언어 집합을 co-NP로 정의하며, P는 여집합에 대해 닫혀 P = co-P가 되지만 NP와 co-NP의 관계, 그리고 P vs NP, NP vs co-NP 포함 여부는 모두 미해결 난제로 남아 있음
|
||
|
[133강] NP-완비성과 환원 가능성
|
1:
06:
25
|
|
|
NP 완비성과 다항시간 환원, 회로만족여부(Circuit-SAT)의 NP완비성 개념 정리• 다항시간 환원과 P·NP 관계: 결정문제 간 다항시간 환원 정의($L_1 \leq_p L_2$), 환원 알고리즘 개념, “상위 문제가 P이면 그에 환원되는 모든 문제도 P” 성질을 통한 문제 난이도 비교 구조• NP-complete·NP-hard와 P vs NP: NP-complete(1) NP 속함 (2) 모든 NP 문제로부터의 다항시간 환원 가능, NP-hard는 (2)만 요구하는 정의, 그리고 “임의 NP-complete 문제를 다항시간에 풀 수 있으면 P=NP”가 되는 정리 구조• 회로만족여부(Circuit-SAT)의 NP완비성: 불조합회로·fan-out·입출력·진리할당·만족할당 정의, 회로만족여부의 NP 포함(증명서로 입력 할당을 주고 회로를 선형 시간에 시뮬레이션)과 임의 NP 언어의 다항시간 검증 알고리즘을 회로로 모사하는 환원을 통한 NP-hard 증명으로 Circuit-SAT가 NP-complete임을 확립하는 커리큘럼 구성
|
||
|
[134강] NP-완비성 증명 (1)
|
0:
44:
00
|
|
|
NP 완비 증명 방법과 부울식 만족여부(SAT)의 NP-완비성 개요 • 계산복잡도 클래스 개념: NP(다항시간 확인 가능 언어), NP-hard(모든 NP 언어의 다항시간 환원 대상), NP-complete(“NP ∧ NP-hard”) 정의 및 최적화·결정·확인 문제와 비결정론의 관계 정리 • NP-완비 증명 스키마: 보조정리 34.8을 이용해 (1) 대상 문제 L이 NP에 속함을 보이고, (2) 알려진 NP-완비 문제 L'에서 L로의 다항시간 환원 알고리즘을 구성·분석하며, (3) 환원에 대해 x ∈ L' ⇔ f(x) ∈ L 임을 양방향으로 증명하는 절차 확립 • SAT의 NP-완비성 구조: 부울식·리터럴·진리할당·만족할당 정의 후 SAT가 NP에 속함을 확인 알고리즘으로 보이고, NP-완비인 Circuit-SAT의 회로를 게이트 동치식의 AND로 표현하는 다항시간 환원(Circuit-SAT ≤p SAT)과 그 필요충분 조건 증명을 통해 SAT가 대표 NP-완비 문제임을 정리함
|
||
|
[135강] NP-완비성 증명 (2)
|
0:
40:
05
|
|
|
3CNF 부울식 만족력과 NP-완비성 환원 절차 정리• 3CNF-SAT 구조 정의: 리터럴·절·CNF·DNF·3CNF 형식과 제약(각 절 3개 상이 리터럴, 변수·부정 동시 금지, 모든 변수 등장) 및 3CNF에서의 만족력(satisfiability) 개념 정리 • NP-완비성 증명 구조: 3CNF-SAT ∈ NP인 증명서 검증 절차와 SAT ≤p 3CNF-SAT 환원 구성을 통해 NP-하드성 및 NP-완비성 결론 도출 • 다항식 시간 환원 절차: 일반 SAT 부울식 F를 파스트리 기반 식 ϕ′ → CNF ϕ″ → 3CNF ϕ‴로 변환하는 규칙(드모르간·진리표 전개·절 길이별 3CNF 치환)과 각 단계의 만족성 보존·문제 크기 상수배 증가 분석
|
||
|
[136강] NP-완비성 문제들 (1)
|
1:
03:
15
|
|
|
3CNF에서 클릭·정점덮개까지 NP-완비 환원 구조 요약• NP-완비 그래프 문제 계열: 클릭·정점덮개를 대표 NP-완비로 두고, NP 포함성(다항시간 검증)과 기존 NP-완비 문제로부터의 다항시간 환원 조건으로 복잡도 계층 구조 정리• 클릭·정점덮개 정의와 결정문제: 클릭은 완전 부분그래프 존재 여부(입력 (G,K)에 대해 크기 K 클릭 존재 판정), 정점 덮개는 모든 간선을 덮는 최소 정점집합 존재 여부(입력 (G,K)에 대해 크기 K 이하 정점 덮개 존재 판정)로 각각의 최적화·결정 문제 구분• 환원 구조와 필요충분 관계: 3CNF-SAT를 절-리터럴→정점, 보수가 아닌 상이한 절 리터럴 쌍→간선 규칙으로 CLIQUE(K)로 다항시간 환원하고, 상보 그래프를 이용해 “G에 크기 K 클릭 존재 ⇔ 𝐺̄에 크기 |V|-K 정점 덮개 존재”를 보임으로써 클릭와 정점 덮개의 NP-완비성과 상보적 환원 구조 확립
|
||
|
[137강] NP-완비성 문제들 (2)
|
1:
04:
05
|
|
|
해밀토니안 순환과 정점덮개, TSP의 NP-완비성 환원 구조 정리• 해밀토니안 순환·TSP NP 포함성: 해밀토니안 순환은 정점 수열(모든 정점 1회 방문·간선 존재·시작점 복귀) 검증으로, TSP는 완전 그래프·비용 함수·상한 K에 대한 순회경로와 총비용 검증으로 다항시간 내 확인 가능함• 정점 덮개 → 해밀토니안 순환 환원: 각 간선을 12정점·14간선의 간선 위젯으로 치환하고, 선택자 정점으로 크기 k 정점 덮개 후보를 부호화하여 위젯 내부 3가지 경로(6간선/12간선)를 통해 “정점덮개 존재 ↔ 해밀토니안 순환 존재”가 되도록 하며, 변환 그래프 크기 |V'|=12|E|+k, |E'|=O(|E|+k|V|)로 다항시간 환원을 구성함• 해밀토니안 순환 → TSP 환원: 일반 그래프를 동일 정점 집합의 완전 그래프로 확장하고, 원래 간선에는 비용 0, 새로 추가된 간선에는 비용 1을 부여하며 상한 K=0으로 설정하여 “해밀토니안 순환 ↔ 비용 0 TSP 순회경로”의 필요충분 대응을 만들고, 이를 통해 TSP의 NP-완비성을 증명함
|
||
|
[138강] NP-완비 문제들 (3). NP-하드 최적화 문제 확장
|
1:
00:
31
|
|
|
Summary Content:부분집합 합 문제와 3CNF 환원을 통한 NP 완비 증명 핵심 정리• 부분집합 합(Subset Sum)과 NP 포함성: 집합 S와 목표값 T에 대해 합이 T인 부분집합 존재 여부를 묻는 결정 문제로, 부분집합 S'를 증명서로 하는 다항시간 합·검사 절차를 통해 NP에 속함을 정리• 3CNF-SAT → Subset Sum 다항시간 환원: 3CNF 식의 변수·절을 N+K 자릿수 숫자(Bi, Bi', Sj, Sj')로 부호화하고, 변수 자릿수는 1, 절 자릿수는 4가 되도록 목표값 T를 설정해 “식이 만족 가능 ⇔ 합이 T인 부분집합 존재”가 되도록 하는 자릿수·슬랙 구성 구조 제시• NP 완비성 및 TSP NP-hard성: Subset Sum이 (i) NP에 속하고 (ii) 3CNF-SAT에서의 자릿수 기반 다항시간 환원을 통해 NP-hard임을 보여 NP 완비가 됨을 정리하고, NP-complete인 TSP 결정문제로부터 최소 비용 경로를 구하는 최적화 TSP로의 환원으로 최적화 TSP가 NP-hard임을 설명
|
||
|
[139강] 정점 덮개 문제
|
0:
31:
15
|
|
|
NP-완비 최적화 문제와 근사 알고리즘: Vertex Cover 중심 정리• NP-완비 최적화 문제와 근사 알고리즘: 최적해 구득이 어려운 NP-hard 최적화 문제에 대해 다항시간에 허용 오차 내 해를 구하는 근사 알고리즘 개념과 성능 평가 지표(근사비·로웬 근사비) 정의• 근사전략·PTAS·FPTAS: 임의의 ε > 0에 대해 (1+ε)-근사를 보장하는 근사전략과 입력 크기에 대해 다항시간인 PTAS, 입력 크기와 1/ε 둘 다에 대해 다항시간인 FPTAS의 구조적 차이 정리• 정점 덮개(Vertex Cover) 근사 알고리즘: 임의 간선 선택·양 끝점 포함·인접 간선 제거 반복을 통해 정점 덮개를 구성하고, 선택 간선 집합 A의 성질을 이용해 |C| = 2|A| ≤ 2|C*|을 증명함으로써 근사비 2와 다항시간 복잡도를 보장하는 대표 근사 알고리즘 정리
|
||
|
[140강] 순회 판매원 문제
|
0:
45:
43
|
|
|
순회판매원 문제 근사 알고리즘과 삼각부등식, 일반 TSP 근사불가 정리 • 삼각부등식을 만족하는 TSP와 2-근사 알고리즘: 완전그래프·MST 구성·전위순회·최초 방문 정점만 나열하여 해밀토니안 순환을 만들고, MST 비용 상계와 전위순회 2배 경로, 삼각부등식을 이용해 근사해 비용이 최적해의 2배 이내임을 증명• 일반 TSP 근사불가 정리: 삼각부등식이 없는 TSP에 대해 P≠NP라면 임의의 상수 ρ-근사 다항시간 알고리즘이 존재하지 않음을, 해밀토니안 순환 문제를 완전그래프 TSP로 환원하고 간선 비용을 1과 ρ|V|+1로 설계하는 방식으로 보이는 구조• 논리 기법과 증명 관점: 귀류법과 대우증명법을 사용해 “ρ-근사 알고리즘이 존재하면 NP-완비 문제를 다항시간에 풀어 P=NP”가 됨을 보이고, 이를 통해 “P≠NP이면 일반 TSP에 상수배 근사 알고리즘이 없다”는 근사불가 명제를 정당화하는 논리 구조 정리
|
||
|
[141강] 집합 덮개 문제
|
1:
01:
06
|
|
|
집합 덮개(Set Cover) 문제와 그리디 근사 알고리즘 요약• 집합 덮개 문제 정의: 유한 집합 X와 부분집합 계 P에서 X를 모두 덮는 부분집합들의 모임 C ⊆ P 중 |C|가 최소가 되는 C를 찾는 NP-난이도 최소화 문제 구조 정리• 그리디 집합 덮개 알고리즘: 남은 미덮개 집합 U를 유지하며 각 단계에서 |S ∩ U|가 최대인 S ∈ P를 선택·갱신하는 다항시간 알고리즘과 비용 분배 c(x), Harmonic number Hn, 최대 부분집합 크기 ρ(A)를 이용한 Hρ(A)-근사비 증명• 근사 성능 보장: 모든 인스턴스에 대해 |C| ≤ Hρ(A)·|C*|, ρ(A) ≤ |X| 및 Hn ≤ ln n + 1을 사용한 |C| ≤ (ln|X|+1)·|C*| 도출과 그리디 집합 덮개의 (ln|X|+1)-근사 알고리즘 성질 정리
|
||
|
[142강] 랜덤화와 선형 계획법
|
0:
31:
38
|
|
|
맥스 3CNF 랜덤 근사와 선형계획법 기반 정점덮개 근사 알고리즘 요약• Max-3CNF 랜덤 근사 알고리즘: 각 변수를 0/1로 독립·균등 랜덤 할당하여 각 절이 7/8 확률로 만족됨을 이용해 기대값 기준 목표값의 최소 7/8을 보장하는 7/8-근사 랜덤 알고리즘 설계• 최소가중치 정점덮개 정식화와 LP 완화: 가중 정점덮개를 0-1 정수계획(목적함수 ∑w_v x_v 최소화, 간선별 x_u + x_v ≥ 1, x_v∈{0,1})으로 표현하고, 이를 0 ≤ x_v ≤ 1 제약의 선형계획으로 완화해 최적값을 원 문제 최적값의 하한으로 활용• LP 라운딩 기반 2-근사 알고리즘: LP 최적해 x*에서 x*_v ≥ 1/2 인 정점만 선택해 정점덮개를 구성하고, 모든 간선 제약 x*_u + x*_v ≥ 1을 이용해 타당성을 보이며, w(C) ≤ 2 z_LP ≤ 2 C*를 통해 근사비 2의 다항시간 근사 알고리즘임을 증명
|
||
|
[143강] 부분 집합의 합 문제
|
1:
07:
04
|
|
|
부분집합 합 문제와 완전다항시간 근사전략 핵심 정리• 부분집합 합(Subset Sum) 최적화 문제: 양의 정수 집합과 목표값에 대해 가능한 부분합 리스트(P_i)를 모두 생성하는 지수시간 정확 알고리즘 구조·복잡도(Θ(2^n))와 리스트 병합 메커니즘 정리• 완전다항시간 근사전략(FPTAS) 설계: 트리밍 연산으로 근접한 부분합을 대표값으로 압축하여 리스트 길이를 O((n/ε)·log T)로 제한하고, poly(n,1/ε) 시간에 동작하는 근사 알고리즘 구성• 근사비 1+ε 보장 원리: 각 단계 트리밍 오차를 (1+δ)로 누적해 (1+δ)^n ≤ 1+ε를 만족하도록 δ=ε/(2n)을 선택하고, 최적해와 근사해 비율 Y*/G* ≤ 1+ε임을 증명하는 구조와 시간복잡도 분석 정리
|
||
|
[144강] 상태공간 트리. 백트래킹
|
0:
29:
01
|
|
|
상태공간 틀과 백트래킹 탐색, TSP·색칠 문제 개요• 상태공간 틀과 조합 최적화: TSP 등에서 가능한 모든 중간 상태를 트리 노드로 표현하고, 노드 수가 계승적으로 증가하는 조합 폭발을 보이는 상태공간 구조 이해• 백트래킹과 DFS 탐색: 미로 찾기 등에서 DFS 기반으로 부분 해를 확장하다가 막다른 상태·부적합 상태에서 상위 분기점으로 되돌아가 다른 선택을 시도하는 가지치기 탐색 절차 이해• 그래프 컬러링과 K-Coloring 알고리즘: 면 분할을 그래프로 모델링하고, Valid 검사로 인접 정점 색 충돌을 확인하며 재귀적 백트래킹으로 K가지 색을 사용하는 유효한 색칠 해를 탐색하는 알고리즘 구조 학습
|
||
|
[145강] 한정분기. 알고리즘
|
0:
54:
06
|
|
|
한정분기와 A* 알고리즘을 이용한 TSP 및 최단경로 탐색 요약• 상태공간 기반 탐색 기초 개념: 백트래킹·한정분기·A*의 공통 구조와 차이, 상태공간 트리와 부분 경로 평가 함수 개념 정리• 한정분기와 TSP 최적화: 하한(각 정점 최소 진출 간선 합) 기반 가지치기 구조, 기준해(incumbent)를 활용한 분기 제거, 비대칭 TSP 탐색 과정과 복잡도 축소 원리• A* 알고리즘과 경로 탐색: g(x)·h(x)·f(x) 정의와 h(x) 하한 조건, 다익스트라와의 관계, 우선순위 큐/힙 기반 구현, 최단경로 및 TSP에서의 적용과 최초 리프 종료의 최적성 타당성
|
||
신흥철 교수님
알고리즘 통합과정
