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가지가 될 수 있다. |
아래 선수 개념부터 차례대로 읽으면 실제 문제의 요구를 이해할 수 있습니다.
시험에서는 코드를 적는 것만으로 최대 점수를 보장하지 않는다. 정렬이 답을 보존하고, 두 boundary가 answer block의 바깥을 정확히 잘라 내며, [L,R)의 길이가 R−L이라는 논리 사슬을 제시해야 구현과 정답성 사이의 빈틈을 닫을 수 있다.
몇 개 예제가 맞는 것을 넘어 모든 valid input에서 알고리즘 출력이 명세와 같음을 논리적으로 보이는 설명이다. 각 코드 단계가 유지하는 사실과 종료 시 결론을 연결한다.
i<L이면 \(A[i]<l, L\le i<R\)A[i]<l, L≤i<R이면 범위 안, \(i\ge R\)i≥R이면 \(A[i]>h\)A[i]>h라고 세 구역을 증명한다.loop 시작과 반복 뒤에도 계속 참인 사실이다. binary search에서는 답 boundary가 후보 안에 남고 확정적으로 작은 또는 큰 구역이 후보 밖에 쌓인다는 사실을 쓴다.
i<lo는 \(A[i]<x\)A[i]<x이고 모든 \(i\ge \text{hi}\)i≥hi는 \(A[i]\ge x\)A[i]≥x다.알고리즘이 무한히 돌지 않고 끝남을 보이는 성질이다. 각 binary-search iteration에서 hi−lo가 엄격히 줄고 음수가 될 수 없으므로 \(\text{lo}=\text{hi}\)lo=hi에 도달한다.
8→4→2→1→0으로 감소한다. 길이 0일 때 답 boundary 하나 \(\text{lo}=\text{hi}\)lo=hi가 확정된다.정렬된 창고 선반에서 왼쪽 안전문 L은 너무 싼 물건을 모두 밖에 두고, 오른쪽 안전문 R은 너무 비싼 첫 물건 앞에서 닫힌다. 두 문 사이 선반만 허용 구역이며 어느 물건도 빠지거나 섞이지 않았음을 문별로 증명한다.
first index with A[i]≥lfirst index with A[i]>h비유의 한계: 안전문 비유는 이미 정렬된 array를 전제로 한다. 정렬 보존을 먼저 증명하지 않으면 원본 S의 answer와 연결되지 않는다.
2. i<L 제외모든 왼쪽 값은 l보다 작다.3. L≤i<R 포함각 값이 l 이상 h 이하다.4. i≥R 제외모든 오른쪽 값은 h보다 크다.어느 한 고리도 생략하지 않는다. 특히 정렬이 같은 multiset을 보존한다는 첫 고리가 있어야 sorted A에서 센 결과가 원본 S의 주민 수와 같아진다.
\(S=[5,1,2,2,9], \text{queries}=[[2,5],[0,1],[6,8]]\)S=[5,1,2,2,9], queries=[[2,5],[0,1],[6,8]]이다. \(A=[1,2,2,5,9]\)A=[1,2,2,5,9]를 한 번 만든다.
첫 ≥2는 \(L=1,\)L=1,첫 >5는 \(R=4\)R=4라 indices 1,2,3의 2,2,5를 센다.
C[0]=4−1=3첫 ≥0은 \(L=0,\)L=0,첫 >1은 \(R=1\)R=1이라 값 1 하나를 센다.
C[1]=1−0=1첫 ≥6과 첫 >8이 모두 index 4의 값 9 앞 boundary다.
\(C[2]=4−4=0\)C[2]=4−4=0각 결과를 같은 j 위치에 저장했으므로 query order가 보존된다.
\(C=[3,1,0]\)C=[3,1,0]작은 예제의 결론: 정렬은 한 번뿐이고 세 query는 같은 A를 사용한다. 손으로 scan한 답과 \(C=[3,1,0]\)C=[3,1,0]이 일치한다.
A는 S의 permutation이라 각 소득값의 등장 횟수가 같다. query는 위치가 아니라 값이 범위에 드는 원소 수만 묻기 때문에 어느 order에서 세어도 count가 같다.
i<L인 값은 전부 제외되나?L은 첫 \(A[i]\ge l\)A[i]≥l위치다. sorted array에서 그보다 왼쪽 index는 모두 l보다 작으므로 lower condition을 만족하지 못한다.
L≤i<R인 값은 전부 포함되나?\(i\ge L\)i≥L이면 \(A[i]\ge l\)A[i]≥l이고, \(i<R\)i<R이면 R이 첫 >h 위치이므로 \(A[i]\le h\)A[i]≤h다. 두 부등식을 합치면 \(l\le A[i]\le h\)l≤A[i]≤h다.
i≥R인 값은 전부 제외되나?R부터 첫 값이 h보다 크고 array가 nondecreasing이므로 그 오른쪽 값도 모두 h보다 크다.
R은 마지막 포함 index가 아니라 첫 제외 boundary다. half-open indices L,L+1,…,R−1의 개수는 정확히 R−L이고 empty block도 0이 된다.
three-zone partition i<L, L≤i<R, i≥R가 모든 index를 겹침 없이 덮는지 확인한다.힌트: empty answer와 끝 sentinel에서 +1 공식을 생각한다.
정답: R−L+1과 별도 not-found 처리가 필요해 empty/end case가 복잡해진다. 첫 >h boundary가 더 일관된다.
A=[1,2,4]이고 query [2,3]일 때 세 구역을 쓰라.힌트: \(L=1, R=2\)L=1, R=2를 기준으로 나눈다.
정답: \(i<1\)i<1의 [1]은 too small, [1,2)의 [2]는 \(\text{answer}, i\ge 2\)answer, i≥2의 [4]는 too large다.
힌트: sorted A의 count와 원본 S의 count를 연결해야 한다.
정답: A에서 올바르게 세었다는 사실이 원본 S의 주민 수와 같다는 첫 논리 연결이 사라진다.
복기 문언, 강의 정의, 공식 연습 풀이, 추가 유도를 구분해 표시합니다.
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