독일어 원문 제목: 3. Sortieralgorithmen (10 Punkte)

3번 · 정렬 알고리즘과 반복 불변식(Loop Invariant)

완전 초보자를 위한 문제 해석 → 개념 이해 → 단계별 풀이 → 증명 → 답안 작성

선행지식 없이 시작

이 페이지를 읽는 순서

배열, 정렬 알고리즘, 재귀, loop invariant를 한 번도 배우지 않은 학습자를 대상으로 합니다. 각 소문제는 용어 정의와 작은 예제를 먼저 읽고, 색으로 구분한 상태 변화와 실제 시험 풀이를 따라간 뒤, 검산과 힌트 연습으로 스스로 재현하는 순서로 구성합니다.

  1. 기호부터 읽기

    A[i], A[l..r], key, prefix처럼 풀이에서 반복되는 말을 미니 사전에서 확인합니다. 대괄호 구간은 양 끝 index를 모두 포함한다는 규칙을 먼저 고정합니다.

  2. 작은 예제로 손 움직이기

    시험 배열보다 짧은 예제에서 비교, 이동, swap을 한 동작씩 따라 합니다. 결과를 외우지 말고 매 동작의 조건이 참인지 직접 말합니다.

  3. 실제 trace 재현하기

    각 줄에서 처리 구간, 선택한 key 또는 pivot, 바뀐 칸, 다음 구간을 표시합니다. 한 줄을 읽은 뒤 화면을 가리고 다음 줄을 먼저 예측합니다.

  4. 검산하고 변형 풀기

    정렬 순서와 원소 보존, partition 경계, invariant의 세 증명 의무를 확인합니다. 마지막 힌트 문제는 답을 열기 전에 종이에 한 번 풉니다.

먼저 익힐 기호와 용어

항목 (A[i])

배열 A의 i번째 index에 저장된 값입니다. 이 페이지는 0부터 세므로 첫 칸은 A[0]입니다.

이 페이지의 예: 초기 배열에서 \(A[0]=10, A[2]=2\)A[0]=10, A[2]=2

항목 (A[l..r])

index l부터 r까지 양 끝을 포함하는 연속 부분 배열입니다. \(l>r\)l>r이면 empty range로 읽습니다.

이 페이지의 예: \(A[0..2]=[10,7,2], A[0..-1]=\text{empty}\)A[0..2]=[10,7,2], A[0..-1]=empty

키

정렬 순서를 결정하는 비교값이며 Insertion Sort에서는 이번에 왼쪽 prefix에 삽입할 값입니다.

이 페이지의 예: \(j=3\)j=3이면 \(\text{key}=A[3]=3\)key=A[3]=3

항목 (swap(x,y))

두 위치의 값을 서로 교환하는 연산입니다. 값의 개수는 바뀌지 않으므로 multiset이 보존됩니다.

이 페이지의 예: swap(10,4) 뒤 두 값의 자리만 바뀜

항목 (p, q)

Hoare partition에서 아직 분류되지 않은 가운데 구간을 양쪽에서 좁히는 두 pointer입니다.

이 페이지의 예: p는 ≥pivot에서, q는 ≤pivot에서 멈춤

항목 (I(i))

반복문의 정해진 시점마다 참이어야 하는 loop invariant를 index i로 표시한 것입니다.

이 페이지의 예: MinSort의 I(i): 앞 i칸은 가장 작은 i개

수식 항목: \(\Theta(f(n))\)Θ(f(n))

입력 크기 n이 커질 때 실행량이 f(n)과 같은 차수로 증가한다는 점근적 표기입니다.

이 페이지의 예: \(\text{Insertion} \text{Sort} \text{worst} \text{case} \Theta(n^{2})\)Insertion Sort worst case Θ(n²)

정확성 범위

시험 문언과 배열, 배점, MinSort 빈칸은 SoSe 2025 기억 복기 자료에서 가져온 재구성(reconstructed)이며 공식 답안지가 아닙니다. Insertion Sort와 Hoare QuickSort의 알고리즘 규칙은 SoSe 2026 현재 강의 슬라이드로 검증했고, invariant 증명 형식은 현재 연습문제와 풀이로 교차 확인했습니다. 따라서 QuickSort trace는 이 페이지에 명시한 ‘첫 원소 pivot + Hoare partition’ 규칙에서만 같은 모양이 됩니다.

배점: 3점

3.1(a) · 삽입 정렬(Insertion Sort) — 정렬된 왼쪽 구간을 한 칸씩 키우기

배열 [10,7,2,3,6,1,4,13,29]을 Insertion Sort로 오름차순 정렬하고 각 단계를 그리시오.

이 절은 다른 소문제를 읽지 않아도 이해되도록 용어, 작은 예제, 실제 풀이, 검산을 모두 포함합니다.

먼저 문제의 정체부터 파악하기

Insertion Sort는 카드 정리와 같습니다. 왼쪽에는 이미 정렬된 카드 묶음이 있고, 오른쪽에서 카드 한 장 key를 꺼내 왼쪽의 알맞은 위치까지 밀어 넣습니다.

반복 j가 시작될 때 A[0..j-1]은 이미 정렬되어 있다는 약속이 핵심입니다. \(\text{key}=A[j]\)key=A[j]보다 큰 원소들을 오른쪽으로 한 칸씩 이동한 뒤 빈자리에 key를 넣으면 정렬 구간이 A[0..j]로 한 칸 커집니다.

이 문항은 최종 배열만 쓰면 부족합니다. 어느 key를 골랐고 어떤 원소가 이동했는지, 매 단계 뒤 정렬된 prefix가 어디까지인지 보여 주어야 합니다.

이 소문제만 읽어도 풀 수 있는 초보자 강의

무엇을 배우고 왜 필요한가

Insertion Sort는 ‘이미 해결한 왼쪽 부분을 한 칸 확장한다’는 가장 기본적인 알고리즘 사고를 보여 줍니다. 이 한 문제를 제대로 따라가면 배열 index, 비교와 이동, 안정성, loop invariant를 서로 연결해 설명할 수 있습니다.

  • 매 outer iteration에서 key와 정렬된 prefix의 범위를 정확히 표시하고 다음 배열을 계산할 수 있습니다.
  • shift와 swap의 차이를 말하고, 왜 엄격한 비교 \(A[i]>\text{key}\)A[i]>key가 같은 key의 상대 순서를 보존하는지 설명할 수 있습니다.
  • 최종 배열이 오름차순이고 입력과 같은 multiset인지 두 조건으로 검산할 수 있습니다.

풀이 전에 알아둘 용어

배열과 인덱스(index)

배열은 값을 순서대로 담은 칸들의 줄이고 인덱스는 칸 번호입니다. 이 알고리즘은 첫 칸을 0으로 세므로 길이 n의 마지막 인덱스는 n-1입니다.

아주 작은 예: [8,3,5]에서 \(A[0]=8, A[2]=5\)A[0]=8, A[2]=5입니다.

오름차순(sorted)

왼쪽 값이 바로 오른쪽 값보다 크지 않은 상태입니다. 모든 인접 쌍에 대해 \(A[k]\le A[k+1]\)A[k]≤A[k+1]이면 배열 전체가 오름차순입니다.

아주 작은 예: [2,2,7]은 정렬, [2,7,3]은 \(7>3\)7>3이라 미정렬입니다.

앞구간(prefix)과 기준값(key)

앞구간은 맨 왼쪽부터 이어지는 구간입니다. j번째 반복에서는 A[0..j-1]가 이미 정렬된 앞구간이고 A[j]를 기준값으로 꺼냅니다.

아주 작은 예: \(j=3\)j=3일 때 [2,7,10]이 앞구간이고 3이 기준값입니다.

중복을 세는 원소 모음(multiset)

각 값이 몇 번 나오는지까지 세는 원소 모음입니다. 올바른 정렬은 순서만 맞추는 것이 아니라 입력의 모든 값을 같은 개수로 보존해야 합니다.

