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