분할 정복·정렬·마스터 정리

점화식과 마스터 정리 (Recurrences and Master theorem)

1타 강사식 학습 동선

직관 → 조작 → 예시 → 함정 → 답안

Recurrence(Rekurrenz)는 recursive algorithm의 실행 시간 T(n)을 더 작은 입력의 실행 시간으로 다시 쓰는 식입니다. Master theorem(Mastertheorem)은 \(T(n)=a\,T(n/b)+f(n)\)T(n)=aT(n/b)+f(n)꼴에서 recursion tree의 leaf 쪽 기준 \(n^{\log_{b} a}\)n^(log_b a)와...

\(T(n)=a\,T(n/b)+f(n)\)T(n)=aT(n/b)+f(n)\(a = \text{recursive} \text{subproblem} \text{count}\)a = recursive subproblem count\(b = \text{shrink} \text{factor}, b > 1\)b = shrink factor, b > 1\(f(n) = \text{non}-\text{recursive} \text{split}/\text{combine} \text{work}\)f(n) = non-recursive split/combine work\(\text{baseline} = n^{\log_{b} a}\)baseline = n^(log_b a)

연습으로 이동 개인화 순서 보기

01 직관이 개념이 왜 필요한지 한 문장으로 잡기

02 손풀이그래프, 트리, 표, 문자열을 직접 움직이며 확인하기

03 단계별 예제시험 답안처럼 조건과 결론을 연결하기

04 함정 점검자주 틀리는 조건과 반례를 먼저 차단하기

점화식(Rekurrenz) · 마스터 정리(Mastertheorem) · 분할 정복(Divide and Conquer)

코드에서 a, b, f(n)을 읽고, 재귀 트리로 펼친 뒤 기준선과 비교합니다

점화식(Recurrence, Rekurrenz)은 큰 입력의 실행 시간(Laufzeit) T(n)을 더 작은 입력의 실행 시간으로 다시 쓰는 식입니다. 마스터 정리(Master theorem, Mastertheorem)는 \(T(n)=a\,T(n/b)+f(n)\)T(n)=aT(n/b)+f(n) 꼴에서 재귀 트리의 잎 기준선 \(n^{\log_{b} a}\)n^(log_b a)과 현재 층에서 직접 하는 일 f(n)을 비교해 점근적 경계를 빠르게 고르는 도구입니다.

\(T(n)=a\,T(n/b)+f(n)\)T(n)=aT(n/b)+f(n) \(a =\)a =재귀 호출 수 \(b =\)b =입력 축소 비율, \(b > 1\)b > 1 \(f(n) =\)f(n) =분할·결합 작업량 기준선 = \(n^{\log_{b} a}\)n^(log_b a)

먼저 알아야 할 개념 지도

분할 정복 (Divide and Conquer)

문제를 나누고(divide), 작은 문제를 재귀로 풀고(conquer), 결과를 합칩니다(combine).

란다우 표기 비교

f(n)이 기준선보다 다항식 차이로 작은지, 같은지, 큰지를 비교해야 합니다.

재귀 트리 (Recursion Tree)

각 층의 노드 수와 부분문제 크기를 이용해 층별 작업량을 계산합니다.

초보자 강의 흐름

점화식은 “코드가 자기 자신에게 일을 몇 번 맡기는지”를 식으로 적은 것입니다

처음부터 마스터 정리의 경우를 외우려 하지 마세요. 먼저 코드를 한 줄씩 읽으며 세 가지 숫자를 찾습니다. 첫째, 재귀 호출이 몇 번 나오는지 세면 a입니다. 둘째, 각 호출이 받는 입력 크기가 원래의 몇 분의 일인지 보면 b입니다. 셋째, 재귀 호출을 제외하고 현재 함수가 직접 하는 분할·파티션·병합·결합 작업이 f(n)입니다.

예를 들어 MergeSort는 배열을 반으로 나누어 왼쪽과 오른쪽을 각각 정렬하고, 마지막에 병합합니다. 호출은 두 번이므로 \(a=2\)a=2, 각 입력은 절반이므로 \(b=2\)b=2, 병합은 전체를 한 번 훑으므로 \(f(n)=\Theta(n)\)f(n)=Θ(n)입니다. 이 세 조각을 합치면 \(T(n)=2T(n/2)+\Theta(n)\)T(n)=2T(n/2)+Θ(n)이 됩니다.