아주 작은 예: [2,2,5]와 [2,5]는 2의 개수가 달라 같은 원소 모음이 아닙니다.

비유로 이해하기 · 손에 든 카드를 한 장씩 끼워 넣기

왼손에는 이미 작은 순서로 정리된 카드 묶음이 있고 오른쪽에서 카드 한 장을 뽑습니다. 새 카드보다 큰 카드들을 오른쪽으로 한 칸씩 밀어 빈틈을 만든 뒤, 새 카드를 그 틈에 넣습니다. 그러면 정리된 묶음이 정확히 한 장 커집니다.

  • 이미 정리된 왼손 카드정렬된 prefix A[0..j-1]
  • 오른쪽에서 뽑은 한 장임시 저장한 \(\text{key}=A[j]\)key=A[j]
  • 큰 카드를 한 칸 밀기\(A[i+1]=A[i] \text{shift}\)A[i+1]=A[i] shift
  • 생긴 틈에 카드 넣기\(A[i+1]=\text{key}\)A[i+1]=key

비유가 설명하지 못하는 부분: 실제 배열에는 물리적인 빈칸이 생기지 않습니다. key를 변수에 임시 저장했기 때문에 덮어써도 값이 사라지지 않는다는 점을 코드로 함께 보아야 합니다.

한 반복의 네 상태

  1. ① 정렬된 앞구간(prefix)[2,7,10]은 이미 정렬되어 있다고 가정합니다.
  2. ② 기준값 꺼내기(lift key)\(j=3\)j=3의 값 3을 기준값 변수에 안전하게 보관합니다.
  3. ③ 오른쪽으로 밀기(shift)10과 7은 3보다 크므로 오른쪽으로 한 칸씩 이동합니다.
  4. ④ 기준값 넣기(insert)\(2\le 3\)2≤3에서 멈추고 그 바로 뒤에 3을 기록합니다.

항상 ‘prefix 확인 → key 보관 → 큰 값 \(\text{shift} \to \text{key}\)shift → key삽입’ 순서입니다. 아직 처리하지 않은 suffix는 이번 반복의 정렬 보장 대상이 아닙니다.

작은 예제로 먼저 연습 · [5,2,4]에서 \(j=1\)j=1과 \(j=2\)j=2

맨 처음 \(A[0]=5\)A[0]=5하나는 정렬된 prefix입니다. 매 단계에서 key를 먼저 적고, 비교가 참일 때만 shift합니다.

  1. \(j=1, \text{key}=2\)j=1, key=2보관

    \(A[0]=5\)A[0]=5하나는 이미 정렬되어 있고 다음 값 2를 그 안에 넣어야 합니다.

    현재 상태: prefix [5] | key 2 | suffix [4]

  2. 5를 오른쪽으로 shift

    \(5>2\)5>2이므로 while 조건이 참이고 \(A[1]=5\)A[1]=5로 복사한 뒤 \(i=-1\)i=-1이 됩니다.

    현재 상태: \([5,5,4], \text{key}=2\)[5,5,4], key=2는 변수에 보존

  3. 빈 위치 A[0]에 2 삽입

    \(i<0\)i<0이므로 더 비교할 prefix 원소가 없고 \(A[i+1]=A[0]\)A[i+1]=A[0]이 삽입 위치입니다.

    현재 상태: [2,5,4]

  4. \(j=2, \text{key}=4\)j=2, key=4처리

    \(5>4\)5>4라 5만 밀고 \(2\le 4\)2≤4에서 멈추므로 4는 두 값 사이에 들어갑니다.

    현재 상태: [2,4,5]

작은 예제의 결론: 각 반복이 끝날 때 정렬된 prefix가 한 칸 커지고 값은 이동만 하므로, 마지막에는 전체 배열이 입력과 같은 원소를 가진 정렬 배열이 됩니다.

핵심 개념을 줄글로 깊게 이해하기

0단계 · 인덱스(index)와 앞구간(prefix)

배열 index는 0부터 8까지입니다. \(j=1\)j=1부터 시작하는 이유는 A[0] 하나만 있는 prefix는 이미 정렬되어 있기 때문입니다.

prefix A[0..j-1]은 배열의 맨 왼쪽에서 j개 원소를 뜻합니다. 이 영역은 원래 입력 prefix와 같은 원소를 가지며 정렬되어 있다고 믿고 다음 key를 삽입합니다.

머릿속 그림: 손에 든 카드 줄의 왼쪽 부분만 순서가 맞고, 오른쪽 카드는 아직 손대지 않은 상태입니다.

\[I(j):\quad A[0{:}j-1]=\operatorname{sort}\!\left(A_0[0{:}j-1]\right)\]
\[\mathrm{key}=A[j]\]

1단계 · 한 칸 밀기(shift)와 맞바꾸기(swap)

표준 Insertion Sort는 key를 임시 저장하고 key보다 큰 prefix 원소를 오른쪽으로 shift합니다. 마지막에 key를 빈 위치에 한 번 기록합니다.

인접 swap을 반복하는 구현도 같은 중간 순서를 만들 수 있지만, 답안에서는 강의 pseudocode에 맞춰 key·shift·insert를 표시하는 편이 명확합니다.

머릿속 그림: 새 책을 꽂으려고 큰 책들을 한 칸씩 옆으로 민 뒤 빈 칸에 새 책을 넣습니다.

\[\text{while } i\ge 0 \land A[i]>\mathrm{key}:\quad A[i+1]\gets A[i]\]
\[A[i+1]\gets\mathrm{key}\]

2단계 · 왜 올바른가

시작할 때 정렬된 prefix에서 key보다 큰 것만 오른쪽으로 이동합니다. key 이하의 마지막 원소 바로 뒤에 key가 들어가므로 새 prefix도 정렬됩니다.

값을 새로 만들거나 버리지 않고 이동만 하므로 원래 배열과 같은 multiset을 유지합니다. 정렬성과 원소 보존 두 조건이 함께 correctness를 만듭니다.

머릿속 그림: 학생들을 키순으로 세우되 누구도 빠지거나 두 번 서지 않게 하는 것입니다.

\[\text{정렬된 앞구간}+\text{원소 보존}\Longrightarrow\text{올바른 앞구간}\]

3단계 · 시간복잡도

이미 정렬된 배열에서는 각 기준값(key)이 바로 멈춰 최선의 경우 \(\Theta(n)\)Θ(n)입니다. 역순 배열에서는 j번째 기준값이 앞구간(prefix) 전체를 지나 이동 횟수가 \(1+2+...+(n-1)=\Theta(n^{2})\)1+2+...+(n-1)=Θ(n²)입니다.

이 문제는 실행 추적(trace)이 중심이지만, 왜 마지막 13과 29에서 이동이 없는지도 최선의 경우 한 단계의 모습으로 이해할 수 있습니다.

머릿속 그림: 새 카드가 항상 맨 뒤에 맞으면 한 번만 보고 끝나지만 항상 맨 앞이면 매번 모두 밀어야 합니다.

\[T_{\text{최선}}(n)=\Theta(n)\]
\[T_{\text{최악}}(n)=\Theta(n^{2})\]
\[S(n)=\Theta(1)\]

답안을 재현하기 위한 전체 의사코드 (pseudocode)

for j = 1 to n-1:
    key = A[j]
    i = j-1
    while i >= 0 and A[i] > key:
        A[i+1] = A[i]
        i = i-1
    A[i+1] = key
  • 인덱스 규칙: index는 0부터 시작하고 A[l..r]은 l과 r을 모두 포함합니다. outer loop의 j는 1,2,...,n-1입니다.
  • 반복 불변식 (invariant): j번째 반복 직전 A[0..j-1]은 원래 입력 \(\text{prefix} A_{0}[0..j-1]\)prefix A₀[0..j-1]와 같은 원소를 가지며 오름차순으로 정렬되어 있습니다.
  • 조기 종료 설명: 표준 pseudocode는 \(j=n-1\)j=n-1까지 실행합니다. 이 시험의 힌트는 \(j=6\)j=6뒤 전체 배열이 이미 정렬된 것이 눈에 보이면 이후 무변경 그림을 답안에서 생략해도 된다는 뜻이지, 알고리즘에 자동 조기 종료 조건이 있다는 뜻은 아닙니다.

