8번 · 소득 구간 질의를 빠르게 처리하는 알고리즘

배열과 이진 탐색을 처음 보는 사람도 이해하도록, 공식 한 문제를 다섯 학습 단계로 나누고 한국어 줄글 설명과 수식을 한 흐름으로 이어 놓았습니다.

독일어 원제 확인

8. Algorithmen-Entwurfsmethoden — Einkommensstatistik (12 Punkte)

공식 문제 구조 · 8.1 (12P)

원문에는 12점짜리 소문항 8.1 하나만 있다. 아래 1/5~5/5 표시는 공식 소문항이나 채점 배점이 아니라, 선행지식 0인 학습자를 위해 이 한 문제를 다섯 학습 단계로 나눈 내부 표기다.

선행지식 0에서 시작

이 페이지를 읽는 순서

array, 정렬, binary search, 시간복잡도를 처음 보는 학습자를 대상으로 한다. 원문 12점 문제 하나를 모델링→전처리→경계 탐색→정확성→복잡도의 다섯 학습 단계로 나누되, 각 단계는 공식 소문항이 아님을 분명히 한다.

  1. 입력과 출력을 작은 숫자로 번역한다N, Q, S, [l,h], C의 뜻을 실제 주민 명단과 여러 질의 예제로 바꾸고 무엇을 세는지 먼저 확인한다.
  2. 느린 해법으로 정답 조건을 고정한다질의마다 모든 소득을 보는 baseline을 손으로 실행해 inclusive 경계와 중복이 답에 어떻게 반영되는지 이해한다.
  3. 정렬 뒤 두 경계를 추적한다index 행과 원소 사이의 N+1개 boundary를 보며 lowerBound와 upperBound가 후보 구간을 절반씩 버리는 과정을 따라간다.
  4. 증명·복잡도·연습으로 마무리한다왜 [L,R)의 길이가 답인지 증명하고, 전체 비용을 합산한 뒤 \(Q>N\)Q>N조건으로 단순화하고 자가점검을 푼다.

기호·용어 미니 사전

이 문제의 핵심은 “값을 직접 세기”를 “정렬된 배열의 두 경계 사이 길이 재기”로 바꾸는 것이다. 아래 기호는 그 변환을 읽는 최소한의 언어다.

