8. Algorithmen-Entwurfsmethoden — Einkommensstatistik (12 Punkte)
선행지식이 전혀 없어도 이 페이지 하나에서 용어를 배우고, 작은 예제를 거쳐 실제 시험 풀이와 검산까지 따라가도록 구성했습니다.
문제 조건과 만점의 optimality 요구는 비공식 복기 `AuD Gedächtnisprotokoll SoSe 2025.md` lines 321-332에서 왔다. 정렬·binary search runtime은 `Vorlesung\02Sorting.pdf`와 updated 강의판을 근거로 한다. lowerBound/upperBound 변형, \(\text{comparison}-\text{model} \text{range}-\text{query} \text{lower} \text{bound}, N=0\)comparison-model range-query lower bound, N=0정책은 강의 개념에서 이 페이지가 명시적으로 유도한 일반 알고리즘 지식이며 공식 해설을 인용한 것이 아니다.
기호를 모른 채 풀이를 외우지 않도록, 이 문제에서 실제로 쓰는 뜻과 작은 예를 먼저 확인합니다.
| 기호·용어 | 뜻 | 작은 예 |
|---|---|---|
| 항목 (S[0…N−1]) | N개 소득을 저장한 0-based array다. 복기 원문은 \(s_{1}\)s₁…\(s_{N}\)sₙ의 1-based 수학 표기를 쓰지만 pseudocode에서는 첫 칸을 index 0으로 둔다. | \(S=[4200,1800,2500]\)S=[4200,1800,2500]이면 \(S[0]=4200, S[2]=2500\)S[0]=4200, S[2]=2500이다. |
| 항목 ([l,h]) | l 이상 h 이하를 모두 포함하는 closed query interval이며 이 페이지는 \(\text{유효} \text{query} l\le h\)valid query l≤h를 전제로 한다. | [2500,4000]은 2500과 4000도 센다. |
| 원소 [lo,hi) / 답 경계 [lo,hi] | 아직 비교할 원소 index는 lo 포함·hi 제외인 [lo,hi)다. 동시에 정답 boundary는 닫힌 구간 [lo,hi] 안에 보존된다. \(\text{lo}=\text{hi}\)lo=hi이면 비교할 원소는 없고 정답 boundary 하나만 확정된다. | \(\text{lo}=2,\text{hi}=6\)lo=2,hi=6이면 원소 후보는 indices 2,3,4,5이고 답 boundary 후보에는 6도 포함된다. |
| 항목 (L / R) | L은 첫 \(A[i]\ge l\)A[i]≥l위치, R은 첫 \(A[i]>h\)A[i]>h위치다. 해당 원소가 없으면 실제 index가 아닌 sentinel boundary N을 반환한다. | \(A=[1,2,2,5]\)A=[1,2,2,5]에서 \(l=h=2\)l=h=2이면 \(L=1, R=3, \text{count}=2\)L=1, R=3, count=2다. |
\(\Theta(f(N))\)Θ(f(N)) | 입력이 커질 때 실행 단계 수가 위아래 모두 f(N)의 상수배 수준으로 증가한다는 tight asymptotic bound다. | binary search는 후보를 반씩 줄여 \(N\ge 2\)N≥2에서 \(\Theta(\log N)\)Θ(log N)이다. |
| 항목 (log(N+2)) | 2진 logarithm의 밑은 Θ 표기에서 상수 차이라 생략한다. \(\Theta(\log(N+2))\)Θ(log(N+2))는 \(N=0\)N=0에서도 상수 1회의 초기 검사 비용을 포함하며, \(N\ge 2\)N≥2에서는 \(\Theta(\log(N+2))\)Θ(log(N+2))=\(\Theta(\log N)\)Θ(log N)이다. | 후보가 8칸이면 약 3번 절반으로 줄이면 한 boundary가 남는다. |
| 결정적 알고리즘 | 난수나 우연한 선택 없이 같은 입력에는 같은 실행 규칙과 같은 출력을 내는 알고리즘이라는 뜻이다. | 이 페이지의 정렬과 lowerBound는 같은 배열·질의에 언제나 같은 경계를 반환한다. |
| 다항 시간(polynomial-time) | 입력 크기의 어떤 고정된 거듭제곱으로 실행시간 상한을 쓸 수 있다는 뜻이다. 풀 수 있을 만큼 체계적인 해법이라는 넓은 기준이지, 그중 가장 빠르다는 뜻은 아니다. | 질의마다 전부 확인하는 \(\Theta(\text{NQ})\)Θ(NQ)도 polynomial이지만 \(Q>N\)Q>N인 이 문제에서는 optimal하지 않다. |
| 항목 (rank / comparison model) | rank는 정렬 순서에서 한 값보다 작은 원소의 개수, 즉 그 값이 들어갈 boundary 위치다. comparison model은 값에 대해 <,≤,> 같은 비교 결과만으로 결정을 내린다고 가정한다. | 서로 다른 N개 값의 hard instance에서는 prefix 질의의 답 rank가 0부터 N까지 N+1가지가 될 수 있다. |
아래 선수 개념부터 차례대로 읽으면 실제 문제의 요구를 이해할 수 있습니다.
이 문제는 올바른 polynomial algorithm만으로 일부 점수, asymptotically optimal한 algorithm과 helper 비용까지 설명해야 최대 점수를 준다고 명시한다. 따라서 정렬·query·출력 비용을 빠짐없이 더하고, \(Q>N\)Q>N을 이용한 단순화와 comparison-model 하한의 적용 범위를 구분해야 한다.
Θ(N log N), query당 \(\Theta(\log N)\)Θ(log N), Q개 \(\Theta(Q \log N)\)Θ(Q log N)을 합쳐 전체식을 유도할 수 있다.Q>N조건 아래 \(\Theta(N \log N+Q \log N)\)Θ(N log N+Q log N)=\(\Theta(Q \log N)\)Θ(Q log N)으로 올바르게 단순화하면서 유도 과정의 전처리 항을 설명할 수 있다.N=0을 포함한 구현 bound \(\Theta(\log(N+2))\)Θ(log(N+2))와 시험 관례 \(N\ge 2\)N≥2의 \(\Theta(\log N)\)Θ(log N)을 구분할 수 있다.Ω(Q log N) 정보가 필요한지 설명하고 integer-universe 추가 가정의 한계를 표시할 수 있다.O, Ω, ΘO는 asymptotic upper bound, Ω는 lower bound, Θ는 둘이 일치하는 tight bound다. 알고리즘이 빠르다는 상한과 어떤 알고리즘도 피할 수 없다는 하한을 구분해야 optimality를 말할 수 있다.
O(log N)이면서 \(\Omega(\log N)\)Ω(log N) worst-case comparisons가 필요해 \(\Theta(\log N)\)Θ(log N)이다.소득과 query endpoint의 순서 정보가 <,≤,> 같은 비교 결과를 통해서만 얻어진다고 보는 계산 모델이다. 정수의 bit 구조나 작은 universe를 공짜로 이용하지 않는다.
같은 model에서 알고리즘 upper bound와 문제 lower bound가 상수배까지 일치하는 상태다. 단지 다른 알려진 방법보다 빨라 보인다는 뜻이 아니다.
Q>N에서 algorithm \(\Theta(Q \log N)\)Θ(Q log N)과 comparison lower bound \(\Omega(Q \log N)\)Ω(Q log N)이 맞아 optimal하다.도서관 영수증에는 개관 전 전체 정리 비용 한 줄과 방문자 Q명에게 선반 두 곳을 안내한 비용 Q줄이 따로 있다. 총액을 먼저 모두 더한 뒤 방문자가 책보다 많다는 \(Q>N\)Q>N조건으로 어느 항이 지배적인지 단순화한다.
Θ(N log N)Θ(log N)Θ(Q log N)Ω(Q log N)비유의 한계: 영수증 비유는 단순 합산을 보여 줄 뿐 lower bound를 증명하지 않는다. optimality에는 어떤 comparison algorithm도 출력 조합을 구분해야 한다는 별도 정보 논증이 필요하다.
Θ(N)+Θ(N log N)=Θ(N log N)2·Θ(log N)+Θ(1)=Θ(log N)Q·Θ(log N)=Θ(Q log N)Θ(N log N+Q log N)use Q>N\(\Theta(Q \log N)\)Θ(Q log N)로 단순화 가능full derivation을 먼저 쓰고 조건을 나중에 적용한다. \(Q>N\)Q>N이면 \(N \log N\le Q \log N\)N log N≤Q log N이므로 합은 \(\Theta(Q \log N)\)Θ(Q log N)이지만, preprocessing을 실제로 하지 않았다는 뜻은 아니다.
N=8, Q=20의 비용 항 읽기정확한 machine step 수가 아니라 성장 항을 비교한다. \(\log_{2}8=3\)log₂8=3이고 \(Q>N\)Q>N이다.
\(N \log_{2}N\)N log₂N은 8×\(3=24\)3=24규모이며 query 전에 한 번 든다.
query당 두 binary search가 상수 2를 제외하면 log N 규모이고 Q번 반복된다.
query scale≈20×\(3=60\)3=6024+60을 모두 유도한 뒤 \(N<Q\)N<Q라 N log N 항이 Q log N보다 크지 않음을 사용한다.
Θ(N log N+Q log N)=Θ(Q log N)copy A는 \(\Theta(N)\)Θ(N), output C는 \(\Theta(Q)\)Θ(Q)이며 output은 반드시 써야 한다.
Θ(N), output \(\Theta(Q)\)Θ(Q)작은 예제의 결론: 전처리 항을 유도에서 보여 주면서도 최종 tight bound를 \(\Theta(Q \log N)\)Θ(Q log N)으로 단순화하는 두 문장은 서로 모순이 아니다.
O(N log N)이라고만 쓰면 안 되나?Q개 query 각각의 두 boundary search 비용을 누락하기 때문이다. Q가 N보다 크므로 오히려 \(\Theta(Q \log N)\)Θ(Q log N) query 항이 전체를 지배한다.
Q>N에서 \(\Theta(Q \log N)\)Θ(Q log N)만 쓰는 것이 수학적으로 틀린가?아니다. full derivation은 \(\Theta(N \log N+Q \log N)\)Θ(N log N+Q log N)이고 \(Q>N\)Q>N이면 \(N \log N<Q \log N\)N log N<Q log N이라 tight bound를 \(\Theta(Q \log N)\)Θ(Q log N)으로 단순화할 수 있다. 시험 답안에는 두 단계를 함께 쓰는 것이 가장 명확하다.
N=0이면 \(\Theta(\log N)\)Θ(log N)을 그대로 쓸 수 있나?log 0은 정의되지 않고 \(\log(1)=0\)log(1)=0은 상수 초기 검사도 나타내지 못하므로, \(N\ge 0\)N≥0전체의 tight bound는 \(\Theta(\log(N+2))\)Θ(log(N+2))로 쓴다. 시험의 보통 분석은 \(N\ge 2\)N≥2를 전제로 \(\Theta(\log N)\)Θ(log N)을 쓴다.
서로 다른 N개 값으로 된 hard-instance sorted S를 고정하면 prefix형 query 하나의 count가 0…N 중 어느 값도 될 수 있다. Q개가 독립이면 \((N+1)^{Q}\)(N+1)ᴽ개의 output vector를 비교 결과로 구분해야 하므로 Ω\((\log((N+1)^{Q}))=\Omega(Q \log(N+1)) \text{comparisons}\)(log((N+1)ᴽ))=Ω(Q log(N+1)) comparisons가 필요하다.
소득 universe 최대값 M이나 bit/digit bound가 주어지지 않았다. counting/radix 방법의 시간·공간은 M 또는 digit 수에도 의존하므로 comparison-model 최적성 주장과 별도 가정이 필요하다.
Q>N단순화를 서로 다른 줄에 써 수학적 등가와 구현 단계를 함께 보인다.N≥2또는 log(N+2) convention을 명시한다.Θ(N)과 반드시 반환할 output \(\Theta(Q)\)Θ(Q)를 구분한다.힌트: 먼저 모든 항을 쓰고 지배 항으로 단순화한다.
정답: \(\Theta(N \log N+Q \log N)\)Θ(N log N+Q log N)이며 \(Q>N\)Q>N조건 아래 \(\Theta(Q \log N)\)Θ(Q log N)으로 단순화할 수 있다.
힌트: integer range나 word operation을 추가로 이용하는 algorithm을 생각한다.
정답: 작은 bounded universe 같은 추가 구조가 있으면 counting/radix/predecessor 방법의 bound가 달라질 수 있어 비교만 허용한 lower bound가 자동 적용되지 않기 때문이다.
힌트: A 복사본과 Q개 답을 따로 센다.
정답: MergeSort용 A와 보조 배열 기준 working \(\Theta(N)\)Θ(N), 반환 output C는 \(\Theta(Q)\)Θ(Q)다.
각 단계에서 무엇을 했는지, 왜 그렇게 했는지, 결과가 무엇인지 차례대로 확인합니다.
복사: \(\Theta(N)\)Θ(N). 정렬: \(\Theta(N \log N)\)Θ(N log N).
\(N\ge 2\)N≥2인 시험 관례에서 각 질의: lowerBound \(\Theta(\log N)\)Θ(log N)+upperBound \(\Theta(\log N)\)Θ(log N)+상수 뺄셈 \(\Theta(1)\)Θ(1)=\(\Theta(\log N)\)Θ(log N). \(N=0\)N=0까지 포괄하는 tight bound는 \(\Theta(\log(N+2))\)Θ(log(N+2))이다.
Q개 질의: \(N\ge 2\)N≥2에서 \(\Theta(Q \log N)\)Θ(Q log N). 결과 배열 C를 쓰는 데도 \(\Omega(Q)\)Ω(Q)가 필요하며 이 항은 \(\Theta(Q \log N)\)Θ(Q log N)에 포함된다.
전체: \(\Theta(N \log N + Q \log N)\)Θ(N log N + Q log N). 같은 식을 \(\Theta((N+Q)\log N)\)Θ((N+Q)log N)이라고 써도 된다.
문제 조건 \(Q>N\)Q>N을 적용하면 \(N \log N<Q \log N\)N log N<Q log N이므로 전체를 \(\Theta(Q \log N)\)Θ(Q log N)으로 올바르게 단순화할 수 있다. 답안에는 full derivation과 조건 적용 후 단순화를 둘 다 쓰면 가장 명확하다.
valid query lⱼ≤hⱼ를 전제로 S를 worst-case \(\Theta(N \log N)\)Θ(N log N)에 오름차순 정렬한다. 각 질의에 대해 \(L=\)L=첫 \(A[i]\ge l\)A[i]≥lⱼ 또는 \(N, R=\)N, R=첫 \(A[i]>h\)A[i]>hⱼ 또는 N을 경계 binary search로 찾고 Cⱼ=R−L로 둔다. \(N\ge 2\)N≥2에서 두 helper는 각각 \(\Theta(\log N)\)Θ(log N), 전체는 \(\Theta(N \log N+Q \log N)\)Θ(N log N+Q log N)이며 \(Q>N\)Q>N이므로 \(\Theta(Q \log N)\)Θ(Q log N)으로 단순화할 수 있다. 이는 comparison model에서 \(\Omega(Q \log N)\)Ω(Q log N) lower bound와 맞는다. 결과 공간은 \(\Theta(Q)\)Θ(Q), 정렬 복사본은 추가 \(\Theta(N)\)Θ(N)이다.
O(N log N)이라고만 쓰고 Q개 질의 비용을 누락한다.O(2 log N)이라고 끝낸다. 상수를 제거하면 \(\Theta(\log N)\)Θ(log N)이다.Θ(Q log N) 단순화만 쓰고 정렬 \(\Theta(N \log N)\)Θ(N log N)과 Q개 query \(\Theta(Q \log N)\)Θ(Q log N)을 어떻게 합했는지 유도 과정을 전혀 보여주지 않는다.복기 문언, 강의 정의, 공식 연습 풀이, 추가 유도를 구분해 표시합니다.
AuD Gedächtnisprotokoll SoSe 2025.md · lines 321-332직접 근거: 입력, \(Q>N,\)Q>N,정적 소득 목록, 양끝 포함 구간 개수 세기(inclusive range count), 최대점수의 최적성 요구
Vorlesung\02Sorting.pdf · p.51; pp.54-80 sorting sections직접 강의 근거: 이진 탐색(binary search)의 로그 시간, MergeSort와 \(\Theta(N \log N)\)Θ(N log N) 정렬 분석
Vorlesung\02Sorting_updated.pdf · pp.136-147직접 강의 근거: 비교 기반 모델(comparison-based model), 정렬 실행시간 비교, 결정 트리 하한
Übung\AuD26_Sheet03-GrpSol.pdf · pp.1-3, 7-9직접 연습 근거: MergeSort 단계와 반복별 실행시간 합산 방식
이 페이지의 유도 · 8.3-8.5일반 알고리즘 지식: lowerBound/upperBound의 센티널 변형, 구간 개수 정확성, \((N+1)^{Q}\)(N+1)ᴽ출력 비교 하한
마지막 생성: 2026-08-02 08:51