실제 시험 문제 풀이를 단계별로 연결

  1. 처음 \(j=1\)j=1에서 무엇을 비교하나?

    \(\text{key}=7\)key=7을 저장하고 prefix의 마지막 \(A[0]=10\)A[0]=10과 비교합니다. \(10>7\)10>7이라 10을 A[1]로 밀고 경계를 지나면 7을 A[0]에 넣어 [7,10,...]을 만듭니다.

  2. \(j=3, \text{key}=3\)j=3, key=3은 왜 index 1에 들어가나?

    정렬 prefix [2,7,10]을 뒤에서 보며 10과 7을 밀고, 처음으로 3보다 크지 않은 2를 만납니다. 따라서 2의 바로 다음 칸 A[1]이 정확한 삽입 위치입니다.

  3. \(j=5, \text{key}=1\)j=5, key=1에서는 왜 다섯 번 shift하나?

    prefix [2,3,6,7,10]의 모든 값이 1보다 크므로 while이 경계 \(i=-1\)i=-1까지 계속됩니다. key는 임시 변수에 있으므로 다섯 칸을 밀어도 1은 사라지지 않습니다.

  4. \(j=6\)j=6뒤 무엇이 보장되나?

    새 \(\text{prefix} A[0..6]=[1,2,3,4,6,7,10]\)prefix A[0..6]=[1,2,3,4,6,7,10]이 정렬됩니다. 남은 13과 29도 이미 그보다 크므로 화면상 전체 배열이 정렬되어 이후 답안 그림은 생략할 수 있지만 표준 loop 자체는 계속됩니다.

실제 배열을 단계별로 끝까지 풀기

  1. 초기이번 기준값\((\text{key}) = -\)(key) = -
    107236141329

    \(A[0]=10\)A[0]=10하나는 이미 정렬된 prefix입니다.

  2. \(j=1\)j=1이번 기준값\((\text{key}) = 7\)(key) = 7
    710236141329

    \(10>7\)10>7이므로 10을 오른쪽으로 밀고 7을 A[0]에 넣습니다.

  3. \(j=2\)j=2이번 기준값\((\text{key}) = 2\)(key) = 2
    271036141329

    10과 7을 차례로 밀고 2를 맨 앞에 넣습니다.

  4. \(j=3\)j=3이번 기준값\((\text{key}) = 3\)(key) = 3
    237106141329

    10과 7을 밀고 \(2\le 3\)2≤3에서 멈춰 그 뒤에 3을 넣습니다.

  5. \(j=4\)j=4이번 기준값\((\text{key}) = 6\)(key) = 6
    236710141329

    10과 7을 밀고 \(3\le 6\)3≤6뒤에 6을 넣습니다.

  6. \(j=5\)j=5이번 기준값\((\text{key}) = 1\)(key) = 1
    123671041329

    prefix의 모든 원소가 1보다 커서 다섯 개를 밀고 1을 맨 앞에 넣습니다.

  7. \(j=6\)j=6이번 기준값\((\text{key}) = 4\)(key) = 4
    123467101329

    10,7,6을 밀고 \(3\le 4\)3≤4뒤에 4를 넣습니다. 이 시점에 전체 배열이 이미 정렬되었습니다.

  8. \(j=7,8\)j=7,8이번 기준값\((\text{key}) = 13,29\)(key) = 13,29
    123467101329

    13과 29는 각각 prefix의 마지막 값 이상이므로 이동이 없습니다. 표준 loop는 이 비교를 실행하지만 문제 힌트에 따라 답안의 무변경 그림은 생략해도 됩니다.

답이 맞는지 스스로 검산

  1. 인접한 모든 쌍을 확인하면 \(1\le 2\le 3\le 4\le 6\le 7\le 10\le 13\le 29\)1≤2≤3≤4≤6≤7≤10≤13≤29이므로 nondecreasing 조건을 만족합니다.
  2. 입력과 출력에 1,2,3,4,6,7,10,13,29가 각각 한 번씩 있어 multiset이 보존되었습니다.
  3. 각 j 뒤 A[0..j]만 따로 읽어도 정렬되어 있으며, 그 구간은 원래 \(A_{0}[0..j]\)A₀[0..j]의 값들을 정확히 한 번씩 포함합니다.

30초 자가점검

[3,3*,2]에서 두 번째 3*을 처리할 때 먼저 있던 3과 순서가 바뀌나?

힌트: while 조건은 ≥가 아니라 엄격한 >입니다.

정답: 바뀌지 않습니다. \(3>3\cdot \)3>3*이 거짓이라 shift하지 않고 3*은 기존 3의 오른쪽에 남으므로 안정적입니다.

[8,4,6]의 \(j=2, \text{key}=6\)j=2, key=6뒤 배열은 무엇인가?

힌트: 정렬 prefix [4,8]을 뒤에서 한 칸씩 비교합니다.

정답: 8만 오른쪽으로 밀고 \(4\le 6\)4≤6에서 멈춰 [4,6,8]이 됩니다.

정렬된 결과만 확인하면 correctness 검산이 끝나는가?

힌트: 값을 잃거나 복제한 잘못된 알고리즘을 생각해 보세요.

정답: 아닙니다. nondecreasing뿐 아니라 출력 multiset이 입력 multiset과 같은지도 확인해야 올바른 정렬입니다.

시험 답안 템플릿

각 줄에 j, key, 이동한 값, 결과 배열을 기록한다. 최종 결과는 [1,2,3,4,6,7,10,13,29]이다.

초보자가 자주 틀리는 지점

  • 최종 배열만 쓰고 중간 단계를 생략한다.
  • 정렬된 prefix 밖의 원소까지 비교한다.
  • key를 임시 저장하지 않아 shift 중 값을 잃는다.
  • 강의 표기에서 내부 scan 조건을 \(A[j]\ge \text{key}\)A[j]≥key로 바꾸면 중복 key의 안정성이 깨진다. 정답은 \(A[j]>\text{key}\)A[j]>key이며, 이 페이지 pseudocode는 같은 scan pointer를 i로 표기해 \(A[i]>\text{key}\)A[i]>key라고 쓴다.
  • \(j=0\)j=0부터 불필요하게 시작한다.

배점: 3점

3.1(b) · 퀵 정렬(QuickSort) — 첫 기준값과 호어 분할을 끝까지 추적하기

같은 배열을 QuickSort로 정렬하고 각 단계를 그리시오.

이 절은 다른 소문제를 읽지 않아도 이해되도록 용어, 작은 예제, 실제 풀이, 검산을 모두 포함합니다.

먼저 문제의 정체부터 파악하기

QuickSort는 pivot 하나를 기준으로 작은 값 영역과 큰 값 영역을 만든 뒤 두 영역을 재귀적으로 정렬합니다. 핵심 작업은 merge가 아니라 partition에 있습니다.

QuickSort에는 여러 올바른 partition 방식이 있으므로 trace는 알고리즘 정의에 따라 달라집니다. 여기서는 현재 강의 pp.103-124의 방식, 즉 첫 원소를 pivot으로 선택하고 p는 왼쪽에서 ≥pivot을, q는 오른쪽에서 ≤pivot을 찾는 Hoare partition을 사용합니다.

partition이 반환한 q에서 pivot이 반드시 최종 위치에 있는 것은 아닙니다. 보장되는 것은 \(A[\text{left}..q] \le_{p} \text{ivot}, A[q+1..\text{right}]\ge \text{pivot}\)A[left..q]≤pivot, A[q+1..right]≥pivot이며 재귀 범위도 [left..q]와 [q+1..right]입니다.