기호/용어한국어 뜻이 문제의 예
\(S[0\ldots 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이다.
\([\ell,h]\)l 이상 h 이하를 모두 포함하는 closed query interval이며 이 페이지는 \(\text{유효} \text{query} l\le h\)valid query l≤h를 전제로 한다.[2500,4000]은 2500과 4000도 센다.
\(\text{원소 }[lo,hi)\;/\;\text{답 경계 }[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)의 상수배 수준으로 증가한다는 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가 남는다.
deterministic난수나 우연한 선택 없이 같은 입력에는 같은 실행 규칙과 같은 출력을 내는 알고리즘이라는 뜻이다.이 페이지의 정렬과 lowerBound는 같은 배열·질의에 언제나 같은 경계를 반환한다.
다항 시간(polynomial-time)입력 크기의 어떤 고정된 거듭제곱으로 실행시간 상한을 쓸 수 있다는 뜻이다. 풀 수 있을 만큼 체계적인 해법이라는 넓은 기준이지, 그중 가장 빠르다는 뜻은 아니다.질의마다 전부 확인하는 \(\Theta(\text{NQ})\)Θ(NQ)도 polynomial이지만 \(Q>N\)Q>N인 이 문제에서는 optimal하지 않다.
rank / comparison modelrank는 정렬 순서에서 한 값보다 작은 원소의 개수, 즉 그 값이 들어갈 boundary 위치다. comparison model은 값에 대해 <,≤,> 같은 비교 결과만으로 결정을 내린다고 가정한다.서로 다른 N개 값의 hard instance에서는 prefix 질의의 답 rank가 0부터 N까지 N+1가지가 될 수 있다.
정확성 경계

문제 조건과 만점의 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정책은 강의 개념에서 이 페이지가 명시적으로 유도한 일반 알고리즘 지식이며 공식 해설을 인용한 것이 아니다.

먼저 필요한 개념을 0부터

아래 네 절은 독립 카드 모음이 아니라, “직접 세기 → 한 번 정렬하기 → 두 경계 찾기 → 두 경계의 차로 개수 구하기”라는 하나의 이야기로 읽으면 된다.

0. 변수와 기호부터 번역하기

N은 주민 수이자 소득 배열의 길이다. S[i]는 i번째 주민의 월소득이다. 같은 소득을 받는 주민이 여러 명 있을 수 있으므로 배열 값은 중복될 수 있다.

Q는 질문의 개수다. j번째 질문은 하한 lⱼ와 상한 hⱼ를 주며, 두 경계는 모두 포함(inclusive)된다. 즉 소득이 정확히 lⱼ 또는 hⱼ인 주민도 센다.

C[j]는 j번째 질문의 답이다. 문제는 소득의 합을 묻는 것이 아니라 조건을 만족하는 주민의 수를 묻는다.

생활 비유: 명단에서 ‘월 2,500유로 이상 4,000유로 이하인 사람이 몇 명인가?’를 Q번 묻는 상황이다.

\[C_j=\left|\left\{i\mid \ell_j\le S_i\le h_j\right\}\right|\]
\[N=|S|\]
\[Q>N\]

1. 왜 한 번 정렬하는가

정렬되지 않은 배열에서는 어떤 값이 구간에 들어가는지 알아보려면 보통 모든 N개를 확인해야 한다. 한 질의는 \(\Theta(N)\), Q개는 \(\Theta(NQ)\)다.

하지만 S는 변하지 않는다. 한 번 정렬해 둔 비용을 모든 질의가 나눠 부담할 수 있다. Q가 N보다 크므로 비싼 전처리를 한 번 하고 질의를 빠르게 만드는 전략이 특히 유리하다.

정렬 후에는 조건을 만족하는 값들이 배열의 한 연속 구간에 모인다. 따라서 그 구간의 시작 위치와 끝 다음 위치만 찾으면 원소를 직접 세지 않아도 된다.

생활 비유: 뒤섞인 도서관을 질문마다 처음부터 뒤지는 대신, 책을 번호순으로 한 번 정리한 뒤 책장이 시작하고 끝나는 위치만 찾는다.

\[T_{\mathrm{naive}}(N,Q)=\Theta(NQ)\]
\[T_{\mathrm{sort}}(N)=\Theta(N\log N)\]
\[\ell\le A_i\le h\quad\Longrightarrow\quad\text{하나의 연속 구간}\]

2. 일반 이진 탐색(binary search)과 경계 이진 탐색

일반 이진 탐색은 x와 같은 원소 하나를 발견하면 끝날 수 있다. 그러나 중복값이 있으면 그 위치만으로 몇 명인지 알 수 없다.

lowerBound(A,x)는 \(A[i]\ge x\)A[i]≥x인 최초의 인덱스를 돌려준다. upperBound(A,x)는 \(A[i]>x\)A[i]>x인 최초의 인덱스를 돌려준다. 수학적으로는 후보 index 집합에 sentinel N을 함께 넣어 값이 없을 때도 minimum이 정의되게 한다.

둘 다 찾지 못하면 N을 반환한다. N은 실제 원소 인덱스가 아니라 배열의 끝 바로 다음 경계(sentinel position)다.

생활 비유: lowerBound는 입장 가능한 첫 사람의 줄 번호, upperBound는 마지막 입장 가능 사람 바로 뒤의 줄 번호다.

\[L=\min\!\left(\{i:A_i\ge\ell\}\cup\{N\}\right)\]
\[R=\min\!\left(\{i:A_i>h\}\cup\{N\}\right)\]
\[\ell\le h\quad\Longrightarrow\quad C=R-L\]

3. 비교할 원소 [lo,hi)와 정답 경계 [lo,hi]

구현에서 아직 비교할 원소 index는 [lo,hi)로 관리하지만, 찾는 답 자체는 원소 사이의 boundary이므로 닫힌 [lo,hi] 안에 보존한다. \(\text{hi}=N\)hi=N은 비교할 원소가 아니라 배열 끝 boundary다.

처음에는 \(\text{lo}=0, \text{hi}=N\)lo=0, hi=N이다. 반복 중 \(\text{mid}=\text{floor}((\text{lo}+\text{hi})/2)\)mid=floor((lo+hi)/2)를 고르고, 답이 mid보다 오른쪽이면 \(\text{lo}=\text{mid}+1, \text{mid}\)lo=mid+1, mid도 답 후보면 \(\text{hi}=\text{mid}\)hi=mid로 줄인다.

반복은 \(\text{lo}=\text{hi}\)lo=hi가 되면 끝난다. 이때 미해결 원소 구간 [lo,hi)는 비었지만 답 boundary 구간 [lo,hi]에는 그 위치 하나가 남는다.

생활 비유: 가능한 칸의 왼쪽 문은 닫혀 포함되고 오른쪽 문은 열려 제외된 복도를 계속 절반으로 줄인다.

\[\text{아직 비교할 인덱스}=[lo,hi)\]
\[\text{정답 경계}\in[lo,hi]\]
\[mid=\left\lfloor\frac{lo+hi}{2}\right\rfloor\]
\[lo=hi\quad\Longrightarrow\quad\text{탐색 종료}\]
학습 단계 1/5

문제 모델링과 느린 기준 해법

이 소단원의 역할

무엇을 세는지 정확히 정의하고, 왜 단순 반복이 만점 해법이 아닌지 이해한다.

학습 단계 1/5 · 독립 개념 강의

왜 이것을 배우는가

빠른 알고리즘을 쓰기 전에 입력과 출력 조건을 잘못 읽으면 아무리 효율적인 코드도 틀린 답을 낸다. 이 단계는 소득의 합이 아니라 사람 수를 세고, 중복과 양쪽 inclusive 경계를 보존하며, 느리지만 분명한 baseline으로 이후 빠른 해법의 정답을 검산하게 한다.

이 단계를 마친 뒤 할 수 있어야 하는 일

  1. N, Q, S, query [l,h], output C를 실제 작은 입력에 대응시키고 \(l\le S[i]\le h\)l≤S[i]≤h를 말로 설명할 수 있다.
  2. 0-based pseudocode와 원문의 1-based 수학 표기를 혼동하지 않고, 중복 소득을 주민 수만큼 각각 셀 수 있다.
  3. 질의마다 N개를 확인하는 baseline의 정답성과 \(\Theta(NQ)\) 비용을 반복 횟수로 유도할 수 있다.

풀이 전에 꼭 알아야 할 말

array와 index

array는 값을 순서대로 담은 고정 길이 칸들의 열이고 index는 각 칸의 위치 번호다. 이 페이지의 코드는 0부터 시작해 길이 N이면 마지막 index가 N−1이다.

아주 작은 예: \(S=[4,7,4]\)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과 중복

multiset은 같은 값이 여러 번 나타날 수 있고 각 등장 횟수를 보존하는 값 모음이다. 주민 두 명의 소득이 같아도 서로 다른 두 사람이라 둘 다 세어야 한다.

아주 작은 예: \(S=[1800,1800,2500]\)S=[1800,1800,2500]에서 query [1800,1800]의 답은 1이 아니라 2다.

양끝을 포함하는 유효 질의(inclusive valid query)

query [l,h]는 l 이상과 h 이하를 모두 포함한다. 이 페이지는 \(l\le h\)l≤h인 valid query를 입력 전제로 두며, \(l>h\)l>h가 오면 invalid로 보고 0을 반환하거나 거절하는 정책을 별도로 명시한다.

아주 작은 예: [2,5]에는 값 2와 값 5도 포함되지만 [5,2]는 valid closed interval이 아니다.

출입 명단을 질문마다 처음부터 확인하기

시청 직원이 주민 소득 명단을 한 줄씩 들고 있다. 질문 하나가 오면 첫 주민부터 마지막 주민까지 확인하고, 소득이 두 경계 사이면 tally mark를 하나 긋는다. 정확하지만 질문이 많으면 같은 명단을 계속 다시 읽는다.

명단의 한 줄
배열 원소(array element) S[i], 한 주민의 소득
질문 카드의 최소·최대 금액
양끝을 포함하는 질의(inclusive query) [l,h]
조건에 맞을 때 긋는 표시
개수 갱신: count ← count+1
질문마다 명단 전체 재검사
Q번 반복되는 N단계 선형 훑기(linear scan)

비유의 한계: 실제 명단은 이름 등 다른 정보도 있지만 이 문제는 소득값과 조건을 만족하는 원소 개수만 사용하며 주민 신원이나 합계는 출력하지 않는다.

느린 해법의 두 겹 반복

질의(query) 0S[0]부터 S[N−1]까지 N개 검사
질의(query) 1같은 S를 다시 N개 검사
…모든 query에서 동일한 전체 scan 반복
질의(query) Q−1총 조건 비교가 N×Q 수준
바깥 반복은 Q개의 query를 하나씩 선택하고, 안쪽 반복은 같은 S의 N개 원소를 전부 본다. 그래서 검사 횟수는 N+N+…+\(N(Q번)=\text{NQ}\)N(Q번)=NQ다.

작은 예제로 먼저 연습 · \(S=[2,5,2,9]\)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다.

  1. 질의(query) [2,5] 처리

    2,5,2는 \(l\le \text{value}\le h\)l≤value≤h를 만족하고 9는 넘는다. 중복 2 두 개를 각각 센다.

    이 단계 후 상태: \(\text{count}=3, C[0]=3\)count=3, C[0]=3

  2. 질의(query) [6,10] 처리

    2,5,2는 하한보다 작고 9 하나만 포함된다.

    이 단계 후 상태: \(\text{count}=1, C[1]=1\)count=1, C[1]=1

  3. 비용 세기

    query마다 원소 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(NQ)\)이 병목이 된다.

실제 시험 문제로 연결하기

1. 이 문제는 정확히 무엇을 출력하나?

각 query j마다 \(l[j]\le S[i]\le h[j]\)l[j]≤S[i]≤h[j]를 만족하는 index i의 개수 C[j]를 출력한다. 소득값의 합이나 주민 목록이 아니라 count만 반환한다.

2. 복기 원문 \(s_{1}\)s₁…\(s_{N}\)sₙ과 코드 S[0]…S[N−1]은 다른 입력인가?

아니다. 같은 N개 값을 수학 표기는 1부터, 구현 표기는 0부터 번호 붙인 것이다. 값과 순서는 같고 위치 이름만 한 칸씩 다르다.

3. baseline이 왜 올바른가?

각 query에서 모든 원소를 정확히 한 번 검사하고 조건이 참인 경우에만 count를 증가시키므로, 조건을 만족하는 원소를 빠뜨리거나 두 번 세지 않는다.

4. 왜 \(\Theta(\text{NQ})\)Θ(NQ)인가?

바깥 loop가 Q번, 그때마다 안쪽 loop가 정확히 N번 실행된다. 상수 시간 비교·증가를 NQ번 하므로 tight bound가 \(\Theta(NQ)\)다.

이 단계의 핵심 수식

\[\begin{aligned}C_j&=\left|\{i:\ell_j\le S_i\le h_j\}\right|\\[-2pt]&\qquad(0\le i\le N-1)\end{aligned}\]
\[T_{\mathrm{baseline}}(N,Q)=\Theta(NQ)\]
  1. 각 질의 j마다 모든 주민 i를 순회해 \(l[j]\le S[i]\le h[j]\)l[j]≤S[i]≤h[j]이면 count를 1 증가시키면 정답 자체는 맞다. 이 방법은 correctness를 이해하기 위한 baseline이다.
  2. 한 질의에서 N개를 확인하므로 \(\Theta(N)\), Q개는 \(\Theta(NQ)\)다. 문제 설명은 deterministic polynomial-time 알고리즘과 올바른 복잡도만으로 절반 점수는 가능하지만 최대 점수에는 asymptotically optimal한 해법이 필요하다고 말한다.
  3. \(Q>N\)Q>N이라는 힌트와 S가 변하지 않는다는 힌트는 ‘질의마다 같은 일을 반복하지 말고 reusable preprocessing을 하라’는 신호다.

느린 기준 해법을 의사코드로 확인

for j = 0 to Q-1:
    count ← 0
    for i = 0 to N-1:
        if l[j] ≤ S[i] and S[i] ≤ h[j]:
            count ← count + 1
    C[j] ← count
return C
핵심 결론

정답성은 있지만 \(\Theta(NQ)\)이므로 최대 점수용 알고리즘이 아니다.

실제 풀이 후 검산

  • 작은 입력에서는 각 query의 답을 손으로 표시해 baseline C와 비교한다.
  • 중복값과 l 또는 h와 정확히 같은 값이 각각 한 사람으로 포함되는지 확인한다.
  • C의 길이가 Q이고 C[j]가 j번째 query와 같은 순서를 유지하는지 확인한다.

답을 가리고 하는 30초 자가점검

\(S=[1,3,3,8]\)S=[1,3,3,8]에서 [3,3]의 답은?

힌트: 같은 소득 두 사람을 따로 센다.

정답: 3이 두 번 등장하므로 답은 2다.

baseline에서 \(N=5, Q=7\)N=5, Q=7이면 조건을 몇 번 검사하는가?

힌트: 바깥 loop 횟수와 안쪽 loop 횟수를 곱한다.

정답: 각 query마다 5번, 총 7개 query이므로 35번이며 일반식은 \(\Theta(NQ)\)다.

\(l>h \text{query}\)l>h query가 들어오면 이 페이지의 정책은 무엇인가?

힌트: 공식 입력 전제를 먼저 확인한다.

정답: 정상 입력은 \(l\le h\)l≤h를 전제로 한다. 방어적 구현에서는 \(l>h\)l>h를 invalid로 보고 0을 반환하거나 오류 처리한다고 명시한다.

초보자가 자주 틀리는 지점

  • \(Q>N\)Q>N조건을 읽고도 질의마다 S 전체를 선형 탐색한다.
  • 소득의 합을 계산한다. 요구값은 사람 수다.
  • 경계가 inclusive인데 <와 >만 사용해 정확히 l 또는 h인 사람을 뺀다.
학습 단계 2/5

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

이 소단원의 역할

반복 질의를 빠르게 만들기 위해 변하지 않는 데이터를 재사용 가능한 형태로 바꾼다.

학습 단계 2/5 · 독립 개념 강의

왜 이것을 배우는가

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

이 단계를 마친 뒤 할 수 있어야 하는 일

  1. preprocessing의 의미와 한 번 지불한 비용을 Q개 query가 함께 재사용한다는 설계 이유를 설명할 수 있다.
  2. 정렬이 원소 순서는 바꾸지만 중복을 포함한 multiset과 모든 range count를 보존함을 설명할 수 있다.
  3. worst-case \(\Theta(N\log N)\) 정렬을 한 번만 호출하고 query loop 밖에 배치할 수 있다.

풀이 전에 꼭 알아야 할 말

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)\)을 확실히 쓰려면 MergeSort 또는 HeapSort처럼 해당 bound가 보장되는 알고리즘을 명시한다.

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

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

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

