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가지가 될 수 있다. |
아래 선수 개념부터 차례대로 읽으면 실제 문제의 요구를 이해할 수 있습니다.
빠른 알고리즘을 쓰기 전에 입력과 출력 조건을 잘못 읽으면 아무리 효율적인 코드도 틀린 답을 낸다. 이 단계는 소득의 합이 아니라 사람 수를 세고, 중복과 양쪽 inclusive 경계를 보존하며, 느리지만 분명한 baseline으로 이후 빠른 해법의 정답을 검산하게 한다.
l≤S[i]≤h를 말로 설명할 수 있다.Θ(NQ) 비용을 반복 횟수로 유도할 수 있다.array는 값을 순서대로 담은 고정 길이 칸들의 열이고 index는 각 칸의 위치 번호다. 이 페이지의 코드는 0부터 시작해 길이 N이면 마지막 index가 N−1이다.
S=[4,7,4]이면 \(N=3, S[0]=4, S[1]=7, S[2]=4\)N=3, S[0]=4, S[1]=7, S[2]=4다.multiset은 같은 값이 여러 번 나타날 수 있고 각 등장 횟수를 보존하는 값 모음이다. 주민 두 명의 소득이 같아도 서로 다른 두 사람이라 둘 다 세어야 한다.
S=[1800,1800,2500]에서 query [1800,1800]의 답은 1이 아니라 2다.query [l,h]는 l 이상과 h 이하를 모두 포함한다. 이 페이지는 \(l\le h\)l≤h인 valid query를 입력 전제로 두며, \(l>h\)l>h가 오면 invalid로 보고 0을 반환하거나 거절하는 정책을 별도로 명시한다.
시청 직원이 주민 소득 명단을 한 줄씩 들고 있다. 질문 하나가 오면 첫 주민부터 마지막 주민까지 확인하고, 소득이 두 경계 사이면 tally mark를 하나 긋는다. 정확하지만 질문이 많으면 같은 명단을 계속 다시 읽는다.
비유의 한계: 실제 명단은 이름 등 다른 정보도 있지만 이 문제는 소득값과 조건을 만족하는 원소 개수만 사용하며 주민 신원이나 합계는 출력하지 않는다.
바깥 반복은 Q개의 query를 하나씩 선택하고, 안쪽 반복은 같은 S의 N개 원소를 전부 본다. 그래서 검사 횟수는 N+N+…+\(N(Q번)=\text{NQ}\)N(Q번)=NQ다.
S=[2,5,2,9]에 두 query\(N=4, \text{queries}=[[2,5],[6,10]]\)N=4, queries=[[2,5],[6,10]]이고 양쪽 경계를 포함한다. 결과 C는 query 순서와 같은 길이 2의 array다.
2,5,2는 \(l\le \text{value}\le h\)l≤value≤h를 만족하고 9는 넘는다. 중복 2 두 개를 각각 센다.
count=3, C[0]=32,5,2는 하한보다 작고 9 하나만 포함된다.
\(\text{count}=1, C[1]=1\)count=1, C[1]=1query마다 원소 4개를 보았고 query가 2개라 조건 검사를 8번 했다.
\(C=[3,1]\)C=[3,1], work=NQ=4×\(2=8\)2=8작은 예제의 결론: baseline은 \(C=[3,1]\)C=[3,1]을 정확히 반환하지만 Q가 매우 커지면 매번 같은 S를 다시 읽는 비용 \(\Theta(\text{NQ})\)Θ(NQ)이 병목이 된다.
각 query j마다 \(l[j]\le S[i]\le h[j]\)l[j]≤S[i]≤h[j]를 만족하는 index i의 개수 C[j]를 출력한다. 소득값의 합이나 주민 목록이 아니라 count만 반환한다.
s₁…\(s_{N}\)sₙ과 코드 S[0]…S[N−1]은 다른 입력인가?아니다. 같은 N개 값을 수학 표기는 1부터, 구현 표기는 0부터 번호 붙인 것이다. 값과 순서는 같고 위치 이름만 한 칸씩 다르다.
각 query에서 모든 원소를 정확히 한 번 검사하고 조건이 참인 경우에만 count를 증가시키므로, 조건을 만족하는 원소를 빠뜨리거나 두 번 세지 않는다.
Θ(NQ)인가?바깥 loop가 Q번, 그때마다 안쪽 loop가 정확히 N번 실행된다. 상수 시간 비교·증가를 NQ번 하므로 tight bound가 \(\Theta(\text{NQ})\)Θ(NQ)다.
S=[1,3,3,8]에서 [3,3]의 답은?힌트: 같은 소득 두 사람을 따로 센다.
정답: 3이 두 번 등장하므로 답은 2다.
N=5, Q=7이면 조건을 몇 번 검사하는가?힌트: 바깥 loop 횟수와 안쪽 loop 횟수를 곱한다.
정답: 각 query마다 5번, 총 7개 query이므로 35번이며 일반식은 \(\Theta(\text{NQ})\)Θ(NQ)다.
l>h query가 들어오면 이 페이지의 정책은 무엇인가?힌트: 공식 입력 전제를 먼저 확인한다.
정답: 정상 입력은 \(l\le h\)l≤h를 전제로 한다. 방어적 구현에서는 \(l>h\)l>h를 invalid로 보고 0을 반환하거나 오류 처리한다고 명시한다.
Q>N조건을 읽고도 질의마다 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