이 소문제만 읽어도 풀 수 있는 초보자 강의

무엇을 배우고 왜 필요한가

QuickSort는 한 번에 정렬하는 알고리즘이 아니라 pivot으로 두 구간을 만들고 같은 문제를 재귀적으로 반복합니다. 시험에서는 partition 방식마다 trace가 달라지므로, 이름만 외우지 않고 pointer 규칙과 재귀 구간을 정확히 선언하는 능력이 핵심입니다.

  • 첫 원소 pivot Hoare partition의 p·q 초기값, scan 정지 조건, swap 조건, 반환값을 순서대로 실행할 수 있습니다.
  • partition 뒤 pivot이 최종 위치에 있다는 잘못된 가정을 피하고 [left..q], [q+1..right] 재귀 범위를 쓸 수 있습니다.
  • 각 반환 q에서 두 partition 조건을 검산하고 재귀 호출이 길이 1에서 끝나는 이유를 설명할 수 있습니다.

풀이 전에 알아둘 용어

부분 배열과 양끝 포함 구간(inclusive range)

퀵 정렬(QuickSort)은 전체 배열 중 왼쪽 경계부터 오른쪽 경계까지의 구간만 다룹니다. 두 끝 인덱스를 모두 포함하므로 길이는 right-left+1입니다.

아주 작은 예: [5,2,8,1]의 [1..2]는 [2,8]입니다.

기준값(pivot)과 분할(partition)

기준값은 현재 구간을 나누는 값이고 분할은 기준값 이하 값이 왼쪽, 기준값 이상 값이 오른쪽에 있도록 재배치하는 과정입니다.

아주 작은 예: \(\text{pivot}=5\)pivot=5이면 2는 왼쪽 조건, 8은 오른쪽 조건을 만족합니다.

포인터(pointer) p와 q

p는 왼쪽에서 오른쪽으로, q는 오른쪽에서 왼쪽으로 움직이는 인덱스입니다. 둘이 멈춘 값이 반대편에 있어야 하면 맞바꿉니다(swap).

아주 작은 예: p가 9에서, q가 2에서 멈추면 9↔2로 교환합니다.

재귀와 종료 조건(base case)

함수가 더 작은 구간에 자기 자신을 호출하는 것을 재귀라 합니다. 길이 0 또는 1의 구간은 이미 정렬되어 더 나누지 않습니다.

아주 작은 예: quicksort(A,4,4)는 한 칸이라 즉시 끝납니다.

비유로 이해하기 · 양쪽 검표원이 잘못 선 사람을 바꾸기

pivot 점수 10을 기준으로 왼쪽 검표원 p는 왼쪽 줄에서 10 이상인 사람을, 오른쪽 검표원 q는 오른쪽 줄에서 10 이하인 사람을 찾습니다. 두 사람이 아직 마주치지 않았다면 서로 반대편에 선 두 사람을 바꾸고, 검표원이 만나거나 지나치면 경계를 확정합니다.

  • 기준 점수표\(\text{pivot}=A[\text{left}]\)pivot=A[left]
  • 왼쪽 검표원p: \(A[p]\ge \text{pivot}\)A[p]≥pivot에서 정지
  • 오른쪽 검표원q: \(A[q] \le_{p} \text{ivot}\)A[q]≤pivot에서 정지
  • 검표원이 교차한 자리partition 경계 q

비유가 설명하지 못하는 부분: 두 그룹은 partition 직후 내부까지 정렬된 것이 아닙니다. 또한 기준값 카드가 반드시 경계 q에 놓이는 방식도 아니므로, 재귀 호출로 양쪽 내부를 계속 정렬해야 합니다.

Hoare partition의 한 cycle

  1. ① pivot 선택현재 구간의 첫 값 A[left]를 기준으로 고정합니다.
  2. ② p의 오른쪽 탐색(scan)p를 먼저 증가시키며 기준값 이상인 첫 값에서 멈춥니다.
  3. ③ q의 왼쪽 탐색(scan)q를 먼저 감소시키며 기준값 이하인 첫 값에서 멈춥니다.
  4. ④ 맞바꾸거나 반환(swap/return)\(p<q\)p<q이면 교환하고 반복, 아니면 q를 반환합니다.

p와 q는 매 while cycle에서 적어도 한 칸 안쪽으로 움직입니다. \(p<q\)p<q일 때만 swap하고, \(p\ge q\)p≥q가 되면 마지막으로 계산된 q가 경계입니다.

작은 예제로 먼저 연습 · [5,8,2,7,1]을 한 번 partition

\(\text{left}=0, \text{right}=4, \text{pivot}=5, p=-1, q=5\)left=0, right=4, pivot=5, p=-1, q=5입니다. scan은 pointer를 먼저 한 칸 움직인 뒤 조건을 검사합니다.

  1. \(p=0, q=4\)p=0, q=4에서 정지

    \(A[0]=5\)A[0]=5는 pivot 이상이고 \(A[4]=1\)A[4]=1은 pivot 이하이므로 첫 정지점입니다.

    현재 상태: p→5 | 8 2 7 | 1←q

  2. 5와 1 swap

    \(p=0<q=4\)p=0<q=4이고 두 값은 각각 잘못된 쪽에 있으므로 위치를 바꿉니다.

    현재 상태: [1,8,2,7,5]

  3. 다음 \(p=1, q=2\)p=1, q=2에서 정지

    왼쪽의 8은 5 이상, 오른쪽에서 찾은 2는 5 이하입니다.

    현재 상태: \([1,8,2,7,5], p=1, q=2\)[1,8,2,7,5], p=1, q=2

  4. 8과 2 swap 후 교차

    교환 뒤 다음 scan은 \(p=2, q=1\)p=2, q=1이 되어 \(p\ge q\)p≥q이므로 \(q=1\)q=1을 반환합니다.

    현재 상태: \([1,2\;\longrightarrow\;8,7,5], \text{return} q=1\)[1,2 | 8,7,5], return q=1

작은 예제의 결론: 왼쪽 [0..1]은 모두 5 이하이고 오른쪽 [2..4]는 모두 5 이상입니다. 두 구간 내부는 아직 정렬되지 않았으므로 각각 QuickSort를 호출합니다.

핵심 개념을 줄글로 깊게 이해하기

0단계 · 분할 정복(Divide and Conquer)

Divide는 partition으로 두 부분 배열을 만들고, Conquer는 각 부분에 QuickSort를 재귀 호출하며, Combine은 별도 작업 없이 두 정렬 부분을 이어 보는 것입니다.

base case는 \(\text{left}\ge \text{right}\)left≥right인 길이 0 또는 1의 구간입니다. 이 구간은 이미 정렬되어 재귀 호출이 즉시 끝납니다.

머릿속 그림: 반 학생들을 기준 점수로 두 그룹에 나누고 각 그룹 안에서 같은 작업을 반복합니다.

\[\operatorname{QuickSort}(A,\mathrm{left},q)\]
\[\operatorname{QuickSort}(A,q+1,\mathrm{right})\]

1단계 · 호어 분할(Hoare partition)의 두 포인터

p는 왼쪽에서 출발해 pivot 이상인 첫 값을 찾고, q는 오른쪽에서 출발해 pivot 이하인 첫 값을 찾습니다. \(p<q\)p<q이면 두 값은 서로 잘못된 편에 있으므로 swap합니다.

p와 q가 만나거나 교차하면 q를 반환합니다. 매 반복에서 두 pointer가 가까워지므로 종료합니다.

머릿속 그림: 왼쪽 줄에서 너무 큰 사람과 오른쪽 줄에서 너무 작은 사람을 찾아 자리를 바꾸는 감독관 두 명입니다.

\[\mathrm{pivot}=A[\mathrm{left}]\]
\[p:\; A[p]\ge\mathrm{pivot}\text{ 에서 정지}\]
\[q:\; A[q]\le\mathrm{pivot}\text{ 에서 정지}\]

