3. Sortieralgorithmen (10 Punkte)

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

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

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

자료의 성격과 정확성 경계

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

문제를 읽기 전에 알아둘 기호와 용어

기호를 모른 채 풀이를 외우지 않도록, 이 문제에서 실제로 쓰는 뜻과 작은 예를 먼저 확인합니다.

기호·용어뜻작은 예
항목 (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²)

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

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를 최종 정렬 조건으로 바꾸는 세 칸 구조입니다.

필요한 개념을 깊게 배우기

개념 1

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

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

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

수식으로 정확히 쓰기

핵심 규칙I(i):\;\operatorname{multiset}(A)=\\(\text{operatorname}{\text{multiset}}(A_{0})\)operatorname{multiset}(A₀)

핵심 규칙A[0{:}i-1]=\text{가장 작은 }i\text{개를 정렬한 앞구간}

개념 2

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 전이므로 원소 보존도 참입니다.

수식으로 정확히 쓰기

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

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_{\min}=\operatorname{indexOfMin}(A[i{:}n-1])
\[I(i)\Longrightarrow I(i+1)\]I(i)\Longrightarrow I(i+1)
개념 4

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]이 정렬됩니다.

수식으로 정확히 쓰기

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

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

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

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

수식으로 정확히 쓰기

핵심 규칙\text{종료}+I(n-1)\Longrightarrow\text{정렬 후 조건(postcondition)}

초보자용 연결 강의

이 소문제를 왜 배우나

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

풀이 전에 꼭 알아야 할 말

실행 전 조건(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의 양방향 효과를 함께 써야 합니다.

증명의 시간축

I(0)prefix는 empty이고 원래 배열과 동일하므로 시작 조건이 참입니다.
I(i) 가정앞 i칸이 가장 작은 i개이고 원소 전체가 보존되어 있다고 가정합니다.
한 번 실행suffix minimum을 A[i]와 swap하여 prefix를 한 칸 확장합니다.
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을 찾습니다.

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

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

prefix [] | suffix [4,1,3,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]
\(i=1\)i=1에서 suffix min 2를 swap

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

prefix [1,2] | suffix [3,4]
\(i=2\)i=2에서 min 3은 제자리

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

prefix [1,2,3] | last [4]
\(i=3 \text{exit}\)i=3 exit해석

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

[1,2,3,4]

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

이제 실제 시험 문제에 연결

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

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

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

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

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

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

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

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

종료에서 \(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, \text{empty} \text{prefix},\)i=0, empty prefix,원래 entry 보존이 모두 들어 있는지 확인합니다.
  • Maintenance 문장에는 검색 범위 i..n−1, imin bound, swap의 multiset 보존, prefix가 i+1개로 확장되는 이유가 모두 있어야 합니다.
  • Termination 문장에는 실행 index 0..n−2와 exit index n−1을 구분하고, 마지막 A[n−1]이 최대라는 연결까지 있어야 합니다.
  • 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과 마지막 최대 원소를 반드시 쓴다.

자주 하는 실수

근거와 정확성 범위

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

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