개관 전 책 정리
질의 전에 한 번 수행하는 정렬 전처리(sorting preprocessing)
책 번호순 선반
비감소 순서로 정렬된 배열 A(nondecreasing sorted array)
같은 제목 책 여러 권
삭제하면 안 되는 중복 소득값(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]을 생각한다.

  1. 중복집합(multiset) 보존 확인

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

    이 단계 후 상태: S와 A의 value counts 동일

  2. 구간 밖 왼쪽 확인

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

    이 단계 후 상태: indices 0,1 제외

  3. 구간 블록 확인

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

    이 단계 후 상태: answer block \(A[2…3]=[5,7]\)A[2…3]=[5,7]

  4. 구간 밖 오른쪽 확인

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

    이 단계 후 상태: index 4 제외, \(\text{count}=2\)count=2

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

실제 시험 문제로 연결하기

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

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

2. 왜 duplicate를 제거하면 안 되나?

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

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

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

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

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

이 단계의 핵심 수식

\[\begin{aligned}A&=\operatorname{sort}(S)\\\operatorname{multiset}(A)&=\operatorname{multiset}(S)\end{aligned}\]
\[T_{\mathrm{preprocess}}(N)=\Theta(N\log N)\]
  1. S의 복사본 A를 오름차순으로 정렬한다. 원본을 보존할 필요가 없다면 S 자체를 정렬해도 된다. 정렬 알고리즘은 worst-case \(\Theta(N\log N)\)을 보장하는 MergeSort나 HeapSort를 명시하는 것이 안전하다.
  2. 정렬은 주민의 신원 순서를 바꾸지만 이 문제는 소득 조건을 만족하는 ‘수’만 묻는다. 따라서 순서를 바꿔도 답은 변하지 않는다.
  3. 정렬 후 l 이상 h 이하인 모든 값은 하나의 연속 블록을 이룬다. 블록 안에 조건 밖의 값이 끼어들 수 없는 이유는 배열이 오름차순이기 때문이다.

정렬 전과 후를 눈으로 비교

입력 배열 S
42001800250051002500320018004000
정렬된 배열 \(A=\text{sort}(S)\)A=sort(S)
18001800250025003200400042005100
정렬 후 불변 사실

\(A[0]\le A[1]\)A[0]≤A[1]≤…≤A[N−1]이며 A는 원래 S와 동일한 multiset을 가진다.

비용

worst-case \(\Theta(N\log N)\), 복사한다면 추가 \(\Theta(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)\)을 Q번 반복한다.

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

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

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

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

초보자가 자주 틀리는 지점

  • 각 질의 전에 다시 정렬해 \(\Theta(\text{QN} \log N)\)Θ(QN log N)으로 만든다.
  • 평균만 빠른 QuickSort를 아무 설명 없이 worst-case \(\Theta(N\log N)\)이라고 쓴다.
  • 중복값을 제거해 버린다. 중복 주민은 각각 한 명으로 세어야 한다.
  • 정렬하면 답이 달라진다고 생각한다. 이 문제는 원래 위치가 아니라 값의 개수만 필요하다.
학습 단계 3/5

질의 처리: 왼쪽 경계(lowerBound)와 오른쪽 경계(upperBound)를 정확히 구현하기

이 소단원의 역할

inclusive 구간 [l,h]를 두 경계 인덱스의 차이로 바꾼다.

학습 단계 3/5 · 독립 개념 강의

왜 이것을 배우는가

일반 binary search는 같은 값 하나를 찾으면 끝나므로 duplicate의 처음과 끝을 알 수 없다. 이 단계는 원소가 아니라 N+1개의 boundary 위치를 찾고, inclusive [l,h]를 정확히 half-open [L,R)로 바꿔 빈 배열·중복·끝 sentinel까지 같은 코드로 처리한다.

이 단계를 마친 뒤 할 수 있어야 하는 일

  1. lowerBound의 첫 ≥x와 upperBound의 첫 >x를 원소 사이 boundary로 표시하고 차이를 설명할 수 있다.
  2. [lo,hi) invariant를 유지하며 lo, hi, mid, 비교, 버리는 절반을 iteration table에 기록할 수 있다.
  3. duplicate와 inclusive upper endpoint 때문에 upperBound(h)가 필요한 이유를 반례로 설명할 수 있다.
  4. \(N=0, N=1,\)N=0, N=1,모든 값 동일, 값 없음 상황에서 sentinel N과 R−L이 안전하게 동작함을 확인할 수 있다.

풀이 전에 꼭 알아야 할 말

boundary와 sentinel N

N개 원소에는 원소 앞·사이·뒤를 합쳐 N+1개의 boundary 0…N이 있다. N은 마지막 원소 index가 아니라 배열 끝 다음 위치이며 찾는 조건의 원소가 없을 때 반환할 수 있다.

아주 작은 예: \(A=[2,5]\)A=[2,5]의 원소 index는 0,1이고 boundary는 0|2|1|5|2처럼 0,1,2 세 곳이다.

lowerBound와 upperBound

lowerBound(A,x)는 첫 값 ≥x인 boundary, upperBound(A,x)는 첫 값 >x인 boundary다. 둘 다 조건을 만족하는 실제 원소가 없으면 N을 반환하도록 후보에 N을 포함한다.

아주 작은 예: \(A=[2,2,5]\)A=[2,2,5]에서 \(\text{lowerBound}(2)=0, \text{upperBound}(2)=2\)lowerBound(2)=0, upperBound(2)=2라서 2의 개수는 2다.

