8. Algorithmen-Entwurfsmethoden — Einkommensstatistik (12 Punkte)

8.2 · 전처리: 소득 배열을 한 번만 정렬하기

선행지식이 전혀 없어도 이 페이지 하나에서 용어를 배우고, 작은 예제를 거쳐 실제 시험 풀이와 검산까지 따라가도록 구성했습니다.

  1. 용어: 기호와 전제
  2. 직관: 비유와 작은 예
  3. 풀이: 실제 상태 변화
  4. 확인: 검산과 자가점검

자료의 성격과 정확성 경계

문제 조건과 만점의 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가지가 될 수 있다.

먼저 문제의 정체를 줄글로 이해하기

아래 선수 개념부터 차례대로 읽으면 실제 문제의 요구를 이해할 수 있습니다.

필요한 개념을 깊게 배우기

초보자용 연결 강의

이 소문제를 왜 배우나

S가 모든 query 동안 변하지 않는다는 조건은 같은 준비 작업을 반복하지 말라는 신호다. 정렬 전처리는 값의 등장 횟수를 보존하면서 조건을 만족하는 값들을 연속 블록으로 모아, 이후 각 query가 전체 명단 대신 두 boundary만 찾게 만든다.

풀이 전에 꼭 알아야 할 말

sorting(정렬)

array의 같은 원소들을 key 오름차순으로 재배치하는 작업이다. 값의 종류와 등장 횟수는 바꾸지 않고 위치만 바꾸므로 count 문제의 답은 보존된다.

아주 작은 예: [4,1,4,2]를 정렬하면 [1,2,4,4]이며 4의 등장 횟수 2는 그대로다.

preprocessing(전처리)

여러 query가 오기 전에 변하지 않는 입력을 한 번 가공해 두는 단계다. 전처리 비용은 한 번 들고, 그 결과를 모든 query가 반복 사용한다.

아주 작은 예: S를 query loop 밖에서 한 번 sort하고 Q개 query가 같은 sorted A를 쓴다.

worst-case 보장

어떤 입력 순서에서도 넘지 않는 실행시간 보장이다. 시험에서 최악 \(\Theta(N \log N)\)Θ(N log N)을 확실히 쓰려면 MergeSort 또는 HeapSort처럼 해당 bound가 보장되는 알고리즘을 명시한다.

아주 작은 예: 이미 정렬된 입력에서도 MergeSort는 같은 divide/merge 구조로 \(\Theta(N \log N)\)Θ(N log N)이다.

도서관을 한 번 번호순으로 정리하기

질문이 올 때마다 뒤섞인 책 더미 전체를 뒤지는 대신 개관 전에 책을 번호순으로 한 번 정리한다. 그 뒤 ‘2500부터 4000까지’ 같은 질문은 해당 구역의 시작 선반과 끝 다음 선반만 찾으면 된다.

개관 전 책 정리
↔
query 전에 한 번 수행하는 sorting preprocessing
책 번호순 선반
↔
nondecreasing sorted array A
같은 제목 책 여러 권
↔
삭제하면 안 되는 duplicate incomes
매 질문에서 같은 선반 사용
↔
정적 S에서 전처리 결과 재사용

비유의 한계: 실제 도서관은 책을 물리적으로 옮기는 비용과 검색 체계가 다양하지만 이 문제의 비용 모델은 array 정렬과 비교 횟수를 점근적으로 센다.

흩어진 조건 만족 값이 한 블록이 되는 이유

정렬 전 S4200,1800,2500,5100,2500,3200,1800,4000
한 번 sort원소의 multiset은 보존하고 위치만 바꾼다.
정렬 후 A1800,1800,2500,2500,3200,4000,4200,5100
연속 query block[2500,4000]은 indices 2…5 한 덩어리다.

정렬 전에는 2500·3200·4000이 여러 위치에 흩어질 수 있지만 정렬 뒤에는 더 작은 값, [2500,4000] 블록, 더 큰 값 순서로만 놓인다. 블록의 두 boundary만 알면 내부를 다시 세지 않아도 된다.

먼저 작은 예제로 연습 · 왜 정렬 뒤 범위가 연속인가