그다음에는 재귀 트리를 생각합니다. 위에서 한 일이 아래 층으로 갈수록 많아지는지, 줄어드는지, 아니면 모든 층이 비슷한지 봅니다. 잎 기준선 \(n^{\log_{b} a}\)n^(log_b a)은 “맨 아래 작은 문제들의 전체 작업량이 얼마나 되는가”를 나타냅니다. f(n)과 기준선이 같으면 모든 층이 비슷해서 \(\log n\)log n개 층의 작업을 더하게 되고, 따라서 MergeSort는 \(\Theta(n \log n)\)Θ(n log n)이 됩니다.

강의 자료에 근거한 개념 지도

근거: \(\text{data}/\text{aud}_{\text{topi}}\,c_{\text{map}}.\text{md}\)data/aud(topic)(map).md는 Übung\AuD26_Sheet03.pdf와 Übung\AuD26_Sheet03-GrpSol.pdf를 “분할 정복, 정렬, 마스터 정리”로 연결합니다. \(\text{data}/\text{aud}_{\text{chunks}}.\text{jsonl}\)data/aud(chunks).jsonl 16번 줄은 MergeSort·QuickSort 의사코드와 MergeSort의 분할·병합 설명을 포함합니다. 17–18번 줄은 Mastertheorem 적용 가능 여부, a, b, f(n), 정규성 조건(regularity condition), 적용 불가 예시를 다룹니다. 주제 지도의 Vorlesung\02Sorting.pdf와 Vorlesung\02Sorting_updated.pdf는 정렬, 점근 분석, 분할 정복 강의 범위입니다.

자료 한계: 추출 텍스트만으로는 모든 재귀 트리 슬라이드의 배치를 완전히 재현할 수 없습니다. 아래 트리는 MergeSort 점화식과 Sheet03의 Mastertheorem 조건을 바탕으로 만든 학습용 도식입니다.

의사코드에서 점화식 만들기

mid = floor((left + right) / 2)
mergeSort(A, left, mid)      // 왼쪽 절반
mergeSort(A, mid + 1, right) // 오른쪽 절반
merge(A, left, mid, right)   // 두 결과 결합

a: 재귀 호출 수

MergeSort는 두 절반을 각각 재귀 호출하므로 \(a=2\)a=2입니다.

b: 입력 축소 비율

각 호출의 입력 크기는 n/2입니다. 표준형 T(n/b)에 맞추면 \(b=2\)b=2입니다.

f(n): 재귀 호출 밖의 일

병합은 정렬된 두 절반을 한 번 훑어 합치므로 \(f(n)=\Theta(n)\)f(n)=Θ(n)입니다.

따라서 MergeSort 실행 시간은 \(T(n)=2T(n/2)+\Theta(n)\)T(n)=2T(n/2)+Θ(n)이고, 기저 조건(base case)은 \(T(1)=\Theta(1)\)T(1)=Θ(1)입니다.

재귀 트리를 그림으로 이해하기

n\(W0 = f(n)\)W0 = f(n)

/ \

n/bn/b\(W1 = a f(n/b)\)W1 = a f(n/b)

/ \ / \

\(n/b^{2}\)n/b²\(n/b^{2}\)n/b²\(n/b^{2}\)n/b²\(n/b^{2}\)n/b²\(W2 = a^{2} f(n/b^{2})\)W2 = a² f(n/b²)

마스터 정리는 이 트리에서 어느 쪽이 지배적인지 묻습니다. 잎 쪽이 지배하면 경우 1, 모든 층의 작업량이 비슷하면 경우 2, 루트의 결합 작업이 지배하면 경우 3입니다.

초보자 관점에서 점화식은 “한 번 호출할 때 일을 몇 조각으로 나누는가”와 “각 조각이 얼마나 작아지는가”를 장부처럼 적는 방식입니다. 먼저 a와 b를 정확히 읽고, f(n)이 재귀 호출 밖에서 직접 처리하는 일인지 확인합니다. 마지막으로 기준선과 비교할 때는 단순히 커 보인다는 느낌이 아니라 다항식 차이(polynomial gap)가 있는지 말로 설명해야 답안이 단단해집니다.