반열린 구간 [lo,hi) 불변 조건(invariant)

탐색 중 가능한 답 boundary는 닫힌 [lo,hi]에 보존하고, 실제로 비교할 미해결 원소 index만 반열린 [lo,hi)로 다룬다. mid가 답 후보이면 \(\text{hi}=\text{mid}\)hi=mid로 남기고 확실히 왼쪽이면 \(\text{lo}=\text{mid}+1\)lo=mid+1로 버린다.

아주 작은 예: [0,8)에서 \(\text{hi}=4\)hi=4가 되면 indices 4…7을 버리고 답 boundary 4 자체는 여전히 가능하다.

입장 줄의 첫 문과 퇴장 줄의 첫 문

소득순 줄에서 lowerBound는 최소 소득 조건을 처음 통과하는 사람 앞의 문이다. upperBound는 최대 소득을 넘는 첫 사람 앞의 문이다. 두 문 사이에 서 있는 사람 수는 오른쪽 문 번호에서 왼쪽 문 번호를 뺀 값이다.

입장 가능한 첫 사람 앞 문
L은 \(A[i]\ge l\)A[i]≥l인 첫 인덱스(first index)
허용 최대를 넘는 첫 사람 앞 문
R은 \(A[i]>h\)A[i]>h인 첫 인덱스(first index)
두 문 사이 사람들
정답 인덱스 구간 [L,R)
줄 끝 다음 문
더 이상 원소가 없음을 나타내는 특별 경계값(sentinel) N

비유의 한계: 실제 줄에서는 사람이 움직이지만 sorted array는 query 동안 변하지 않는다. boundary 번호는 사람 자체가 아니라 원소 사이 위치라는 점을 유지해야 한다.

배열의 값 칸과 경계(boundary) 칸을 따로 보기

왼쪽 경계(boundary) L첫 \(A[i]\ge l\)A[i]≥l위치, 왼쪽 값은 모두 너무 작다.
A[L…R−1]모든 값이 l 이상 h 이하인 answer block이다.
오른쪽 경계(boundary) R첫 \(A[i]>h\)A[i]>h위치, R 자체 원소는 answer가 아니다.
길이 R−Lhalf-open block의 원소 수를 바로 계산한다.
A의 index는 0…N−1이지만 L과 R은 0…N boundary다. [L,R)에 들어간 값만 세므로 마지막 포함 index를 따로 계산하거나 +1 예외를 둘 필요가 없다.

작은 예제로 먼저 연습 · duplicate 2의 정확한 개수

\(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다.

  1. 왼쪽 경계 lowerBound(A,2) 찾기

    첫 \(A[i]\ge 2\)A[i]≥2는 index 1의 값 2다. 같은 2가 더 있어도 가장 왼쪽 boundary를 찾는다.

    이 단계 후 상태: \(L=1\)L=1

  2. 오른쪽 경계 upperBound(A,2) 찾기

    첫 \(A[i]>2\)A[i]>2는 index 4의 값 5다. A[1],A[2],A[3]의 2를 모두 포함한 뒤 멈춘다.

    이 단계 후 상태: \(R=4\)R=4

  3. 반열린 구간(half-open interval)의 길이 계산

    answer 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를 보존한다.

실제 시험 문제로 연결하기

1. 왜 hi를 N−1이 아니라 N으로 시작하나?

찾는 답은 원소 index뿐 아니라 모든 값 뒤의 boundary N일 수 있다. 답 boundary를 닫힌 [lo,hi]에 보존하고 \(\text{hi}=N\)hi=N을 두면 빈 array와 x가 모든 값보다 큰 경우도 별도 분기 없이 처리한다.

2. lowerBound에서 \(A[\text{mid}]=x\)A[mid]=x이면 왜 즉시 return하지 않나?

duplicate x가 mid보다 왼쪽에 더 있을 수 있다. mid도 답 후보로 남기면서 왼쪽 절반을 계속 보기 위해 \(\text{hi}=\text{mid}\)hi=mid로 줄인다.

3. upperBound의 비교가 왜 ≤인가?

\(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를 찾는다.

4. worked query [2500,4000]의 두 boundary는?

정렬 A에서 첫 ≥2500은 index 2이므로 \(L=2,\)L=2,첫 >4000은 index 6의 4200이므로 \(R=6\)R=6이다. [2,6)의 네 값이 답이다.

\(5. N=0\)5. 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))\)=\(\Theta(1)\)Θ(1)이다.

이 단계의 핵심 수식

\[\begin{aligned}L&=\min\!\left(\{i:A_i\ge\ell\}\cup\{N\}\right)\\R&=\min\!\left(\{i:A_i>h\}\cup\{N\}\right)\end{aligned}\]
\[C=|[L,R)|=R-L\]

왼쪽 경계(lowerBound): 처음으로 x 이상인 위치

lowerBound(A, x):
    lo ← 0
    hi ← length(A)
    while lo < hi:
        mid ← floor((lo + hi) / 2)
        if A[mid] < x:
            lo ← mid + 1
        else:
            hi ← mid
    return lo

오른쪽 경계(upperBound): 처음으로 x보다 큰 위치

upperBound(A, x):
    lo ← 0
    hi ← length(A)
    while lo < hi:
        mid ← floor((lo + hi) / 2)
        if A[mid] ≤ x:
            lo ← mid + 1
        else:
            hi ← mid
    return lo

두 코드의 단 한 글자 차이

  1. lowerBound에서는 \(A[\text{mid}]<x\)A[mid]<x일 때만 mid를 버리고 오른쪽으로 간다. \(A[\text{mid}]=x\)A[mid]=x이면 첫 x가 더 왼쪽일 수 있으므로 \(\text{hi}=\text{mid}\)hi=mid다.
  2. upperBound에서는 \(A[\text{mid}]\le x\)A[mid]≤x이면 mid까지 모두 답 경계의 왼쪽이므로 \(\text{lo}=\text{mid}+1\)lo=mid+1이다. 이것이 h와 같은 값들을 모두 포함시키는 핵심이다.
  3. 두 함수의 코드는 비교 연산 하나만 다르지만 그 한 글자가 inclusive upper endpoint를 정확히 처리한다.

배열의 값 칸과 경계(boundary)를 분리해 보기

대표 질의 [2500,4000]을 손으로 끝까지

정렬된 A
18001800250025003200400042005100

왼쪽 경계 추적: \(L=\text{lowerBound}(A,2500)\)L=lowerBound(A,2500)

  1. 초기 \([\text{lo},\text{hi})=[0,8), \text{mid}=4, A[4]=3200. 3200<2500\)[lo,hi)=[0,8), mid=4, A[4]=3200. 3200<2500은 거짓 → \(\text{hi}=4.\)hi=4.
  2. \([0,4), \text{mid}=2, A[2]=2500. 2500<2500\)[0,4), mid=2, A[2]=2500. 2500<2500은 거짓 → \(\text{hi}=2.\)hi=2.
  3. \([0,2), \text{mid}=1, A[1]=1800. 1800<2500\)[0,2), mid=1, A[1]=1800. 1800<2500은 참 → \(\text{lo}=2.\)lo=2.
  4. \(\text{lo}=\text{hi}=2\)lo=hi=2이므로 \(L=2.\)L=2.인덱스 2가 첫 2500이다.

오른쪽 경계 추적: \(R=\text{upperBound}(A,4000)\)R=upperBound(A,4000)

  1. 초기 \([0,8), \text{mid}=4, A[4]=3200. 3200\le 4000 \to \text{lo}=5.\)[0,8), mid=4, A[4]=3200. 3200≤4000 → lo=5.
  2. \([5,8), \text{mid}=6, A[6]=4200. 4200\le 4000\)[5,8), mid=6, A[6]=4200. 4200≤4000은 거짓 → \(\text{hi}=6.\)hi=6.
  3. \([5,6), \text{mid}=5, A[5]=4000. 4000\le 4000 \to \text{lo}=6.\)[5,6), mid=5, A[5]=4000. 4000≤4000 → lo=6.
  4. \(\text{lo}=\text{hi}=6\)lo=hi=6이므로 \(R=6.\)R=6.인덱스 6은 첫 4000 초과 값 4200이다.

lowerBound(A,2500) 실행표