2단계 · 분할 불변식(partition invariant)

각 반복의 같은 시점에서 p 왼쪽의 확정 영역은 pivot 이하이고 q 오른쪽의 확정 영역은 pivot 이상입니다. 가운데만 아직 분류되지 않았습니다.

swap은 잘못된 양쪽 원소를 올바른 쪽으로 보내 이 invariant를 확장합니다. 종료 시 미분류 영역이 사라져 두 partition 조건이 완성됩니다.

머릿속 그림: 검사가 끝난 좌우 구역은 봉인하고 가운데 미검사 구역만 줄여 나갑니다.

\[\forall x\in A[\mathrm{left}{:}q]:\;x\le\mathrm{pivot}\]
\[\forall x\in A[q+1{:}\mathrm{right}]:\;x\ge\mathrm{pivot}\]

3단계 · 실행시간과 기준값(pivot)

한 분할(partition)은 구간을 한 번 훑으므로 \(\Theta(m)\)Θ(m)입니다. 균형 분할이 계속되면 깊이 \(\Theta(\log n)\)Θ(log n), 층마다 \(\Theta(n)\)Θ(n)으로 전체 \(\Theta(n \log n)\)Θ(n log n)입니다.

첫 원소를 기준값으로 삼을 때 이미 정렬된 배열처럼 매번 1개만 떨어지면 \(\Theta(n^{2})\)Θ(n²)입니다. 무작위 기준값은 입력과 독립적으로 좋은 분할을 기대해 평균 \(\Theta(n \log n)\)Θ(n log n)을 얻습니다.

머릿속 그림: 팀을 매번 반으로 나누면 빠르지만 한 명과 나머지로 계속 나누면 단계가 길어집니다.

\[T_{\text{최선/기대}}(n)=\Theta(n\log n)\]
\[T_{\text{최악}}(n)=\Theta(n^{2})\]

답안을 재현하기 위한 전체 의사코드 (pseudocode)

quicksort(A,left,right):
    if left < right:
        q = partition(A,left,right)
        quicksort(A,left,q)
        quicksort(A,q+1,right)
partition(A,left,right):
    pivot = A[left]
    p = left-1; q = right+1
    while p < q:
        repeat p=p+1 until A[p] >= pivot
        repeat q=q-1 until A[q] <= pivot
        if p < q: swap(A[p],A[q])
    return q
  • 인덱스 규칙: 모든 구간 [left..right]는 양 끝을 포함합니다. 초기 호출은 quicksort(A,0,n-1)이고 \(\text{left}\ge \text{right}\)left≥right이면 길이 0 또는 1이라 즉시 반환합니다.
  • 분할 직후 보장: 반환 q는 \(\text{left}\le q<\text{right}\)left≤q<right이고 A[left..q]의 모든 값은 pivot 이하, A[q+1..right]의 모든 값은 pivot 이상입니다. pivot 자체가 q에 있을 필요는 없습니다.

첫 분할(partition)의 포인터 이동을 한 칸씩 보기

포인터는 배열 바깥에서 시작하고, scan할 때 먼저 한 칸 움직인 뒤 정지 조건을 검사합니다.

장면포인터배열왜 이렇게 움직이나
초기화\(p=-1, q=9\)p=-1, q=9
107236141329
\(\text{pivot}=A[0]=10, p=\text{left}-1, q=\text{right}+1\)pivot=A[0]=10, p=left-1, q=right+1로 배열 바깥에서 시작
첫 scan\(p=0, q=6\)p=0, q=6
107236141329
p는 \(10\ge 10\)10≥10에서, q는 오른쪽에서 내려와 \(4\le 10\)4≤10에서 정지
항목 (swap)\(p=0, q=6\)p=0, q=6
472361101329
\(p<q\)p<q이므로 잘못된 양쪽 값 10과 4를 교환
둘째 scan/종료\(p=6, q=5\)p=6, q=5
472361101329
p와 q가 교차했으므로 swap하지 않고 \(q=5\)q=5반환

실제 시험 문제 풀이를 단계별로 연결

  1. 첫 P(0,8)에서 p와 q는 어디서 시작하나?

    \(p=\text{left}-1=-1, q=\text{right}+1=9\)p=left-1=-1, q=right+1=9에서 시작합니다. 첫 scan 후 \(p=0\)p=0의 \(10, q=6\)10, q=6의 4에서 멈추고 \(p<q\)p<q이므로 두 값을 바꿉니다.

  2. 10↔4 뒤 왜 \(q=5\)q=5를 반환하나?

    다음 p scan은 index 6의 10에서 멈추고 q scan은 index 5의 1에서 멈춥니다. \(p=6\ge q=5\)p=6≥q=5라 교환하지 않고 \(q=5\)q=5를 반환합니다.

  3. \(P(0,5), \text{pivot}=4\)P(0,5), pivot=4에서 두 swap은 무엇인가?

    먼저 4와 1을 바꿔 [1,7,2,3,6,4]를 만들고, 다음 scan에서 7과 3을 바꿔 [1,3,2,7,6,4]를 만듭니다. 그 뒤 \(p=3,q=2\)p=3,q=2로 교차합니다.

  4. 반환 q 뒤 재귀 범위는 어떻게 쓰나?

    Hoare 방식에서는 quicksort(left,q)와 quicksort(q+1,right)입니다. q 자체가 왼쪽 구간에 포함되며 [left,q-1]로 줄이면 원소를 빠뜨릴 수 있습니다.

  5. 전체 trace는 어디서 끝나나?

    P(0,2), P(1,2), P(3,5), P(3,4), P(6,8), P(7,8)를 거치면 모든 호출 구간이 길이 1이 됩니다. 이 base case들이 모여 전체 정렬을 완성합니다.

실제 배열을 단계별로 끝까지 풀기

  1. \(P(0,8), \text{pivot}=10\)P(0,8), pivot=10
    472361101329

    \(p=0\)p=0의 10과 \(q=6\)q=6의 4를 swap합니다. 다음 scan에서 \(p=6,q=5\)p=6,q=5로 교차하여 \(q=5\)q=5를 반환합니다. 재귀 구간은 [0..5], [6..8]입니다.

  2. \(P(0,5), \text{pivot}=4\)P(0,5), pivot=4
    132764101329

    4↔1, 이어서 7↔3을 swap한 뒤 \(p=3,q=2\)p=3,q=2로 교차하여 \(q=2\)q=2를 반환합니다.

  3. \(P(0,2), \text{pivot}=1\)P(0,2), pivot=1
    132764101329

    \(p=q=0\)p=q=0이 되어 \(q=0\)q=0을 반환합니다. 왼쪽은 길이 1이고 오른쪽 [1..2]만 남습니다.

  4. \(P(1,2), \text{pivot}=3\)P(1,2), pivot=3
    123764101329

    3과 2를 swap하고 \(q=1\)q=1을 반환하여 [1..2]가 정렬됩니다.

  5. \(P(3,5), \text{pivot}=7\)P(3,5), pivot=7
    123467101329

    7과 4를 swap하고 \(q=4\)q=4를 반환합니다.

  6. \(P(3,4), \text{pivot}=4\)P(3,4), pivot=4
    123467101329

    swap 없이 \(q=3\)q=3을 반환합니다. 왼쪽 큰 구간 [0..5] 정렬이 끝납니다.

  7. \(P(6,8), \text{pivot}=10\)P(6,8), pivot=10
    123467101329

    이미 pivot보다 큰 값들이 오른쪽에 있어 swap 없이 \(q=6\)q=6을 반환합니다.

  8. \(P(7,8), \text{pivot}=13\)P(7,8), pivot=13
    123467101329

    swap 없이 \(q=7\)q=7을 반환하고 모든 재귀 구간이 길이 1이 됩니다.