마스터 정리의 세 경우

f(n)을 기준선 \(n^{\log_{b} a}\)`n^(log_b a)`와 다항식 차이로 비교합니다

경우 1: 잎의 작업이 지배함

\[f(n)=O(n^{\log_{b} a - \varepsilon}) \Rightarrow T(n)=\Theta(n^{\log_{b} a})\]f(n)=O(n^(log_b a - epsilon)) => T(n)=Θ(n^(log_b a))

f(n)이 기준선보다 다항식 차이로 작으면 잎 부분문제의 수가 전체를 지배합니다.

경우 2: 모든 층의 작업이 비슷함

\[f(n)=\Theta(n^{\log_{b} a}) \Rightarrow T(n)=\Theta(n^{\log_{b} a} \log n)\]f(n)=Θ(n^(log_b a)) => T(n)=Θ(n^(log_b a) log n)

각 층의 작업량이 비슷해서 깊이 \(\log n\)log n만큼 더해집니다. MergeSort가 대표 예시입니다.

경우 3: 루트의 작업이 지배함

\[f(n)=\Omega(n^{\log_{b} a + \varepsilon})\quad\text{and}\quad a\cdot f(n/b) \le c\cdot f(n), c<1 \Rightarrow T(n)=\Theta(f(n))\]f(n)=Ω(n^(log_b a + epsilon)) and a*f(n/b) ≤ c*f(n), c<1 => T(n)=Θ(f(n))

f(n)이 기준선보다 다항식 차이로 크고 정규성 조건까지 맞으면 루트 쪽 작업이 지배합니다.

단계별 풀이 예제

병합 정렬 (MergeSort)

\(T(n)=2T(n/2)+\Theta(n)\)T(n)=2T(n/2)+Θ(n)이므로 \(a=2\)a=2, \(b=2\)b=2, \(f(n)=\Theta(n)\)f(n)=Θ(n)이다.
기준선은 \(n^{\log_{2} 2}=n\)n^(log₂ 2)=n이다.
\(f(n)=\Theta(n)\)f(n)=Θ(n)이므로 경우 2이다.
결론: \(T(n)=\Theta(n \log n)\)T(n)=Θ(n log n).

수식이 포함된 학습 항목: \(T(n)=2T(n/4)+n^{2}\)`T(n)=2T(n/4)+n²`

\(a=2\)a=2, \(b=4\)b=4, \(f(n)=n^{2}\)f(n)=n².
기준선은 \(n^{\log_{4} 2}=n^{1/2}\)n^(log₄ 2)=n^(1/2)이다.
\(n^{2}\)n²는 기준선보다 다항식 차이로 크다.
정규성: \(2\cdot (n/4)^{2} = n^{2}/8 \le c\cdot n^{2}\)2*(n/4)² = n²/8 ≤ c*n²이고 \(c=1/8\)c=1/8로 둘 수 있다.
경우 3이므로 \(T(n)=\Theta(n^{2})\)T(n)=Θ(n²)이다.

수식이 포함된 학습 항목: \(T(n)=16T(n/2)+n^{3}\)`T(n)=16T(n/2)+n³`

\(a=16\)a=16, \(b=2\)b=2, \(f(n)=n^{3}\)f(n)=n³.
기준선은 \(n^{\log_{2} 16}=n^{4}\)n^(log₂ 16)=n⁴이다.
\(n^{3}\)n³은 \(n^{4}\)n⁴보다 다항식 차이로 작다.
경우 1이므로 \(T(n)=\Theta(n^{4})\)T(n)=Θ(n⁴)이다.

대화형 시각화

마스터 정리 경우 선택기

a, b, \(f(n)=n^{k}\)f(n)=nᵏ를 바꿔 보세요. 이 도구는 k와 잎 기준선의 지수인 \(\log_{b}(a)\)log_b(a)를 비교합니다.

\(a =\)a = 2 \(b =\)b = 2 \(f(n)=n^{k}\)f(n)=nᵏ의 k: 1

f(n)\(n^{1}\)n¹

기준선\(n^{1}.00\)n¹.00

경우경우 2

