홈 > 강의소개
알고리즘Ⅲ
신흥철 교수
KAIST 대학원 전산학부 석사과정
KAIST 대학원 전산학부 박사졸업
KAIST 대학원 전산학부 석사과정
KAIST 대학원 전산학부 박사졸업
숙명여자대학교
Microsoft
현) 유니와이즈 전임교수
AI가 이끄는 스마트한 학습 경험, AI 튜터와 함께 더 빠르고, 더 깊게 학습하세요.
긴 강의 내용을 AI가 핵심만 요약하여 복습 시간을 단축시킵니다.
강의에서 가장 중요한 키워드와 개념을 자동으로 추출해 제공합니다.
학습한 내용을 바탕으로 AI가 생성한 퀴즈를 풀며 이해도를 점검합니다.
모르는 부분을 24시간 언제든 AI 튜터에게 질문하고 답변을 받습니다.
총 1개 챕터, 57강으로 구성되어 있습니다.
| 제목 | 강의시간 | 상세내용 |
|---|---|---|
| 7장. 알고리즘 분야의 중요한 토픽 | ||
|
[1강] 동적 멀티스레딩의 기본 (1)
|
0:
37:
35
|
|
|
멀티코어 병렬 컴퓨팅과 동적 멀티스레딩 기초 개념 정리
• 병렬 컴퓨터 기본 개념: 프로세스·프로세서·스레드의 정의와 차이, 공유 메모리·분산 메모리 모델 구조와 결정성·비결정성 및 동기화·통신 비용 이슈 정리 • 동적 멀티스레딩 모델: 정적 스레딩 vs 동적 스레딩 비교, 운영체제·동시성 플랫폼·병렬 컴파일러에 의한 스레드 스케줄링·부하분산·중첩 병렬성·병렬 루프 관리 원리 • 동시성 키워드와 Fibonacci 예제: parallel·spawn·sync 키워드로 직렬 코드를 병렬화하는 구조, 재귀 Fibonacci 알고리즘의 재귀트리·중복 계산·시간복잡도 T(n)=Θ(Fₙ)=Θ(φⁿ) 분석 및 동적 프로그래밍·반복법 비교 |
||
|
[2강] 동적 멀티스레딩의 기본 (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와 완전 선형 속도 향상 조건 정리, 병렬 완화성으로 프로세서 수 대비 활용 가능 병렬도 판단 |
||
|
[3강] 동적 멀티스레딩의 기본 (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) 도출과 높은 병렬성이 만드는 선형 속도 향상 가능성 분석 |
||
|
[4강] 동적 멀티스레딩의 기본 (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∞) 트레이드오프, 목표 프로세서 수에 따른 병렬 알고리즘 구조 및 동기화 전략 설계 원칙 정리 |
||
|
[5강] 멀티스레드 행렬의 곱셈
|
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)$ 비교 분석 |
||
|
[6강] 멀티스레드 병합 정렬
|
0:
54:
01
|
|
|
멀티스레드 병합정렬과 병렬 병합 알고리즘 분석 요약
• 알고리즘 분석·복잡도 개념: 멀티스레드 병합정렬의 정확성·수행시간을 점근적 표기(Big-Oh/Theta), 마스터 정리, 대입법으로 해석하고 작업(Work)·범위(Span)·병렬성 관계 정의 • 멀티스레드 병합·머지 구조: 중앙 원소 선택·이분 탐색을 이용한 분할정복 병합으로 두 정렬 배열을 병렬 병합하고, 머지 작업 Θ(n)·범위 Θ(log²n)·병렬성 Θ(n/log²n) 확보 • 완전 멀티스레드 병합정렬 성능 분석: 전체 정렬 작업 Θ(n log n), 범위 Θ(log³n), 병렬성 Θ(n/log²n)을 도출하고, 임계 크기(threshold) 설정·스레드 오버헤드 고려한 실무용 하이브리드 구현 전략 정리 |
||
|
[7강] 선형 연립방정식의 해 (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$를 이용한 선형시스템 해법 알고리즘 개요 정리 |
||
|
[8강] 선형 연립방정식의 해 (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$ 절차로 해를 구하는 구조 |
||
|
[9강] 역행렬
|
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 분할 기반 선형계 해법의 이론·실무 효율 비교 |
||
|
[10강] 양으로 정의된 대칭 행렬과 최소-제곱 근사 (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 분해 알고리즘의 정당성을 보장함 |
||
|
[11강] 양으로 정의된 대칭 행렬과 최소-제곱 근사 (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 구성 |
||
|
[12강] 선형 계획법
|
0:
35:
20
|
|
|
선형계획법과 정치 캠페인 예제의 수학적 모형화 핵심 정리
• 선형계획 모형 구조: 선형 목적함수·선형제약조건·의미 아닌 제약조건으로 의사결정 문제를 수학적으로 표현하고 가능영역·최적해·목표값 개념으로 해를 정의하는 방법론 • 기하학적·알고리즘적 해석: 2차원에서는 제약의 교집합인 볼록 다각형 가능영역과 목적함수 직선의 교점을 통해 정점에서 최적해를 찾고, 고차원에서는 볼록 다면체 정점들을 심플렉스 방법으로 탐색하여 최적해를 도출하는 절차 • 응용 및 모형화 사례: 정치 캠페인 득표·비용 최소화, 승무원 편성, 자원 배분·채굴 등에서 변수 정의, 목적함수 설정, 집단·자원 제약식을 선형식으로 구성해 전략·정책 결정을 지원하는 응용 구조 |
||
|
[13강] 정규형과 이완형
|
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)의 구조와 피벗 연산을 통한 최적해 탐색 기반 정리 |
||
|
[14강] 문제의 선형 계획법 구성
|
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)와 상품별 플로우 보존·요구량 제약을 통해 여러 상품이 간선을 공유하는 네트워크에서 실현가능성·비용최적 배치 모델링 |
||
|
[15강] 심플렉스 알고리즘 (1)
|
0:
57:
56
|
|
|
심플렉스 알고리즘 예제와 피벗 연산 원리 요약(최적해 도달 과정 중심)
• 정규형 선형계획과 이완형·기본해: 정규형을 이완형으로 변환하고 이완변수를 기본변수로 두어 초기 기본해를 구성, 목적함수를 기본/비기본 변수 분해 표현 • 진입·진출변수 선택과 피벗 절차: 목적함수에서 양의 계수 기본아닌변수를 진입변수로 선택, 최소비율 규칙으로 진출변수 결정 후 피벗으로 기본/비기본 집합 교환 및 계수·우변·목적값 갱신 • 피벗 일반식·최적성·보조정리 29.2: 피벗 후 새로운 A,B,c 갱신식과 기본해 계산식 정식화, 모든 기본아닌변수 0·갱신된 기본변수 값의 타당성 증명, 목적함수 계수 비양수이면 최적해 및 이완변수의 slack 의미 확립 |
||
|
[16강] 심플렉스 알고리즘 (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 조건과 기본해 가능성을 귀납적으로 보존하는 루프 불변성을 설정해, 종료 시 알고리즘이 최적해 또는 언바운디드 판정을 올바르게 반환함을 보이는 타당성 검증 구조 |
||
|
[17강] 심플렉스 알고리즘 (3)
|
0:
31:
43
|
|
|
심플렉스 알고리즘 종료 조건과 순환 방지 요약
• 심플렉스 알고리즘 종료성 구조: 목적함수 증분식·피벗 연산·목표값 비감소 조건을 통해 유한 반복 내 종료 여부와 사이클링 발생 메커니즘 정리 • 이완형 유일성과 개수: 선형식 계수 유일성 보조정리로 기본변수 집합당 이완형의 유일성을 증명하고, 가능한 이완형 개수를 조합식 𝑪(n+m, m) 으로 한정하여 순환 발생 조건을 규명 • 피벗 선택 규칙과 종료 형태: b_ℓ=0 피벗 회피 및 최소 인덱스 규칙으로 순환을 방지하고, 심플렉스 알고리즘이 최대 𝑪(n+m, m) 회 반복 이내에 언바운디드 판정 또는 유한 최적해 반환 두 형태 중 하나로 종료함을 정리 |
||
|
[18강] 쌍대성
|
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 = 정규형 최적값 일치로 쌍대 최적해 판정 과정 |
||
|
[19강] 초기 가능한 기본 해
|
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 또는 유한 최적해를 도출함 |
||
|
[20강] 다항식의 표현
|
0:
57:
24
|
|
|
다항식 곱셈과 고속 푸리에 변환 개요 정리
• 다항식과 표현 방식: 차수·차수한계, 컨볼루션 구조의 다항식 곱셈(Θ(n²)), 계수표현·점값표현 및 점계산·보간과 유일성 정리(반더몬드 행렬) 정리 • 계수↔점값 변환 복잡도: Horner 방법에 의한 점계산 Θ(n²), 일반 보간 Θ(n³) 한계와 이를 극복하기 위한 복소수 단위근 선택·DFT 관점의 계수↔점값 변환 구조 제시 • FFT 기반 고속 곱셈: 2n차 복소수 단위근을 이용한 DFT/역 DFT 계산(각 Θ(n log n)), 점값 영역 성분별 곱셈(Θ(n))으로 전체 다항식 곱셈 복잡도를 Θ(n log n)으로 감소시키는 정리 30.2의 절차적 틀 정리 |
||
|
[21강] 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)에 수행하는 기반 제시 |
||
|
[22강] 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)$으로 개선하는 알고리즘 구조 정리 |
||
|
[23강] 효율적인 FFT의 구현
|
0:
30:
22
|
|
|
FFT 반복 알고리즘과 비트 역순, 병렬화 개념 정리
• 반복형 FFT 구조: 재귀 FFT를 반복 루프 기반 구조로 변환하여 스택 오버헤드 제거, 나비 연산을 기본 단위로 사용하는 단계별 DFT 구성 • 비트 역순 재배열과 인덱싱: 인덱스를 이진수로 표현 후 비트 역순으로 재배열하여 iterative FFT의 메모리 상 데이터 순서 정렬 및 단계별 블록(2^s) 인덱스 체계 확립 • 시간·병렬 복잡도 분석: 비트 역순 재배열과 단계별 나비 연산을 합쳐 Θ(n log n) 시간 복잡도 도출, 병렬화 시 Work = Θ(n log n), Span = Θ(log n)으로 높은 병렬 효율 확보 |
||
|
[24강] 기초 정수론
|
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 등 암호 이론의 기반 개념 정리 |
||
|
[25강] 최대공약수
|
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⌋을 도입하고, 베이스 케이스와 역추적 절차로 베주 계수 산출 과정을 정리함 |
||
|
[26강] 모듈로 연산 (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$ 계산 원리 정리 |
||
|
[27강] 모듈로 연산 (2)
|
1:
02:
15
|
|
|
유한군에서의 서브군, 라그랑주 정리, 원소의 차수 개념 정리
• 서브군과 판정 조건: 군의 부분집합이 닫힘·항등원 포함·역원 존재·결합법칙을 만족할 때 서브군이 되며, 유한군에서는 닫힘과 항등원 포함만으로도 역원 존재가 따라옴 • 라그랑주 정리와 진 서브군: 유한군의 임의의 서브군 크기는 군 크기의 약수이고, 진 서브군의 크기는 군 크기의 1/2 이하이며, 각 서브군은 코셋 분할을 통해 군 전체를 분해함 • 생성 서브군·원소의 차수·주기성: 한 원소가 만드는 생성 서브군의 원소 개수가 그 원소의 차수와 같고, 해당 수열은 차수 길이의 주기를 가지며, 이로부터 ord(A) | |S| 및 A^{|S|}=e (또는 |S|·A가 항등원) 성질과 지수의 모듈러 동치 관계가 도출됨 |
||
|
[28강] 모듈로 선형 방정식의 해
|
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)의 존재·계산 방법 정리 |
||
|
[29강] 중국인의 나머지 정리
|
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) 복원 알고리즘 정리 • 연산 보존·응용: 덧셈·곱셈의 좌표별 보존으로 큰 모듈러 연산을 작은 모듈러 연산으로 분할·병렬화하고, 수론·암호·알고리즘 설계에서 효율적 계산 구조 제공 |
||
|
[30강] 원소의 거듭제곱
|
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) 알고리즘 구조·시간복잡도·루프 불변식 이해 |
||
|
[31강] 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) 정확성 증명과, 큰 정수 소인수분해 계산 복잡도 및 비밀키 관리·키 길이·구현 이슈에 기반한 안전성·한계 정리 |
||
|
[32강] 스트링 매칭 문제. 단순 스트링 매칭 알고리즘
|
0:
38:
36
|
|
|
문자열 패턴 매칭 기본 개념과 단순 스트링 매칭 알고리즘 정리
• 스트링 매칭 문제와 형식적 모델: 텍스트 T, 패턴 P, 알파벳 집합 Σ, 문자열 집합 Σ*, 문자열 길이 |x|, Shift S 개념을 이용해 패턴의 모든 발생 위치를 찾는 문제 구조 정의 • 문자열 구조와 이론 요소: 접두부·접미부, 부분 문자열 P_k, 중복 접미부 보조정리, 문자열 비교 연산 모델을 통해 KMP 등 선형 시간 알고리즘의 전처리·부분 일치 길이 계산 이론 기반 정리 • 스트링 매칭 알고리즘 분류와 복잡도: 단순 스트링 매칭의 전처리 부재·모든 Shift 직접 비교·최악 시간복잡도 Θ(NM) 특징과 Rabin-Karp, Finite Automata, KMP, Boyer-Moore 등 전처리·이력 정보 활용 기반 선형 시간 급 알고리즘 개관 |
||
|
[33강] 라빈-카프 알고리즘
|
0:
41:
58
|
|
|
라빈 카프 문자열 매칭 알고리즘과 Horner 법칙, 모듈러 연산 핵심 정리
• 라빈 카프 알고리즘 핵심 개념: 문자열을 D진수 정수(또는 모듈러 값)로 표현하고 Horner 법칙과 슬라이딩 윈도우로 각 위치 해시를 상수 시간에 갱신하여 패턴 매칭을 수행하는 알고리즘 구조 • 모듈러 연산과 가짜 적중: 큰 정수 폭발을 방지하기 위해 소수 Q에 대한 모듈러 연산을 사용하고, 해시 값이 같을 때만 실제 문자열 비교로 가짜 적중(false hit)과 유효 매칭을 판별하는 검증 절차 • 수행시간 및 한계: 전처리 Θ(m), 평균적 매칭 O(n), 최악 O(nm) 복잡도를 가지며, 문자 집합 크기에 따라 D와 Q 선택이 성능에 큰 영향을 주어 ASCII/알파누메릭에는 유리하지만 대규모 유니코드 환경에서는 비효율적이라는 적용 한계가 존재함 |
||
|
[34강] 유한 오토마타를 이용한 스트링 매칭 (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 도달 여부로 패턴 매칭을 판정하는 알고리즘 구조 설명 |
||
|
[35강] 유한 오토마타를 이용한 스트링 매칭 (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 알고리즘의 실패 함수 개념으로 연결하는 내용 |
||
|
[36강] 크누스-모리스-프랫(KMP) 알고리즘
|
0:
58:
05
|
|
|
KMP 알고리즘과 접두부 함수 개념 정리
• KMP 알고리즘과 유한 오토마타 패턴 매칭: 전이함수 대신 패턴 기반 접두부 함수(π 함수)를 사용해 전처리 비용과 메모리를 줄이면서도 매칭 단계는 선형 시간으로 수행하는 문자열 패턴 매칭 알고리즘 구조 정리 • 접두부 함수(π 함수): 부분 문자열 P[1..i]의 접미부이면서 동시에 전체 패턴 P의 접두부인 부분 문자열 중 가장 긴 길이를 저장해 불일치 시 최소 shift를 결정하고 패턴 재비교를 줄이는 핵심 테이블 정의·의미·선형 시간 계산 절차 정리 • KMP 전처리·매칭 알고리즘과 복잡도: π 테이블 O(m) 전처리와 이를 활용한 텍스트 매칭 O(n) 절차, q 갱신 규칙과 shift 원리, 그리고 유한 오토마타 방식과의 전처리 시간·공간 복잡도 비교를 통한 전체 성능 O(m+n), 메모리 O(m) 구조 정리 |
||
|
[37강] 보이어-무어 알고리즘
|
0:
41:
42
|
|
|
보이어-무어 알고리즘과 휴리스틱 패턴 매칭 정리
• 보이어-무어 알고리즘 구조: 패턴의 끝에서 시작하는 역방향 비교와 문자 집합 기반 점프 테이블을 이용해 평균 비교 횟수를 줄이는 문자열 패턴 매칭 기법 • 점프 테이블 및 수행시간: 각 문자에 대해 패턴 끝으로부터의 최소 거리를 저장한 점프 테이블로 쉬프트 길이를 결정하며, 최악 시간 복잡도는 O(MN), 평균적으로는 선형 이하에 가까운 효율 달성 • 휴리스틱 패턴 매칭: 불일치 문자 휴리스틱(bad-character)과 일치 접미부 휴리스틱(good-suffix)을 결합해 두 쉬프트 값 중 더 큰 값을 선택함으로써 실질적 점프 폭을 최대화하고 영어 등 소규모 문자 집합에서 특히 높은 성능 확보 |
||
|
[38강] 선분의 특징
|
0:
52:
47
|
|
|
컴퓨테이셔널 지오메트리: 선분, 벡터곱, 방향 판단과 교차 판정 요약
• 2D 벡터·선분 기초 개념: 선분의 볼록 조합 표현, 방향선분 정의, 2D 벡터곱/행렬식으로 면적과 시계·반시계·공선 판정 구조 이해 • 방향·회전 판정 원리: 기준점 이동 후 벡터곱 부호로 기준 선분 대비 방향, 세 점의 좌·우회전(직진 포함) 판정 및 Convex Hull 등 알고리즘의 기본 연산 정리 • 선분 교차 알고리즘: Direction·OnSegment 함수와 벡터곱 부호·좌표 범위 조건을 이용한 일반 교차·경계 교차(끝점 포함) SegmentIntersection 절차 통합 정리 |
||
|
[39강] 선분의 교차성 결정
|
0:
58:
51
|
|
|
선분 교차성 결정 알고리즘과 스위핑 구조 요약
• 선분 교차성 판정 문제와 스위핑 구조: 수직선분·다중 교차 배제 전제에서 검사선·사건점·검사선 상태 개념을 사용해 선분 교차 여부를 효율적으로 판정하는 문제 구조와 정의 • 검사선 상태 자료구조와 인접 선분 관리: 사건점에서 검사선을 지나는 선분들을 y-좌표 기준 전체 순서로 유지하고, 레드블랙트리(삽입·삭제·Above·Below 연산 O(log n))로 인접 선분 쌍만 비교하여 교차 후보를 관리하는 절차 • Any Segment Intersect 알고리즘과 성능·정당성: 끝점 정렬 규칙(동일 x에서 왼쪽 끝점·작은 y 우선), 시작·끝 사건 처리 시 인접 쌍 교차 검사, 가장 왼쪽·아래 교차점을 이용한 코렉트니스 증명과 전체 시간 복잡도 O(n log n) 분석 |
||
|
[40강] 볼록 껍질의 발견
|
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과의 성능 비교 |
||
|
[41강] 가장 가까운 점들의 쌍 구하기
|
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) 결합 보장 |
||
|
[42강] 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성을 증명함 |
||
|
[43강] 다항 시간
|
1:
02:
16
|
|
|
다항시간 알고리즘과 P복잡도 클래스 핵심 정리
• 다항시간 알고리즘·P복잡도 클래스: 입력 이진 인코딩 길이 기준 시간복잡도 O(n^k) 알고리즘, 다항식 닫힘성과 서브루틴 합성을 전제로 한 “현실적 계산 가능” 결정문제 집합 P 정의 • 추상적 문제·인코딩·언어: 추상적 문제를 사례–해 이항관계로 보고 이를 이진 문자열로 인코딩한 구체적 문제·언어 L⊆{0,1}*로 표현하며, 결정문제를 yes 인스턴스 이진 문자열 집합(형식 언어)과 1–0 출력 관계로 동치화 • 인코딩 불변성·결정 vs 받아들임: 서로 다항식적으로 변환 가능한 인코딩들 사이에서 P 소속 여부가 보존됨을 보조정리로 정립하고, 다항시간에 언어를 받아들이는 알고리즘과 다항시간에 언어를 결정하는 알고리즘이 동일한 클래스 P를 정의함을 증명·정식화 |
||
|
[44강] 다항 시간 확인
|
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 포함 여부는 모두 미해결 난제로 남아 있음 |
||
|
[45강] 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임을 확립하는 커리큘럼 구성 |
||
|
[46강] 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-완비 문제임을 정리함 |
||
|
[47강] 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 치환)과 각 단계의 만족성 보존·문제 크기 상수배 증가 분석 |
||
|
[48강] 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-완비성과 상보적 환원 구조 확립 |
||
|
[49강] 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-완비성을 증명함 |
||
|
[50강] 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임을 설명 |
||
|
[51강] 정점 덮개 문제
|
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와 다항시간 복잡도를 보장하는 대표 근사 알고리즘 정리 |
||
|
[52강] 순회 판매원 문제
|
0:
45:
43
|
|
|
순회판매원 문제 근사 알고리즘과 삼각부등식, 일반 TSP 근사불가 정리
• 삼각부등식을 만족하는 TSP와 2-근사 알고리즘: 완전그래프·MST 구성·전위순회·최초 방문 정점만 나열하여 해밀토니안 순환을 만들고, MST 비용 상계와 전위순회 2배 경로, 삼각부등식을 이용해 근사해 비용이 최적해의 2배 이내임을 증명 • 일반 TSP 근사불가 정리: 삼각부등식이 없는 TSP에 대해 P≠NP라면 임의의 상수 ρ-근사 다항시간 알고리즘이 존재하지 않음을, 해밀토니안 순환 문제를 완전그래프 TSP로 환원하고 간선 비용을 1과 ρ|V|+1로 설계하는 방식으로 보이는 구조 • 논리 기법과 증명 관점: 귀류법과 대우증명법을 사용해 “ρ-근사 알고리즘이 존재하면 NP-완비 문제를 다항시간에 풀어 P=NP”가 됨을 보이고, 이를 통해 “P≠NP이면 일반 TSP에 상수배 근사 알고리즘이 없다”는 근사불가 명제를 정당화하는 논리 구조 정리 |
||
|
[53강] 집합 덮개 문제
|
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)-근사 알고리즘 성질 정리 |
||
|
[54강] 랜덤화와 선형 계획법
|
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의 다항시간 근사 알고리즘임을 증명 |
||
|
[55강] 부분 집합의 합 문제
|
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+ε임을 증명하는 구조와 시간복잡도 분석 정리 |
||
|
[56강] 상태공간 트리. 백트래킹
|
0:
29:
01
|
|
|
상태공간 틀과 백트래킹 탐색, TSP·색칠 문제 개요
• 상태공간 틀과 조합 최적화: TSP 등에서 가능한 모든 중간 상태를 트리 노드로 표현하고, 노드 수가 계승적으로 증가하는 조합 폭발을 보이는 상태공간 구조 이해 • 백트래킹과 DFS 탐색: 미로 찾기 등에서 DFS 기반으로 부분 해를 확장하다가 막다른 상태·부적합 상태에서 상위 분기점으로 되돌아가 다른 선택을 시도하는 가지치기 탐색 절차 이해 • 그래프 컬러링과 K-Coloring 알고리즘: 면 분할을 그래프로 모델링하고, Valid 검사로 인접 정점 색 충돌을 확인하며 재귀적 백트래킹으로 K가지 색을 사용하는 유효한 색칠 해를 탐색하는 알고리즘 구조 학습 |
||
|
[57강] 한정분기. 알고리즘
|
0:
54:
06
|
|
|
한정분기와 A* 알고리즘을 이용한 TSP 및 최단경로 탐색 요약
• 상태공간 기반 탐색 기초 개념: 백트래킹·한정분기·A*의 공통 구조와 차이, 상태공간 트리와 부분 경로 평가 함수 개념 정리 • 한정분기와 TSP 최적화: 하한(각 정점 최소 진출 간선 합) 기반 가지치기 구조, 기준해(incumbent)를 활용한 분기 제거, 비대칭 TSP 탐색 과정과 복잡도 축소 원리 • A* 알고리즘과 경로 탐색: g(x)·h(x)·f(x) 정의와 h(x) 하한 조건, 다익스트라와의 관계, 우선순위 큐/힙 기반 구현, 최단경로 및 TSP에서의 적용과 최초 리프 종료의 최적성 타당성 |
||
신흥철 교수님
알고리즘Ⅲ