회차항목 (lo)항목 (hi)항목 (mid)항목 (A[mid])비교갱신남은 경계(boundary) 후보
10843200\(3200<2500 = \text{false}\)3200<2500 = falsehi←4[0,4] boundary
20422500\(2500<2500 = \text{false}\)2500<2500 = falsehi←2[0,2] boundary
30211800\(1800<2500 = \text{true}\)1800<2500 = truelo←2boundary 2
422——\(\text{lo}=\text{hi}\)lo=hireturn 2\(L=2\)L=2

upperBound(A,4000) 실행표

회차항목 (lo)항목 (hi)항목 (mid)항목 (A[mid])비교갱신남은 경계(boundary) 후보
10843200\(3200\le 4000 = \text{true}\)3200≤4000 = truelo←5[5,8] boundary
25864200\(4200\le 4000 = \text{false}\)4200≤4000 = falsehi←6[5,6] boundary
35654000\(4000\le 4000 = \text{true}\)4000≤4000 = truelo←6boundary 6
466——\(\text{lo}=\text{hi}\)lo=hireturn 6\(R=6\)R=6
계산

\(C=R\)C=R−\(L=6\)L=6−\(2=4.\)2=4.인덱스 2,3,4,5의 [2500,2500,3200,4000] 네 명이다.

일반 경계 질의 검산

질의두 경계계산 결과배울 점
[1800,1800]\(L=0, R=2\)L=0, R=22중복된 경계값 두 개를 모두 센다.
[1900,2400]\(L=2, R=2\)L=2, R=20값이 하나도 없으면 두 경계가 같아 음수가 아닌 0이 된다.
[0,1000]\(L=0, R=0\)L=0, R=00모든 값보다 작은 구간도 처리된다.
[6000,9000]\(L=8, R=8\)L=8, R=80경계 함수가 N을 반환해도 안전하다.
[1800,5100]\(L=0, R=8\)L=0, R=88전체 배열을 포함한다.

빈 배열·한 원소·중복·잘못된 입력까지

정렬된 배열 A질의(query)경계 L, R개수왜 중요한가
[][1,2]\(L=0, R=0\)L=0, R=00\(N=0\)N=0이면 loop를 한 번도 돌지 않고 sentinel 0을 반환한다.
[7][7,7]\(L=0, R=1\)L=0, R=11\(N=1\)N=1에서도 같은 코드로 유일한 값을 센다.
[4, 4, 4][4,4]\(L=0, R=3\)L=0, R=33모든 값이 같아도 duplicate 전체를 센다.
[1, 4, 4, 9][3,8]\(L=1, R=3\)L=1, R=32endpoint 값 3과 8이 없어도 내부의 4 두 개를 센다.
[1, 2, 3][5,2]invalid0이 페이지는 \(l\le h\)l≤h를 입력 전제로 둔다. 방어적 정책에서는 \(l>h\)l>h를 0 또는 error로 처리하며 R−L을 그대로 계산하지 않는다.
질의 비용

\(N=0\)N=0까지 포함한 helper의 tight bound는 \(\Theta(\log(N+2))\)이다. 시험의 통상 전제 \(N\ge 2\)N≥2에서는 각 helper와 한 query가 \(\Theta(\log N)\)이다.

실제 풀이 후 검산

  • \(L=0\)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\)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인지 확인한다.
  • 각 iteration에서 hi−lo가 엄격히 줄고 \(\text{lo}=\text{hi}\)lo=hi에서 종료하는지 structured trace를 확인한다.
  • 같은 예제를 직접 scan한 count와 R−L이 일치하는지 비교한다.

답을 가리고 하는 30초 자가점검

\(A=[1,2,2,5]\)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이다.

upperBound에서 비교를 \(A[\text{mid}]<x\)A[mid]<x로 쓰면 어떤 값이 빠지나?

힌트: \(A[\text{mid}]=x\)A[mid]=x일 때 어느 방향으로 가는지 본다.

정답: x와 같은 값들을 오른쪽 boundary 전에 모두 포함하지 못해 inclusive upper endpoint h의 duplicate가 빠질 수 있다.

연습: \(A=[1,4,4,4,9]\)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]을 센다.

초보자가 자주 틀리는 지점

  • 일반 binary search로 l과 h의 임의 위치 하나씩을 찾는다. 중복값에서 오답이다.
  • upperBound를 첫 \(A[i]\ge h\)A[i]≥h로 정의해 h와 같은 사람들을 제외한다.
  • 마지막 포함 인덱스를 찾아 R−L+1을 쓰다가 빈 구간과 끝 경계에서 복잡한 예외를 만든다.
  • hi=N−1로 시작하면서 [lo,hi) 불변식을 섞는다.
  • \(A[\text{mid}]=x\)A[mid]=x일 때 즉시 return하여 첫 위치를 보장하지 못한다.
학습 단계 4/5

전체 알고리즘과 정확성 증명

이 소단원의 역할

코드를 합치고, 왜 R−L이 정확히 원하는 사람 수인지 논리적으로 설명한다.

학습 단계 4/5 · 독립 개념 강의

왜 이것을 배우는가

시험에서는 코드를 적는 것만으로 최대 점수를 보장하지 않는다. 정렬이 답을 보존하고, 두 boundary가 answer block의 바깥을 정확히 잘라 내며, [L,R)의 길이가 R−L이라는 논리 사슬을 제시해야 구현과 정답성 사이의 빈틈을 닫을 수 있다.

이 단계를 마친 뒤 할 수 있어야 하는 일

  1. copy/sort 한 번과 Q개의 두 boundary search를 하나의 전체 pseudocode로 연결할 수 있다.
  2. 정렬 보존, 왼쪽 제외, 가운데 포함, 오른쪽 제외, 개수라는 다섯 claim으로 correctness를 증명할 수 있다.
  3. 여러 query의 답을 원래 query 순서대로 C에 저장하는 완전한 입력→출력 예제를 재현할 수 있다.

풀이 전에 꼭 알아야 할 말

정확성 증명(correctness proof)

몇 개 예제가 맞는 것을 넘어 모든 valid input에서 알고리즘 출력이 명세와 같음을 논리적으로 보이는 설명이다. 각 코드 단계가 유지하는 사실과 종료 시 결론을 연결한다.

아주 작은 예: 정렬 후 \(i<L\)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 invariant)

loop 시작과 반복 뒤에도 계속 참인 사실이다. binary search에서는 답 boundary가 후보 안에 남고 확정적으로 작은 또는 큰 구역이 후보 밖에 쌓인다는 사실을 쓴다.

아주 작은 예: lowerBound에서 모든 \(i<\text{lo}\)i<lo는 \(A[i]<x\)A[i]<x이고 모든 \(i\ge \text{hi}\)i≥hi는 \(A[i]\ge x\)A[i]≥x다.

종료성(termination)

알고리즘이 무한히 돌지 않고 끝남을 보이는 성질이다. 각 binary-search iteration에서 hi−lo가 엄격히 줄고 음수가 될 수 없으므로 \(\text{lo}=\text{hi}\)lo=hi에 도달한다.

아주 작은 예: 미해결 원소 구간의 길이 hi−lo가 \(8\to 4\to 2\to 1\to 0\)8→4→2→1→0으로 감소한다. 길이 0일 때 답 boundary 하나 \(\text{lo}=\text{hi}\)lo=hi가 확정된다.

창고에서 허용 구역을 두 안전문으로 봉인하기

정렬된 창고 선반에서 왼쪽 안전문 L은 너무 싼 물건을 모두 밖에 두고, 오른쪽 안전문 R은 너무 비싼 첫 물건 앞에서 닫힌다. 두 문 사이 선반만 허용 구역이며 어느 물건도 빠지거나 섞이지 않았음을 문별로 증명한다.

정렬된 창고 선반
S와 같은 중복집합을 가진 비감소 배열 A
왼쪽 안전문 L
\(A[i]\ge l\)A[i]≥l인 첫 인덱스
오른쪽 안전문 R
\(A[i]>h\)A[i]>h인 첫 인덱스
두 문 사이 선반 수
반열린 구간의 길이 R−L

비유의 한계: 안전문 비유는 이미 정렬된 array를 전제로 한다. 정렬 보존을 먼저 증명하지 않으면 원본 S의 answer와 연결되지 않는다.

정확성 증명의 다섯 고리