지수가 같으면 모든 재귀 층이 같은 차수의 작업을 하므로 log n 인수가 추가됩니다.

마스터 정리를 적용할 수 없는 경우

마스터 정리를 바로 쓰지 마세요 \(T(n)=2T(4n/3)+n\)T(n)=2T(4n/3)+n: \(b=3/4\)b=3/4이므로 \(b>1\)b>1조건을 만족하지 않음 \(T(n)=T(n/2)+2T(n/4)+n\)T(n)=T(n/2)+2T(n/4)+n: 부분문제 크기가 서로 다름 \(T(n)=2T(n/2)+n\)T(n)=2T(n/2)+n log n: 기본 세 경우의 다항식 차이 조건에 바로 들어가지 않음 \(T(n)=2\text{nT}(n/2)+n^{n}\)T(n)=2nT(n/2)+nⁿ: a가 상수가 아님

객관식 함정과 바로잡기

b를 거꾸로 읽기

함정: \(T(n)=2T(n/2)+n\)T(n)=2T(n/2)+n에서 \(b=1/2\)b=1/2로 읽는다. 교정: 표준형은 T(n/b)이므로 \(b=2\)b=2입니다.

f(n)을 전체 실행 시간으로 착각

교정: f(n)은 재귀 호출 밖의 분할·파티션·병합·결합 작업입니다.

경우 2의 log 인수 누락

교정: 모든 층의 작업량이 비슷하면 \(\log n\)log n개 층을 더해야 합니다.

경우 3의 정규성 조건 생략

교정: f가 더 크다는 것만으로 부족합니다. \(a\cdot f(n/b) \le c\cdot f(n)\)a*f(n/b) ≤ c*f(n), \(c<1\)c<1도 확인합니다.

QuickSort를 항상 균형 분할로 가정

교정: 균형 분할과 최악의 경우를 구분해야 합니다. 피벗 선택이 나쁘면 점화식이 달라집니다.

표준형 확인 전 경우 선택

교정: 먼저 \(a\ge 1\)a≥1, \(b>1\)b>1, 같은 부분문제 크기, 음이 아닌 f(n), 다항식 차이를 봅니다.

구두 답안과 능동 회상

MergeSort 의사코드에서 a, b, f(n)을 각각 어느 줄에서 읽나요?
재귀 트리의 i번째 층에서 노드 수와 부분문제 크기를 말해 보세요.
왜 깊이가 \(\log_{b} n\)log_b n이고 잎 기준선이 \(n^{\log_{b} a}\)n^(log_b a)인가요?
마스터 정리 경우 1, 2, 3의 조건과 결과를 재귀 트리 직관으로 설명하세요.
경우 3의 정규성 조건은 무엇을 보장하나요?
\(T(n)=2T(n/4)+n^{2}\)T(n)=2T(n/4)+n²를 기준선, 경우, 정규성, 결과 순서로 말하세요.
기본 마스터 정리가 적용되지 않는 점화식 하나와 이유를 말하세요.

추가 학습용 AI 프롬프트

Vorlesung/02Sorting.pdf, Vorlesung/02Sorting_updated.pdf, Übung/AuD26_Sheet03.pdf, Übung/AuD26_Sheet03-GrpSol.pdf를 첨부한다. AUD 시험에 맞춰 점화식과 마스터 정리를 한국어로 가르친다. MergeSort 의사코드에서 시작해 T(n)=2T(n/2)+Theta(n)을 도출하고, 층별 작업량을 그리며 깊이 log_b n과 기준선 n^(log_b a)을 유도한다. 정규성 조건을 포함해 마스터 정리의 세 경우를 설명하고 T(n)=2T(n/4)+n^2, T(n)=16T(n/2)+n^3을 푼다. 마지막에는 적용할 수 없는 경우의 함정을 한 번에 한 문항씩 연습한다.

출처 파일

`Übung\AuD26_Sheet03.pdf`
`Übung\AuD26_Sheet03-GrpSol.pdf`
`Vorlesung\02Sorting.pdf`
`Vorlesung\02Sorting_updated.pdf`
`AuD Gedächtnisprotokoll SoSe 2025.md`

연결 개념 (Related concepts)

후속 튜터 학습 프롬프트

마지막 생성: 2026-08-03 03:24