\(S=[7,2,5,2,9]\)S=[7,2,5,2,9]를 \(A=[2,2,5,7,9]\)A=[2,2,5,7,9]로 정렬하고 query [3,8]을 생각한다.

multiset 보존 확인

정렬 전후 모두 2 두 개, 5,7,9 한 개씩 있어 각 값의 주민 수가 같다.

S와 A의 value counts 동일
구간 밖 왼쪽 확인

3보다 작은 값 2,2는 정렬상 모두 만족 블록 왼쪽에 있다.

indices 0,1 제외
구간 블록 확인

5와 7은 3 이상 8 이하이고 정렬 때문에 그 사이에 조건 밖 값이 끼어들 수 없다.

answer block \(A[2…3]=[5,7]\)A[2…3]=[5,7]
구간 밖 오른쪽 확인

8보다 큰 9와 그 이후 값은 모두 만족 블록 오른쪽에 있다.

index 4 제외, \(\text{count}=2\)count=2

작은 예제의 결론: 정렬 후 answer indices는 하나의 half-open block [2,4)이고 길이는 4−\(2=2\)2=2다. 이 구조가 두 boundary search를 가능하게 한다.

이제 실제 시험 문제에 연결

왜 원본 S를 정렬해도 답이 바뀌지 않나?

각 query는 원래 위치나 주민 이름이 아니라 조건에 맞는 값의 등장 횟수만 묻는다. 정렬은 같은 multiset의 순서만 바꾸므로 모든 range count가 같다.

왜 duplicate를 제거하면 안 되나?

같은 소득을 받는 서로 다른 주민도 각각 한 명이다. deduplication은 multiset을 set으로 바꿔 등장 횟수를 잃으므로 query 답을 줄여 버린다.

정렬을 어디에서 몇 번 호출해야 하나?

query loop에 들어가기 전에 정확히 한 번 호출한다. query마다 다시 sort하면 Q번 \(\Theta(N \log N)\)Θ(N log N)을 지불해 전처리 재사용 목적을 잃는다.

어떤 sorting algorithm을 쓰는 것이 안전한가?

worst-case bound를 요구하므로 MergeSort나 HeapSort처럼 \(\Theta(N \log N)\)Θ(N log N)이 보장되는 course algorithm을 명시한다. QuickSort는 별도 보장 없이 worst-case \(\Theta(N \log N)\)Θ(N log N)이라고 쓰면 안 된다.

답이 맞는지 스스로 검산

  • 정렬 전후 array 길이 N과 각 값의 등장 횟수가 모두 같은지 확인한다.
  • \(A[0]\le A[1]\)A[0]≤A[1]≤…≤A[N−1]인지 인접 pair를 비교해 sorted invariant를 확인한다.
  • sort 호출이 query loop 바깥에 한 번만 있고 모든 query가 같은 A를 읽는지 pseudocode에서 확인한다.

30초 자가점검

[4,1,4,3]을 정렬한 결과와 4의 등장 횟수는?

힌트: 값을 삭제하지 말고 오름차순으로만 옮긴다.

정답: \(A=[1,3,4,4]\)A=[1,3,4,4]이고 4는 여전히 두 번 등장한다.

query마다 MergeSort를 다시 하면 전체 정렬 비용은?

힌트: 한 번의 \(\Theta(N \log N)\)Θ(N log N)을 Q번 반복한다.

정답: \(\Theta(\text{QN} \log N)\)Θ(QN log N)이라서 한 번 전처리하는 설계보다 불필요하게 크다.

정렬 뒤 [l,h]를 만족하는 값이 두 조각으로 떨어질 수 있는가?

힌트: 두 만족 값 사이의 값을 정렬 순서로 생각한다.

정답: 없다. 두 만족 값 사이의 값도 l 이상 h 이하이므로 answer는 하나의 연속 block이다.

마지막에 쓰는 시험 답안 틀

자주 하는 실수

근거와 정확성 범위

복기 문언, 강의 정의, 공식 연습 풀이, 추가 유도를 구분해 표시합니다.

마지막 생성: 2026-08-02 08:51