1. multiset 보존A는 S의 값과 등장 횟수가 같다.
\(2. i<L\)2. i<L제외모든 왼쪽 값은 l보다 작다.
\(3. L\le i<R\)3. L≤i<R포함각 값이 l 이상 h 이하다.
\(4. i\ge R\)4. i≥R제외모든 오른쪽 값은 h보다 크다.
5. 길이정확한 answer indices [L,R)의 수는 R−L이다.
어느 한 고리도 생략하지 않는다. 특히 정렬이 같은 multiset을 보존한다는 첫 고리가 있어야 sorted A에서 센 결과가 원본 S의 주민 수와 같아진다.

작은 예제로 먼저 연습 · 세 query를 끝까지 출력하기

\(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]를 한 번 만든다.

  1. 질의(query) [2,5]

    첫 ≥2는 \(L=1,\)L=1,첫 >5는 \(R=4\)R=4라 indices 1,2,3의 2,2,5를 센다.

    이 단계 후 상태: \(C[0]=4−1=3\)C[0]=4−1=3

  2. 질의(query) [0,1]

    첫 ≥0은 \(L=0,\)L=0,첫 >1은 \(R=1\)R=1이라 값 1 하나를 센다.

    이 단계 후 상태: \(C[1]=1−0=1\)C[1]=1−0=1

  3. 질의(query) [6,8]

    첫 ≥6과 첫 >8이 모두 index 4의 값 9 앞 boundary다.

    이 단계 후 상태: \(C[2]=4−4=0\)C[2]=4−4=0

  4. 순서대로 반환

    각 결과를 같은 j 위치에 저장했으므로 query order가 보존된다.

    이 단계 후 상태: \(C=[3,1,0]\)C=[3,1,0]

작은 예제의 결론: 정렬은 한 번뿐이고 세 query는 같은 A를 사용한다. 손으로 scan한 답과 \(C=[3,1,0]\)C=[3,1,0]이 일치한다.

실제 시험 문제로 연결하기

1. 정렬이 왜 원래 문제의 답을 보존하나?

A는 S의 permutation이라 각 소득값의 등장 횟수가 같다. query는 위치가 아니라 값이 범위에 드는 원소 수만 묻기 때문에 어느 order에서 세어도 count가 같다.

2. 왜 \(i<L\)i<L인 값은 전부 제외되나?

L은 첫 \(A[i]\ge l\)A[i]≥l위치다. sorted array에서 그보다 왼쪽 index는 모두 l보다 작으므로 lower condition을 만족하지 못한다.

3. 왜 \(L\le i<R\)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다.

4. 왜 \(i\ge R\)i≥R인 값은 전부 제외되나?

R부터 첫 값이 h보다 크고 array가 nondecreasing이므로 그 오른쪽 값도 모두 h보다 크다.

5. 왜 개수에 +1을 하지 않나?

R은 마지막 포함 index가 아니라 첫 제외 boundary다. half-open indices L,L+1,…,R−1의 개수는 정확히 R−L이고 empty block도 0이 된다.

이 단계의 핵심 수식

\[\begin{aligned}\mathopen{[}0,N)&=[0,L)\;\dot\cup\;[L,R)\\&\quad\dot\cup\;[R,N)\end{aligned}\]
\[i\in[L,R)\iff \ell\le A_i\le h\]

전체 의사코드(pseudocode)

IncomeStatistics(S, queries):
    A ← copy(S)
    MergeSort(A)
    C ← new array of length Q
    for j = 0 to Q-1:
        l ← queries[j].lower
        h ← queries[j].upper
        L ← lowerBound(A, l)
        R ← upperBound(A, h)
        C[j] ← R - L
    return C

한 번 정렬한 배열로 여러 질의(query) 처리

입력 S
42001800250051002500320018004000
한 번 만든 \(A=\text{sort}(S)\)A=sort(S)
18001800250025003200400042005100
질의 번호 j질의(query)왼쪽 경계 L오른쪽 경계 R수식·상태: \(C[j]=R−L\)C[j]=R−L세어진 값
0[2500,4000]264[2500, 2500, 3200, 4000]
1[1800,1800]022[1800, 1800]
2[1900,2400]220[]
3[6000,9000]880[]
최종 출력 벡터(output vector) C[4, 2, 0, 0]

A는 한 번만 정렬하고 모든 query가 재사용한다. C[j]는 j번째 query의 R−L을 같은 순서로 저장한다.

정확성 증명: 다섯 문장 사슬

1. 정렬은 답을 보존한다.

A는 S의 원소들을 순서만 바꾼 같은 multiset이다. 각 소득값의 등장 횟수가 같으므로 어떤 값 구간에 속하는 주민 수도 같다.

2. L보다 왼쪽에는 답이 없다.

\(L=\text{lowerBound}(A,l)\)L=lowerBound(A,l)는 첫 \(A[i]\ge l\)A[i]≥l위치다. 따라서 모든 \(i<L\)i<L에 대해 \(A[i]<l\)A[i]<l이라서 구간 조건을 만족하지 않는다.

3. L부터 R−1까지는 모두 답이다.

\(i\ge L\)i≥L이면 \(A[i]\ge l\)A[i]≥l이다. \(R=\text{upperBound}(A,h)\)R=upperBound(A,h)는 첫 \(A[i]>h\)A[i]>h위치이므로 \(i<R\)i<R이면 \(A[i]\le h\)A[i]≤h다. 따라서 \(L\le i<R\)L≤i<R인 모든 값은 \(l\le A[i]\le h\)l≤A[i]≤h다.

4. R부터 오른쪽에는 답이 없다.

R의 정의와 정렬성 때문에 모든 \(i\ge R\)i≥R에 대해 \(A[i]>h\)A[i]>h다.

5. 따라서 개수는 R−L이다.

조건을 만족하는 인덱스 집합은 정확히 {L,L+1,…,R−1}이고 반열린 구간 [L,R)의 원소 수는 R−L이다.

경계 탐색의 반복 불변식(loop invariant)과 종료

  • lowerBound 반복 중 정답 위치는 항상 [lo,hi] 경계 안에 남아 있다. lo보다 왼쪽 값은 모두 x보다 작고, hi부터 오른쪽 값은 모두 x 이상이다.
  • upperBound 반복 중 lo보다 왼쪽 값은 모두 x 이하이고, hi부터 오른쪽 값은 모두 x보다 크다.
  • 매 반복마다 hi−lo가 엄격히 줄어들므로 두 함수는 종료한다.

실제 풀이 후 검산

  • 각 query마다 \(\text{three}-\text{zone} \text{partition} i<L, L\le i<R, i\ge R\)three-zone partition i<L, L≤i<R, i≥R가 모든 index를 겹침 없이 덮는지 확인한다.
  • multi-query 예제 C의 각 위치가 원래 query 순서와 맞고 손 scan count와 같은지 확인한다.
  • lower/upper loop invariant와 hi−lo 감소가 초기화·유지·종료 세 단계에서 모두 설명되는지 확인한다.

답을 가리고 하는 30초 자가점검

R을 마지막 ≤h index로 정의하면 어떤 추가 문제가 생기나?

힌트: empty answer와 끝 sentinel에서 +1 공식을 생각한다.

정답: R−L+1과 별도 not-found 처리가 필요해 empty/end case가 복잡해진다. 첫 >h boundary가 더 일관된다.

\(A=[1,2,4]\)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다.

증명에서 multiset 보존을 생략하면 무엇이 비나?

힌트: sorted A의 count와 원본 S의 count를 연결해야 한다.

정답: A에서 올바르게 세었다는 사실이 원본 S의 주민 수와 같다는 첫 논리 연결이 사라진다.

초보자가 자주 틀리는 지점

  • pseudocode만 쓰고 correctness 설명을 전혀 하지 않는다.
  • R−L 공식을 제시하지만 L과 R의 정의를 쓰지 않는다.
  • 정렬 후 원소의 개수가 보존된다는 첫 단계를 생략한다.
  • helper를 호출만 하고 helper의 pseudocode 또는 강의에서 배운 어떤 binary search 변형인지 명확히 하지 않는다.
학습 단계 5/5

시간복잡도, 공간복잡도, 그리고 왜 이 설계가 좋은가

이 소단원의 역할