답이 맞는지 스스로 검산

  1. 각 partition 반환 직후 A[left..q]의 모든 값≤pivot이고 A[q+1..right]의 모든 값≥pivot인지 실제 값을 훑습니다.
  2. 재귀 자식 [left..q], [q+1..right]가 겹치지 않으면서 부모 구간을 빠짐없이 덮고, 둘 다 부모보다 짧은지 확인합니다.
  3. 최종 배열은 nondecreasing이고 입력의 아홉 값을 같은 개수로 가지므로 정렬 결과 조건을 만족합니다.

30초 자가점검

Hoare partition이 q를 반환하면 pivot은 항상 A[q]인가?

힌트: 첫 P(0,8)의 pivot 10과 반환 \(q=5\)q=5를 비교하세요.

정답: 아닙니다. 첫 partition 뒤 10은 index 6이고 \(q=5\)q=5입니다. 보장은 pivot의 위치가 아니라 두 구간의 ≤/≥ 조건입니다.

[4,1,6]에서 첫 원소 pivot Hoare partition의 반환 q는?

힌트: \(p=-1,q=3\)p=-1,q=3에서 시작해 4와 1을 먼저 찾습니다.

정답: 4↔1 뒤 [1,4,6]이 되고 다음 scan에서 \(p=1,q=0\)p=1,q=0으로 교차하므로 \(q=0\)q=0을 반환합니다.

첫 원소 pivot QuickSort의 worst case가 \(\Theta(n^{2})\)Θ(n²)이 되는 입력은?

힌트: 매번 한 칸과 나머지로 가장 불균형하게 나뉘는 경우를 생각하세요.

정답: 이미 오름차순이거나 내림차순인 배열처럼 첫 pivot이 계속 극값이면 분할이 1 대 n-1에 가까워져 \(\Theta(n^{2})\)Θ(n²)이 됩니다.

시험 답안 템플릿

답안 첫 줄에 'pivot=A[left], Hoare partition'을 선언하고 각 partition마다 구간, pivot, swap 후 배열, 반환 q, 다음 재귀 구간을 쓴다. 최종 배열은 [1,2,3,4,6,7,10,13,29]이다.

초보자가 자주 틀리는 지점

  • partition 방식을 선언하지 않아 trace 기준이 불명확하다.
  • Hoare 방식에서 pivot이 항상 q에 있다고 가정한다.
  • 재귀 범위를 [left,q-1]과 [q+1,right]로 잘못 쓴다.
  • p와 q가 교차한 뒤에도 swap한다.
  • partition 한 번으로 양쪽 내부까지 정렬됐다고 생각한다.
  • expected \(\Theta(n \log n)\)Θ(n log n)을 worst-case 보장으로 쓴다.

배점: 4점

3.2 · 최솟값 정렬(MinSort)의 반복 불변식 — 빈칸 암기가 아니라 증명의 시간축 이해하기

고유한 key(eindeutige Schlüssel)를 가진 배열을 오름차순으로 정렬하는 MinSort의 주어진 loop invariant를 이용해 Initialization, Maintenance, Termination 증명의 빈칸을 채우시오. indexOfMin(A[p..q])는 그 구간에서 최소 key의 index를 반환한다.

이 절은 다른 소문제를 읽지 않아도 이해되도록 용어, 작은 예제, 실제 풀이, 검산을 모두 포함합니다.

먼저 문제의 정체부터 파악하기

Loop invariant는 반복문이 도는 동안 아무 때나 참인 문장이 아니라, 매 반복의 같은 시점—이 문제에서는 i번째 반복 직전—에 참인 약속입니다.

MinSort는 suffix A[i..n-1]의 최솟값을 찾아 A[i]와 swap합니다. 따라서 반복 하나가 끝날 때마다 가장 작은 원소 하나가 확정 prefix 뒤에 추가됩니다.

증명은 Initialization에서 첫 시점을 확인하고, Maintenance에서 \(I(i)\to I(i+1)\)I(i)→I(i+1)을 보이며, Termination에서 loop가 끝난 시점의 invariant를 최종 정렬 조건으로 바꾸는 세 칸 구조입니다.

이 소문제만 읽어도 풀 수 있는 초보자 강의

무엇을 배우고 왜 필요한가

Loop invariant 증명은 코드를 실행해 정답을 얻는 것과 그 정답이 모든 입력에서 맞는 이유를 설명하는 일을 연결합니다. MinSort는 prefix가 한 칸씩 확정되는 모습이 단순해서 Initialization, Maintenance, Termination의 역할을 처음 배우기에 적합합니다.

  • invariant가 참인 정확한 시점과 A[0..i-1]의 의미를 index가 어긋나지 않게 말할 수 있습니다.
  • swap이 원소 보존을, suffix minimum이 정렬된 prefix 확장을 보장하는 이유를 각각 설명할 수 있습니다.
  • 원문의 15개 빈칸을 위치별 근거와 함께 채우고 종료 시 invariant에서 전체 정렬을 도출할 수 있습니다.

풀이 전에 알아둘 용어

실행 전 조건(precondition)과 실행 후 조건(postcondition)

실행 전 조건은 알고리즘 시작 전에 가정하는 조건이고 실행 후 조건은 끝난 뒤 반드시 얻어야 하는 결과입니다. 증명은 둘 사이를 연결합니다.

아주 작은 예: 입력은 배열이고, 출력은 같은 원소를 오름차순으로 담은 배열입니다.

반복 불변식(loop invariant)

매 반복의 같은 시점에 참인 문장입니다. 이 문제에서는 i번째 반복 본문(loop body)을 실행하기 직전에 참이라고 시점을 고정합니다.

아주 작은 예: \(i=2\)i=2직전 앞 두 칸은 가장 작은 두 기준값을 정렬해 담습니다.

빈 구간(empty range)

왼쪽 인덱스가 오른쪽 인덱스보다 큰 구간은 원소가 하나도 없는 빈 구간입니다. 빈 구간은 역전 쌍이 없어 자명하게 정렬입니다.

아주 작은 예: A[0..−1]은 길이 0이고 가장 작은 0개를 담습니다.

원소 보존과 순열(permutation)

정렬은 입력 값을 삭제하거나 새로 만들면 안 됩니다. 맞바꾸기만 하는 알고리즘은 각 값의 개수를 유지하므로 출력이 입력의 순열입니다.

아주 작은 예: \(\text{swap}([3,1])=[1,3]\)swap([3,1])=[1,3]은 같은 두 원소를 유지합니다.

비유로 이해하기 · 아직 뽑지 않은 선수 중 1등을 확정 명단에 붙이기

전체 선수 중 기록이 가장 작은 사람부터 한 명씩 확정 명단의 뒤에 붙입니다. i명이 이미 기록순으로 확정되어 있다면, 남은 선수 중 최고 기록 한 명을 골라 i번째 자리에 놓으면 i+1명이 올바른 순서로 확정됩니다.

  • 확정된 수상자 명단prefix A[0..i-1]
  • 아직 순위가 없는 선수들suffix A[i..n-1]
  • 남은 선수 중 최고 기록indexOfMin이 찾은 A[imin]
  • 명단 끝 자리와 교환swap(A[i],A[imin])

비유가 설명하지 못하는 부분: 실제 swap은 A[i]에 있던 값을 suffix의 imin 자리로 보냅니다. 명단에 단순히 복사해 붙이는 것이 아니므로 원소가 중복되지 않는다는 swap의 양방향 효과를 함께 써야 합니다.

증명의 시간축

  1. I(0)prefix는 empty이고 원래 배열과 동일하므로 시작 조건이 참입니다.
  2. I(i) 가정앞 i칸이 가장 작은 i개이고 원소 전체가 보존되어 있다고 가정합니다.
  3. 한 번 실행suffix minimum을 A[i]와 swap하여 prefix를 한 칸 확장합니다.
  4. I(n−1)앞 n−1칸과 마지막 최대 key를 합쳐 전체 정렬을 얻습니다.

Initialization은 I(0), Maintenance는 임의의 I(i)⇒I(i+1), Termination은 I(n−1)과 종료 조건을 postcondition으로 해석하는 단계입니다.

