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가지가 될 수 있다. |
아래 선수 개념부터 차례대로 읽으면 실제 문제의 요구를 이해할 수 있습니다.
일반 binary search는 같은 값 하나를 찾으면 끝나므로 duplicate의 처음과 끝을 알 수 없다. 이 단계는 원소가 아니라 N+1개의 boundary 위치를 찾고, inclusive [l,h]를 정확히 half-open [L,R)로 바꿔 빈 배열·중복·끝 sentinel까지 같은 코드로 처리한다.
N=0, N=1,모든 값 동일, 값 없음 상황에서 sentinel N과 R−L이 안전하게 동작함을 확인할 수 있다.N개 원소에는 원소 앞·사이·뒤를 합쳐 N+1개의 boundary 0…N이 있다. N은 마지막 원소 index가 아니라 배열 끝 다음 위치이며 찾는 조건의 원소가 없을 때 반환할 수 있다.
A=[2,5]의 원소 index는 0,1이고 boundary는 0|2|1|5|2처럼 0,1,2 세 곳이다.lowerBound(A,x)는 첫 값 ≥x인 boundary, upperBound(A,x)는 첫 값 >x인 boundary다. 둘 다 조건을 만족하는 실제 원소가 없으면 N을 반환하도록 후보에 N을 포함한다.
A=[2,2,5]에서 \(\text{lowerBound}(2)=0, \text{upperBound}(2)=2\)lowerBound(2)=0, upperBound(2)=2라서 2의 개수는 2다.탐색 중 가능한 답 boundary는 닫힌 [lo,hi]에 보존하고, 실제로 비교할 미해결 원소 index만 반열린 [lo,hi)로 다룬다. mid가 답 후보이면 \(\text{hi}=\text{mid}\)hi=mid로 남기고 확실히 왼쪽이면 \(\text{lo}=\text{mid}+1\)lo=mid+1로 버린다.
hi=4가 되면 indices 4…7을 버리고 답 boundary 4 자체는 여전히 가능하다.소득순 줄에서 lowerBound는 최소 소득 조건을 처음 통과하는 사람 앞의 문이다. upperBound는 최대 소득을 넘는 첫 사람 앞의 문이다. 두 문 사이에 서 있는 사람 수는 오른쪽 문 번호에서 왼쪽 문 번호를 뺀 값이다.
L=first index with A[i]≥lR=first index with A[i]>h비유의 한계: 실제 줄에서는 사람이 움직이지만 sorted array는 query 동안 변하지 않는다. boundary 번호는 사람 자체가 아니라 원소 사이 위치라는 점을 유지해야 한다.
A[i]≥l위치, 왼쪽 값은 모두 너무 작다.A[i]>h위치, R 자체 원소는 answer가 아니다.A의 index는 0…N−1이지만 L과 R은 0…N boundary다. [L,R)에 들어간 값만 세므로 마지막 포함 index를 따로 계산하거나 +1 예외를 둘 필요가 없다.
\(A=[1,2,2,2,5], \text{query} [2,2]\)A=[1,2,2,2,5], query [2,2]다. 원소 index는 0…4이고 boundary는 0…5다.
첫 \(A[i]\ge 2\)A[i]≥2는 index 1의 값 2다. 같은 2가 더 있어도 가장 왼쪽 boundary를 찾는다.
L=1첫 \(A[i]>2\)A[i]>2는 index 4의 값 5다. A[1],A[2],A[3]의 2를 모두 포함한 뒤 멈춘다.
R=4answer indices는 1,2,3이고 [1,4)의 길이는 4−1이다.
\(C=R−L=4−1=3\)C=R−L=4−1=3작은 예제의 결론: upperBound 대신 lowerBound(2)를 오른쪽에도 쓰면 \(R=L=1\)R=L=1이 되어 오답 0이 된다. \(\text{first} >h\)first >h가 inclusive endpoint를 보존한다.
찾는 답은 원소 index뿐 아니라 모든 값 뒤의 boundary N일 수 있다. 답 boundary를 닫힌 [lo,hi]에 보존하고 \(\text{hi}=N\)hi=N을 두면 빈 array와 x가 모든 값보다 큰 경우도 별도 분기 없이 처리한다.
A[mid]=x이면 왜 즉시 return하지 않나?duplicate x가 mid보다 왼쪽에 더 있을 수 있다. mid도 답 후보로 남기면서 왼쪽 절반을 계속 보기 위해 \(\text{hi}=\text{mid}\)hi=mid로 줄인다.
\(A[\text{mid}]=h\)A[mid]=h인 원소도 query에 포함해야 하므로 그 위치를 오른쪽 문 왼쪽에 남긴다. 따라서 \(A[\text{mid}]\le h\)A[mid]≤h이면 \(\text{lo}=\text{mid}+1\)lo=mid+1로 이동해 첫 >h를 찾는다.
정렬 A에서 첫 ≥2500은 index 2이므로 \(L=2,\)L=2,첫 >4000은 index 6의 4200이므로 \(R=6\)R=6이다. [2,6)의 네 값이 답이다.
N=0에서도 어떤 값이 나오나?처음부터 \(\text{lo}=\text{hi}=0\)lo=hi=0이라 두 helper 모두 \(0=N\)0=N을 반환한다. valid query라면 R−\(L=0\)L=0이고 초기 검사까지 포함한 질의 비용은 \(\Theta(\log(N+2))\)Θ(log(N+2))=\(\Theta(1)\)Θ(1)이다.
L=0또는 \(N, R=0\)N, R=0또는 N을 포함해 항상 \(0\le L\le R\le N\)0≤L≤R≤N인지 \(\text{유효} \text{query} l\le h\)valid query l≤h에서 확인한다.i<L은 \(A[i]<l,\)A[i]<l,모든 \(L\le i<R\)L≤i<R은 \(l\le A[i]\le h,\)l≤A[i]≤h,모든 \(i\ge R\)i≥R은 \(A[i]>h\)A[i]>h인지 확인한다.lo=hi에서 종료하는지 structured trace를 확인한다.A=[1,2,2,5]에서 query [2,5]의 L,R,count는?힌트: 첫 ≥2와 첫 >5를 찾고 끝 다음 sentinel을 허용한다.
정답: \(L=1,\)L=1, \(R=4\)R=4=N, count=4−\(1=3\)1=3이다.
A[mid]<x로 쓰면 어떤 값이 빠지나?힌트: \(A[\text{mid}]=x\)A[mid]=x일 때 어느 방향으로 가는지 본다.
정답: x와 같은 값들을 오른쪽 boundary 전에 모두 포함하지 못해 inclusive upper endpoint h의 duplicate가 빠질 수 있다.
A=[1,4,4,4,9]에서 [3,8]을 계산하라.힌트: 정확한 3이나 8이 배열에 없어도 insertion boundary를 찾는다.
정답: 첫 ≥3은 \(L=1,\)L=1,첫 >8은 \(R=4\)R=4이므로 \(\text{count}=3\)count=3이며 값 [4,4,4]을 센다.
A[i]≥h로 정의해 h와 같은 사람들을 제외한다.A[mid]=x일 때 즉시 return하여 첫 위치를 보장하지 못한다.복기 문언, 강의 정의, 공식 연습 풀이, 추가 유도를 구분해 표시합니다.
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