전처리와 Q개 질의를 분리해 전체 점근 복잡도를 정확히 합산한다.

학습 단계 5/5 · 독립 개념 강의

왜 이것을 배우는가

이 문제는 올바른 polynomial algorithm만으로 일부 점수, asymptotically optimal한 algorithm과 helper 비용까지 설명해야 최대 점수를 준다고 명시한다. 따라서 정렬·query·출력 비용을 빠짐없이 더하고, \(Q>N\)Q>N을 이용한 단순화와 comparison-model 하한의 적용 범위를 구분해야 한다.

이 단계를 마친 뒤 할 수 있어야 하는 일

  1. 전처리 \(\Theta(N\log N)\), query당 \(\Theta(\log N)\), Q개 \(\Theta(Q\log N)\)을 합쳐 전체식을 유도할 수 있다.
  2. \(Q>N\)Q>N조건 아래 \(\Theta(N\log N+Q\log N)\)=\(\Theta(Q\log N)\)으로 올바르게 단순화하면서 유도 과정의 전처리 항을 설명할 수 있다.
  3. \(N=0\)N=0을 포함한 구현 bound \(\Theta(\log(N+2))\)와 시험 관례 \(N\ge 2\)N≥2의 \(\Theta(\log N)\)을 구분할 수 있다.
  4. comparison model에서 왜 Q개 독립 range count에 \(\Omega(Q\log N)\) 정보가 필요한지 설명하고 integer-universe 추가 가정의 한계를 표시할 수 있다.

풀이 전에 꼭 알아야 할 말

점근 복잡도 표기(O, Ω, Θ)

O는 asymptotic upper bound, Ω는 lower bound, Θ는 둘이 일치하는 tight bound다. 알고리즘이 빠르다는 상한과 어떤 알고리즘도 피할 수 없다는 하한을 구분해야 optimality를 말할 수 있다.

아주 작은 예: binary search는 \(O(\log N)\)O(log N)이면서 \(\Omega(\log N)\)Ω(log N) worst-case comparisons가 필요해 \(\Theta(\log N)\)이다.

비교 모델(comparison model)

소득과 query endpoint의 순서 정보가 <,≤,> 같은 비교 결과를 통해서만 얻어진다고 보는 계산 모델이다. 정수의 bit 구조나 작은 universe를 공짜로 이용하지 않는다.

아주 작은 예: 한 비교는 yes/no 정도의 상수 개 결과만 주며 rank 0…N 중 하나를 찾으려면 log(N+1) 정보가 필요하다.

점근적으로 최적(asymptotically optimal)

같은 model에서 알고리즘 upper bound와 문제 lower bound가 상수배까지 일치하는 상태다. 단지 다른 알려진 방법보다 빨라 보인다는 뜻이 아니다.

아주 작은 예: \(Q>N\)Q>N에서 algorithm \(\Theta(Q\log N)\)과 comparison lower bound \(\Omega(Q\log N)\)이 맞아 optimal하다.

초기 정리 비용과 질문당 안내 비용을 영수증으로 분리하기

도서관 영수증에는 개관 전 전체 정리 비용 한 줄과 방문자 Q명에게 선반 두 곳을 안내한 비용 Q줄이 따로 있다. 총액을 먼저 모두 더한 뒤 방문자가 책보다 많다는 \(Q>N\)Q>N조건으로 어느 항이 지배적인지 단순화한다.

개관 전 한 번의 정리 비용
정렬 전처리(sorting preprocessing) \(\Theta(N \log N)\)Θ(N log N)
방문자 한 명의 두 boundary 안내
질의 하나의 두 경계 탐색(searches) \(\Theta(\log N)\)Θ(log N)
Q명 안내 총액
\(\Theta(Q \log N)\)Θ(Q log N)
같은 서비스를 위해 필요한 최소 정보
비교 모델의 하한(comparison-model lower bound) \(\Omega(Q \log N)\)Ω(Q log N)

비유의 한계: 영수증 비유는 단순 합산을 보여 줄 뿐 lower bound를 증명하지 않는다. optimality에는 어떤 comparison algorithm도 출력 조합을 구분해야 한다는 별도 정보 논증이 필요하다.

전체 실행 시간(runtime) 식을 조립하고 단순화하기

복사 후 정렬(copy + sort)\(\Theta(N)\)+\(\Theta(N\log N)\)=\(\Theta(N\log N)\)
질의 하나(one query)\(2\cdot \(\Theta(\log N)\)+\Theta(1)=\(\Theta(\log N)\)\)2·\(\Theta(\log N)\)+Θ(1)=\(\Theta(\log N)\)
Q개 질의(queries)Q·\(\Theta(\log N)\)=\(\Theta(Q\log N)\)
전체 시간 합계(full total)\(\Theta(N\log N+Q\log N)\)
조건 \(Q>N\)Q>N적용\(\Theta(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)\)이지만, preprocessing을 실제로 하지 않았다는 뜻은 아니다.

작은 예제로 먼저 연습 · \(N=8, Q=20\)N=8, Q=20의 비용 항 읽기

정확한 machine step 수가 아니라 성장 항을 비교한다. \(\log_{2}8=3\)log₂8=3이고 \(Q>N\)Q>N이다.

  1. 정렬 항 계산

    \(N \log_{2}N\)N log₂N은 8×\(3=24\)3=24규모이며 query 전에 한 번 든다.

    이 단계 후 상태: preprocess scale≈24

  2. 질의(query) 항 계산

    query당 두 binary search가 상수 2를 제외하면 log N 규모이고 Q번 반복된다.

    이 단계 후 상태: query scale≈20×\(3=60\)3=60

  3. 합과 단순화

    24+60을 모두 유도한 뒤 \(N<Q\)N<Q라 N log N 항이 Q log N보다 크지 않음을 사용한다.

    이 단계 후 상태: \(\Theta(N\log N+Q\log N)\)=\(\Theta(Q\log N)\)

  4. 공간 분리

    copy A는 \(\Theta(N)\), output C는 \(\Theta(Q)\)이며 output은 반드시 써야 한다.

    이 단계 후 상태: auxiliary \(\Theta(N)\), output \(\Theta(Q)\)

작은 예제의 결론: 전처리 항을 유도에서 보여 주면서도 최종 tight bound를 \(\Theta(Q\log N)\)으로 단순화하는 두 문장은 서로 모순이 아니다.

실제 시험 문제로 연결하기

1. 전체 시간을 왜 \(O(N \log N)\)O(N log N)이라고만 쓰면 안 되나?

Q개 query 각각의 두 boundary search 비용을 누락하기 때문이다. Q가 N보다 크므로 오히려 \(\Theta(Q\log N)\) query 항이 전체를 지배한다.

\(2. Q>N\)2. Q>N에서 \(\Theta(Q \log N)\)Θ(Q log N)만 쓰는 것이 수학적으로 틀린가?

아니다. full derivation은 \(\Theta(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)\)으로 단순화할 수 있다. 시험 답안에는 두 단계를 함께 쓰는 것이 가장 명확하다.

\(3. N=0\)3. 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))\)로 쓴다. 시험의 보통 분석은 \(N\ge 2\)N≥2를 전제로 \(\Theta(\log N)\)을 쓴다.

4. comparison model에서 왜 query당 log N이 자연스러운 하한인가?

서로 다른 N개 값으로 된 hard-instance sorted S를 고정하면 prefix형 query 하나의 count가 0…N 중 어느 값도 될 수 있다. Q개가 독립이면 \((N+1)^Q\)개의 output vector를 비교 결과로 구분해야 하므로 \(\Omega\!\left(\log((N+1)^Q)\right)=\Omega\!\left(Q\log(N+1)\right)\) comparisons가 필요하다.

5. 정수 입력인데 counting array가 항상 더 빠르지 않은 이유는?

소득 universe 최대값 M이나 bit/digit bound가 주어지지 않았다. counting/radix 방법의 시간·공간은 M 또는 digit 수에도 의존하므로 comparison-model 최적성 주장과 별도 가정이 필요하다.

이 단계의 핵심 수식

\[\begin{aligned}T(N,Q)&=\Theta(N\log N)+Q\cdot\Theta(\log N)\\&=\Theta(N\log N+Q\log N)\end{aligned}\]
\[Q>N\quad\Longrightarrow\quad T(N,Q)=\Theta(Q\log N)\]
\[S_{\mathrm{work}}=\Theta(N),\qquad S_{\mathrm{output}}=\Theta(Q)\]