작은 예제로 먼저 연습 · MinSort([4,1,3,2])

key는 모두 고유합니다. 각 반복 직전에 prefix가 무엇을 보장하는지 먼저 말하고 suffix minimum을 찾습니다.

  1. \(i=0\)i=0초기화

    A[0..−1]은 empty이고 배열은 아직 [4,1,3,2] 그대로라 I(0)이 참입니다.

    현재 상태: prefix [] | suffix [4,1,3,2]

  2. suffix min 1을 A[0]과 swap

    \(\text{imin}=1\)imin=1이고 \(0\le 1\le 3\)0≤1≤3입니다. 1이 앞에 와서 가장 작은 한 개가 확정됩니다.

    현재 상태: prefix [1] | suffix [4,3,2]

  3. \(i=1\)i=1에서 suffix min 2를 swap

    이미 확정된 1보다 작을 수 없는 남은 최소 2가 뒤에 붙어 [1,2]가 정렬됩니다.

    현재 상태: prefix [1,2] | suffix [3,4]

  4. \(i=2\)i=2에서 min 3은 제자리

    \(\text{imin}=i=2\)imin=i=2여도 자기 자신과 swap하면 multiset과 prefix 성질이 그대로 유지됩니다.

    현재 상태: prefix [1,2,3] | last [4]

  5. \(i=3 \text{exit}\)i=3 exit해석

    앞 세 칸은 가장 작은 세 key이고 남은 4는 가장 큰 key이므로 전체가 정렬입니다.

    현재 상태: [1,2,3,4]

작은 예제의 결론: 한 반복은 원소를 잃지 않으면서 ‘가장 작은 i개’라는 부분 정답을 i+1개로 확장하고, 마지막 한 값은 자동으로 최대가 됩니다.

핵심 개념을 줄글로 깊게 이해하기

0단계 · 반복 불변식(invariant)의 두 문장

첫째, A에는 원래 배열의 원소가 정확히 그대로 있습니다. swap만 하므로 원소가 사라지거나 새로 생기지 않습니다.

둘째, 반복 i 직전 A[0..i-1]은 전체에서 가장 작은 i개 원소를 오름차순으로 담습니다. suffix는 아직 정렬되지 않아도 됩니다.

머릿속 그림: 수상자 명단 앞부분에 지금까지 확정된 최저 기록 선수들을 순서대로 붙이는 과정입니다.

\[I(i):\;\operatorname{multiset}(A)=\operatorname{multiset}(A_0)\]
\[A[0{:}i-1]=\text{가장 작은 }i\text{개를 정렬한 앞구간}\]

1단계 · 초기 성립(Initialization)과 빈 앞구간

첫 반복은 \(i=0\)i=0입니다. 그러면 \(\text{prefix} A[0..i-1]=A[0..-1]\)prefix A[0..i-1]=A[0..-1]은 원소가 0개인 empty range입니다.

빈 배열은 비교할 역전 쌍이 없으므로 자명하게 정렬되어 있고, 가장 작은 0개를 담는다는 문장도 자명합니다. 아직 swap 전이므로 원소 보존도 참입니다.

머릿속 그림: 아직 뽑은 수상자가 0명인 명단은 순서가 틀릴 수 없습니다.

\[i=0\]
\[A[0{:}-1]=\varnothing\]
\[\lvert A[0{:}-1]\rvert=0\]

2단계 · 반복 유지(Maintenance)

I(i)를 가정하면 prefix에는 이미 가장 작은 i개가 확정되어 있습니다. 남은 suffix A[i..n-1]에서 가장 작은 key의 index imin은 \(i\le \text{imin}\le n-1\)i≤imin≤n-1입니다.

A[i]와 A[imin]을 swap하면 그 원소가 prefix 끝 A[i]에 붙습니다. 기존 prefix의 마지막보다 작을 수 없는 '남은 원소 중 최소'이므로 A[0..i]는 가장 작은 i+1개를 정렬 상태로 담습니다.

머릿속 그림: 아직 순위가 없는 선수 중 최고 기록 한 명을 뽑아 확정 명단 맨 뒤에 붙입니다.

\[i\le i_{\min}\le n-1\]
\[i_{\min}=\operatorname{indexOfMin}(A[i{:}n-1])\]
\[I(i)\Longrightarrow I(i+1)\]

3단계 · 종료와 결론(Termination)

\(\text{for} i=0 \text{to} n-2\)for i=0 to n-2는 \(i=n-1\)i=n-1반복 직전에 종료합니다. invariant에 \(i=n-1\)i=n-1을 대입하면 A[0..n-2]가 가장 작은 n-1개를 정렬해서 담습니다.

원소 전체가 보존되었으므로 남은 A[n-1]은 유일하게 남은 가장 큰 key입니다. 따라서 prefix 뒤에 이 값을 붙인 전체 A[0..n-1]이 정렬됩니다.

머릿속 그림: 가장 작은 n-1명을 순서대로 확정하면 마지막 남은 한 명은 자동으로 가장 큽니다.

\[i_{\mathrm{exit}}=n-1\]
\[A[0{:}n-2]=\text{가장 작은 }n-1\text{개}\]
\[A[n-1]=\max(A)\]

4단계 · 끝남과 정당성(correctness)의 차이

for loop의 범위가 유한하므로 알고리즘이 끝난다는 termination은 쉽게 보입니다. 하지만 끝난다는 사실만으로 정렬이 맞다는 결론은 나오지 않습니다.

종료 시 invariant가 전체 postcondition을 함의한다는 연결이 필요합니다. 즉 '끝난다'와 '끝났을 때 답이 맞다'를 둘 다 써야 완전한 correctness 증명입니다.

머릿속 그림: 시험 시간이 끝났다고 답이 맞는 것은 아닙니다. 종료 시 작성한 내용이 정답 조건을 만족해야 합니다.

\[\text{종료}+I(n-1)\Longrightarrow\text{정렬 후 조건(postcondition)}\]

답안을 재현하기 위한 전체 의사코드 (pseudocode)

n = length(A)
for i = 0 to n-2:
    imin = indexOfMin(A[i..n-1])
    swap(A[i], A[imin])
  • 실행 전 조건 (precondition): \(n\ge 1\)n≥1이고 A의 key들은 서로 고유하며 indexOfMin(A[p..q])는 \(p\le q\)p≤q인 inclusive range에서 최소 key의 index를 반환합니다. \(n=0\)n=0인 빈 배열은 이미 정렬됐지만 아래 termination 문장 A[n−1]을 사용할 수 없으므로 별도 trivial case로 처리합니다.
  • 반복 불변식 (invariant): i번째 반복 직전 A는 원래 배열의 entry들을 정확히 포함하고, A[0..i-1]은 전체에서 가장 작은 i개 key를 오름차순으로 포함합니다.
  • 실행 후 조건 (postcondition): 종료 시 A는 원래 entry들의 permutation이며 A[0..n-1] 전체가 오름차순입니다.

원문 15개 빈칸 풀이: 위치 → 정답 → 이유

복기 원문의 각 빈칸에 B01부터 B15까지 번호를 붙였습니다. 먼저 원문만 채운 뒤 표로 검산하세요.

Induktionsanfang: Vor dem ersten Schleifendurchlauf (\(i=[B01]\)i=[B01]) stimmt A mit dem ursprünglichen Array überein, und A[0,...,[B02]] enthält die [B03] Einträge mit den kleinsten Schlüsseln.

Induktionsschritt: Der Algorithmus berechnet den Index [B04] ≤ imin ≤ [B05] des kleinsten Schlüssels in A[[B06],...,[B07]]. Zu Beginn der nächsten, der ([B08])-ten Iteration enthält A[0,...,[B09]] die i+1 [B10], sortiert in aufsteigender Reihenfolge.

Terminierung: Die FOR-Schleife bricht vor dem [B11]-ten Durchlauf ab. Mit \(i=[B12]\)i=[B12] gilt: A[0,...,[B13]] enthält die [B14] kleinsten Einträge. Also muss A[n-1] [B15] sein.

항목 (ID)빈칸 위치정답왜?
항목 (B01)첫 반복의 i0for loop가 \(i=0\)i=0에서 시작합니다.
항목 (B02)초기 prefix의 오른쪽 끝−1i-1에 \(i=0\)i=0을 넣으면 −1이라 A[0..−1]은 empty range입니다.
항목 (B03)초기 prefix에 든 최소 entry 수0빈 prefix는 가장 작은 0개를 자명하게 담습니다.
항목 (B04)imin의 하한i최솟값 검색은 아직 확정되지 않은 suffix의 첫 index i부터 합니다.
항목 (B05)imin의 상한n−1배열의 마지막 유효 index가 n−1입니다.
항목 (B06)indexOfMin 검색 구간 시작i이미 확정된 prefix를 제외하고 A[i]부터 검색합니다.
항목 (B07)indexOfMin 검색 구간 끝n−1남은 suffix 전체를 마지막 index까지 포함합니다.
항목 (B08)다음 반복 번호i+1한 번 실행하면 for index가 1 증가합니다.
항목 (B09)확장된 prefix의 오른쪽 끝i기존 A[0..i−1]에 새 A[i]가 붙습니다.
항목 (B10)확장된 prefix의 내용Einträge von A mit den kleinsten Schlüsselnsuffix 최소를 붙였으므로 전체에서 가장 작은 i+1개입니다.
항목 (B11)실행되지 않는 첫 반복 indexn−1실제 실행은 \(i=0\)i=0부터 n−2까지이고 그 다음 \(i=n\)i=n−1에서 종료합니다.
항목 (B12)종료 상태에 대입할 in−1종료 직전의 invariant를 I(n−1)로 해석합니다.
항목 (B13)종료 prefix의 오른쪽 끝n−2i−1에 n−1을 넣으면 n−2입니다.
항목 (B14)종료 prefix의 최소 entry 수n−1A[0..n−2]에는 n−1개 칸이 있습니다.
항목 (B15)마지막 A[n−1]의 정체der Eintrag mit dem größten Schlüssel가장 작은 n−1개를 제외하고 남은 고유 key는 가장 큰 key 하나입니다.

실제 시험 문제 풀이를 단계별로 연결

  1. Initialization의 세 빈칸은 왜 0, −1, 0인가?

    첫 index가 \(i=0\)i=0이고 invariant의 prefix 끝은 i−1이므로 −1입니다. A[0..−1]은 empty라 가장 작은 0개를 정렬해 담는다는 문장이 자명합니다.

  2. Maintenance에서 imin의 범위는 왜 i..n−1인가?

    앞 i칸은 이미 확정했으므로 다시 고르지 않습니다. indexOfMin은 아직 미확정인 suffix A[i..n−1] 전체에서 최소를 찾아야 합니다.

  3. swap 뒤 A[0..i]가 왜 정렬인가?

    기존 prefix는 전체 최소 i개를 정렬해 담고 있습니다. 새 A[i]는 나머지 중 최소라 기존 prefix의 마지막보다 작을 수 없으므로 뒤에 붙여도 오름차순입니다.

  4. 원소 보존은 어느 연산에서 나오나?

    loop body는 A[i]와 A[imin]을 swap할 뿐입니다. 두 값을 교환하면 값과 등장 횟수는 변하지 않아 원래 배열과 같은 multiset이 유지됩니다.

  5. 종료에서 \(i=n\)i=n−1을 넣는 이유는?

    실제 마지막 body index는 n−2이고 다음 \(i=n\)i=n−1에서 loop condition이 거짓이 됩니다. 따라서 exit state에 I(n−1)을 적용하면 앞 n−1칸이 확정됩니다.

증명 전체를 문장으로

초기 성립 (Initialization)

첫 반복 직전 \(i=0\)i=0이다. A는 아직 바뀌지 않아 원래 원소를 그대로 가진다. A[0..-1]은 빈 prefix로, 가장 작은 0개 원소를 오름차순으로 담는다는 명제가 자명하게 참이다. 따라서 I(0)이 성립한다.

반복 유지 (Maintenance)

I(i)를 가정한다. indexOfMin은 A[i..n-1]에서 최소 key의 index imin을 계산하므로 \(i\le \text{imin}\le n-1\)i≤imin≤n-1이다. A[i]와 A[imin]의 swap은 원소 multiset을 보존한다. suffix의 최소값이 기존의 가장 작은 i개 뒤 A[i]에 붙으므로 A[0..i]는 전체에서 가장 작은 i+1개를 오름차순으로 담는다. 따라서 다음 반복 직전 I(i+1)이 성립한다.

종료와 결론 (Termination)

마지막 실행 index는 n-2이며 loop는 \(i=n-1\)i=n-1반복 직전에 끝난다. I(n-1)에 의해 A[0..n-2]는 가장 작은 n-1개 원소를 정렬해 담는다. 원소가 보존되었으므로 A[n-1]은 가장 큰 key이고, 따라서 전체 배열이 오름차순이다.

답이 맞는지 스스로 검산

  1. Initialization 문장에는 시점 \(i=0, \text{empty} \text{prefix},\)i=0, empty prefix,원래 entry 보존이 모두 들어 있는지 확인합니다.
  2. Maintenance 문장에는 검색 범위 i..n−1, imin bound, swap의 multiset 보존, prefix가 i+1개로 확장되는 이유가 모두 있어야 합니다.
  3. Termination 문장에는 실행 index 0..n−2와 exit index n−1을 구분하고, 마지막 A[n−1]이 최대라는 연결까지 있어야 합니다.
  4. 15개 blank id B01..B15가 빠짐없이 한 번씩 채워졌는지 원문 표시와 답 표를 맞대어 확인합니다.

30초 자가점검

\(i=0\)i=0에서 A[0..−1]을 오류가 아니라 empty로 읽어야 하는 이유는?

힌트: prefix가 포함해야 할 가장 작은 원소 수를 세어 보세요.

정답: 첫 반복 전 확정 원소가 0개여야 하므로 길이 0인 prefix가 필요하고 A[0..−1]이 이를 정확히 표현합니다.

Maintenance에서 ‘A[0..i]가 정렬’만 쓰면 충분한가?

힌트: 정렬된 [100,200]도 전체의 가장 작은 두 값은 아닐 수 있습니다.

정답: 충분하지 않습니다. 전체에서 가장 작은 i+1개를 담는다는 선택 성질과 원소 보존도 함께 써야 종료 결론을 얻습니다.

key가 중복될 수 있다면 B15의 표현을 어떻게 조심해야 하나?

힌트: 원문은 eindeutige Schlüssel를 전제로 합니다.

정답: 고유 key 전제에서는 ‘유일하게 남은 가장 큰 key’라 할 수 있습니다. 중복을 허용하면 남은 값이 최대값 중 하나라고 표현해야 합니다.

시험 답안 템플릿

Initialization에는 \(i=0\)i=0과 empty prefix, Maintenance에는 검색 범위·imin bound·swap 후 i+1 prefix, Termination에는 exit index n-1과 마지막 최대 원소를 반드시 쓴다.

초보자가 자주 틀리는 지점

  • invariant 시점을 반복 후로 바꿔 index가 한 칸씩 어긋난다.
  • A[0..-1]을 오류라고 생각한다. 이는 empty range 표기입니다.
  • swap이 원소 보존을 보인다는 문장을 생략한다.
  • suffix 최소가 왜 prefix 맨 뒤에 붙어도 정렬인지 설명하지 않는다.
  • 종료 index를 n-2와 n-1 사이에서 혼동한다.
  • A[0..n-2]가 정렬됐다는 것만 쓰고 마지막 원소가 최대임을 연결하지 않는다.

근거와 정확성 범위

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