항목별로 복잡도 더하기

  1. 복사: \(\Theta(N)\). 정렬: \(\Theta(N\log N)\).
  2. \(N\ge 2\)N≥2인 시험 관례에서 각 질의: lowerBound \(\Theta(\log N)\)+upperBound \(\Theta(\log N)\)+상수 뺄셈 \(\Theta(1)\)Θ(1)=\(\Theta(\log N)\). \(N=0\)N=0까지 포괄하는 tight bound는 \(\Theta(\log(N+2))\)이다.
  3. Q개 질의: \(N\ge 2\)N≥2에서 \(\Theta(Q\log N)\). 결과 배열 C를 쓰는 데도 \(\Omega(Q)\)Ω(Q)가 필요하며 이 항은 \(\Theta(Q\log N)\)에 포함된다.
  4. 전체: \(\Theta(N \log N + Q \log N)\)Θ(N log N + Q log N). 같은 식을 \(\Theta((N+Q)\log N)\)Θ((N+Q)log N)이라고 써도 된다.
  5. 문제 조건 \(Q>N\)Q>N을 적용하면 \(N \log N<Q \log N\)N log N<Q log N이므로 전체를 \(\Theta(Q\log N)\)으로 올바르게 단순화할 수 있다. 답안에는 full derivation과 조건 적용 후 단순화를 둘 다 쓰면 가장 명확하다.

다른 접근과 비교

방법전처리질의당전체판정
질의마다 선형 스캔없음\(\Theta(N)\)\(\Theta(NQ)\)정확하지만 최대 점수용 아님
매번 다시 정렬질의마다 \(\Theta(N\log N)\)추가 탐색\(\Theta(\text{QN} \log N)\)Θ(QN log N)전처리 재사용 실패
한 번 정렬 + 두 경계 검색\(\Theta(N\log N)\)\(\Theta(\log N)\)\(\Theta(N\log N+Q\log N)\)권장 답안
균형 BST에 빈도·subtree size 저장\(\Theta(N\log N)\)\(\Theta(\log N)\)\(\Theta(N\log N+Q\log N)\)가능하지만 설명이 더 복잡

공간복잡도

  • A를 별도 복사하고 MergeSort auxiliary array를 사용하면 working space는 \(\Theta(N)\), 결과 C는 \(\Theta(Q)\)다.
  • 입력 S를 in-place HeapSort하면 정렬용 추가 공간을 줄일 수 있지만 결과 C의 \(\Theta(Q)\)는 필요하다.
  • 시험에서 공간복잡도를 요구하지 않아도 한 줄 언급하면 설계가 완결된다.

최적성 설명

  • 비교 기반 모델에서 MergeSort로 정렬 전처리를 \(\Theta(N\log N)\)에 구현하고 각 query를 \(\Theta(\log N)\)에 처리할 수 있다.
  • 서로 다른 N개 값을 가진 hard-instance sorted S를 고정하면 prefix형 query 하나의 count는 0,…,N 중 어느 값도 가능하다. Q개 독립 query는 \((N+1)^Q\)개 output vector를 만들 수 있으므로 이를 비교 결과로 구분하려면 \(\Omega\!\left(\log((N+1)^Q)\right)=\Omega\!\left(Q\log(N+1)\right)\) comparisons가 필요하다.
  • \(N\ge 2, Q>N\)N≥2, Q>N에서 알고리즘의 \(\Theta(Q\log N)\)과 이 comparison lower bound가 일치하므로 comparison model에서 asymptotically optimal하다. 이 lower-bound 적용은 강의 개념에서 유도한 일반 알고리즘 지식이다.
  • 소득값 universe나 word/digit bound가 작다는 추가 가정이 없으므로 counting array나 radix/predecessor 구조가 항상 더 빠르다고 주장하면 안 된다. 다른 계산 model에서는 bound가 달라질 수 있다.

시험 답안 템플릿

valid query lⱼ≤hⱼ를 전제로 S를 worst-case \(\Theta(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)\), 전체는 \(\Theta(N\log N+Q\log N)\)이며 \(Q>N\)Q>N이므로 \(\Theta(Q\log N)\)으로 단순화할 수 있다. 이는 comparison model에서 \(\Omega(Q\log N)\) lower bound와 맞는다. 결과 공간은 \(\Theta(Q)\), 정렬 복사본은 추가 \(\Theta(N)\)이다.

실제 풀이 후 검산

  • 정렬, helper 두 개, Q loop, output write의 비용이 모두 total 식에 포함됐는지 확인한다.
  • full derivation과 \(Q>N\)Q>N단순화를 서로 다른 줄에 써 수학적 등가와 구현 단계를 함께 보인다.
  • optimal이라는 단어 앞에 comparison model과 \(N\ge 2\)N≥2또는 log(N+2) convention을 명시한다.
  • 공간에서 working copy \(\Theta(N)\)과 반드시 반환할 output \(\Theta(Q)\)를 구분한다.

답을 가리고 하는 30초 자가점검

Q가 N보다 클 때 전체 tight runtime을 두 형태로 쓰라.

힌트: 먼저 모든 항을 쓰고 지배 항으로 단순화한다.

정답: \(\Theta(N\log N+Q\log N)\)이며 \(Q>N\)Q>N조건 아래 \(\Theta(Q\log N)\)으로 단순화할 수 있다.

왜 ‘optimal’에 comparison model이라는 조건이 필요한가?

힌트: integer range나 word operation을 추가로 이용하는 algorithm을 생각한다.

정답: 작은 bounded universe 같은 추가 구조가 있으면 counting/radix/predecessor 방법의 bound가 달라질 수 있어 비교만 허용한 lower bound가 자동 적용되지 않기 때문이다.

결과 C를 제외한 working space와 output space는?

힌트: A 복사본과 Q개 답을 따로 센다.

정답: MergeSort용 A와 보조 배열 기준 working \(\Theta(N)\), 반환 output C는 \(\Theta(Q)\)다.

초보자가 자주 틀리는 지점

  • 전체를 \(O(N \log N)\)O(N log N)이라고만 쓰고 Q개 질의 비용을 누락한다.
  • 두 번의 binary search라서 \(O(2 \log N)\)O(2 log N)이라고 끝낸다. 상수를 제거하면 \(\Theta(\log N)\)이다.
  • \(\Theta(Q\log N)\) 단순화만 쓰고 정렬 \(\Theta(N\log N)\)과 Q개 query \(\Theta(Q\log N)\)을 어떻게 합했는지 유도 과정을 전혀 보여주지 않는다.
  • 정수라는 이유만으로 소득 최대값 M 크기의 counting array를 제안한다. M에 대한 제한이 없으므로 공간과 시간이 최적이라는 보장이 없다.
  • 평균 복잡도와 worst-case 복잡도를 섞는다.

답을 가리고 하는 전체 회상 연습

답을 펼치기 전에 말로 먼저 설명해 보세요.

왜 lowerBound(h)가 아니라 upperBound(h)를 써야 하는가?

h와 같은 소득도 포함해야 하므로 첫 >h 위치를 찾아야 한다.

조건을 만족하는 값이 하나도 없으면 왜 R−L이 안전한가?

두 경계가 같은 삽입 위치를 가리켜 0이 된다.

일반 binary search가 중복값에서 부족한 이유는?

같은 값 중 임의의 하나만 찾아 최초·마지막 경계를 알 수 없기 때문이다.

\(Q>N\)Q>N은 어떤 설계 힌트인가?

변하지 않는 S를 한 번 전처리하고 그 비용을 많은 질의에 나눠 부담하라는 뜻이다.

전체 시간복잡도는?

full derivation은 \(\Theta(N\log N+Q\log N)\)이고, \(Q>N\)Q>N조건 아래 \(\Theta(Q\log N)\)으로 단순화할 수 있다.

\(N=0\)N=0까지 포함하면 query helper의 tight bound를 어떻게 쓰나?

\(\Theta(\log(N+2))\)로 쓰면 빈 배열의 상수 초기 검사까지 포함한다. 시험 관례 \(N\ge 2\)N≥2에서는 \(\Theta(\log N)\)이다.

근거와 정확성 범위

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