알고리즘·자료구조·삽입 정렬·불변식

루프 불변식과 정확성 증명 (Loop invariants and correctness)

1타 강사식 학습 동선

직관 → 조작 → 예시 → 함정 → 답안

Loop invariant(Schleifeninvariante)는 loop의 같은 시점에서 반복해서 참이어야 하는 상태 문장입니다. AUD에서는 보통 각 반복 직전의 상태를 잡고, Initialization, Maintenance/Fortsetzung, Termination/Terminierung 세 의무로 part...

loop invariant / Schleifeninvarianteprecondition / Vorbedingungpostcondition / Nachbedingunginitialization / Induktionsanfangmaintenance / Fortsetzung / Induktionsschritt

연습으로 이동 개인화 순서 보기

01 직관이 개념이 왜 필요한지 한 문장으로 잡기

02 손풀이그래프, 트리, 표, 문자열을 직접 움직이며 확인하기

03 단계별 예제시험 답안처럼 조건과 결론을 연결하기

04 함정 점검자주 틀리는 조건과 반례를 먼저 차단하기

반복 불변식(Schleifeninvariante) · 정확성(Korrektheit) · 종료성(Terminierung)

반복문 증명은 “매 반복 직전의 상태 사진”을 끝까지 유지하는 일입니다

반복 불변식(Loop invariant, Schleifeninvariante)은 반복문 안의 아무 문장이 아니라, 정해 둔 시점마다 반드시 참이어야 하는 상태 문장입니다. AUD 답안에서는 보통 각 반복 직전 상태를 잡고 초기화(Initialization, Induktionsanfang), 유지(Maintenance/Fortsetzung, Induktionsschritt), 종료(Termination, Terminierung)의 세 단계로 부분 정확성(partial correctness)을 보입니다.

I(j) 1. 초기화: 처음에도 참 2. 유지: 한 번 실행해도 참 3. 종료: 반복 조건이 거짓이라는 사실과 합쳐 사후조건 도출

먼저 알아야 할 개념 지도

명세 (Specification)

사전조건(Precondition, Vorbedingung)은 시작 조건이고, 사후조건(postcondition, Nachbedingung)은 끝난 뒤 만족해야 할 결과 조건입니다.

수학적 귀납법 (Induction)

불변식 증명(invariant proof)은 수학적 귀납법과 같습니다. 처음 참이고 한 단계가 참을 보존하면 모든 반복 직전에 참입니다.

반복 조건 (Loop Guard)

마지막에는 불변식만 쓰지 말고 반복 조건(guard)이 거짓이라는 사실을 함께 써서 사후조건을 얻습니다.

강의 자료에 근거한 개념 지도

근거: \(\text{data}/\text{aud}_{\text{topi}}\,c_{\text{map}}.\text{md}\)data/aud(topic)(map).md는 Übung\AuD26_Sheet01.pdf, Übung\AuD26_Sheet01-Sol.pdf, Übung\AuD26_Sheet01-GrpSol.pdf를 “알고리즘, 자료구조, 삽입 정렬, 불변식”으로 연결합니다. \(\text{data}/\text{aud}_{\text{chunks}}.\text{jsonl}\)data/aud(chunks).jsonl 2번 줄은 알고리즘(Algorithmus)의 종료성, 정확성, 효율성을 다루고, Minimum 예시에서 반복 불변식을 초기화·유지·종료로 검증합니다. 9–12번 줄은 InsertionSort와 BubbleSort의 정확성 증명, 정렬된 출력 외에 원래 원소 보존도 필요하다는 문제를 포함합니다.

자료 한계: 추출된 구간은 모든 슬라이드 그림을 완전하게 재현하지 않습니다. 아래 배열 시각화는 Sheet01의 불변식 증명 형식과 InsertionSort 의사코드를 바탕으로 Study Hub에서 만든 설명용 도식입니다.

사전조건과 사후조건

사전조건(Precondition, Vorbedingung)은 알고리즘 시작 전에 허용되는 입력 조건입니다. 사후조건(Postcondition, Nachbedingung)은 알고리즘이 끝난 뒤 반드시 참이어야 하는 결과 조건입니다. 정렬의 정확성에서는 sorted(A)만으로는 부족합니다. 원래 원소를 잃거나 새로 만들지 않았다는 \(\text{multiset}(A)=\text{multiset}(A0)\)multiset(A)=multiset(A0), 즉 순열 보존(permutation preservation)도 함께 말해야 합니다.

사전조건 반복문 + 불변식 증명 사후조건 = sorted(A) + 원소 보존

증명 공식

답안에 바로 쓸 수 있는 증명 문장

반복 불변식이 나타내는 상태

\[I(j): A[0..j-1] \text{is} \text{sorted}\quad\text{and}\quad \text{multiset}(A[0..j-1]) = \text{multiset}(A0[0..j-1])\]I(j): A[0..j-1] is sorted and multiset(A[0..j-1]) = multiset(A0[0..j-1])

j번째 바깥 반복 직전, 왼쪽 접두 구간이 이미 처리된 구간이라는 뜻입니다.

유지 단계에서 증명할 내용

\[I(j)\quad\text{and}\quad j < n\quad\text{and}\quad \text{body}(j) \text{implies} I(j+1)\]I(j) and j < n and body(j) implies I(j+1)

반복문 본문을 실행해도 다음 반복 직전에 불변식이 다시 참이어야 합니다.

종료 조건에서 얻는 결론

\[I(n)\quad\text{and}\quad \text{not}(j < n) \text{implies} \text{sorted}(A)\quad\text{and}\quad \text{multiset}(A)=\text{multiset}(A0)\]I(n) and not(j < n) implies sorted(A) and multiset(A)=multiset(A0)

반복 조건이 거짓이므로 \(j=n\)j=n이라는 사실을 불변식에 넣으면 전체 배열에 대한 사후조건이 나옵니다.

정확성의 두 부분

\[\text{total} \text{correctness} = \text{partial} \text{correctness} + \text{termination}\]total correctness = partial correctness + termination

부분 정확성(partial correctness)은 “끝난다면 답이 맞다”, 전체 정확성(total correctness)은 “정말 끝나고 답도 맞다”라는 뜻입니다.

삽입 정렬 증명을 그림으로 이해하기

\(j=1\)`j=1`반복 직전

5246

A[0..0]은 정렬되어 있다. 키 A[1]은 아직 삽입하지 않았다.

키 2를 삽입한 뒤

2546

A[0..1]은 정렬되어 있고 이전과 같은 두 원소를 가진다.

종료 단계

2456

\(j=n\)j=n이면 증명된 접두 구간이 전체 배열과 같다.

대화형 시각화

반복 불변식 단계 이동기

삽입 정렬을 단계별로 실행하며 증명된 접두 구간이 커지는 모습을 확인하세요. 강조된 접두 구간이 I(j)가 가리키는 부분입니다.

\(j=1,\)j=1,첫 삽입 직전

A[0..0]은 정렬되어 있으므로 초기화가 성립합니다.

단계별 풀이 예제

초기화 (Initialization)

첫 반복 직전은 \(j=1\)j=1입니다. \(A[0..0]=[5]\)A[0..0]=[5]는 원소 하나짜리 배열이라 자동으로 정렬되어 있고, 원래 접두 구간의 원소 5를 그대로 가집니다. 따라서 I(1)은 참입니다.

유지 (Maintenance/Fortsetzung)

I(j)가 참이라고 가정합니다. 반복문 본문은 \(\text{key}=A[j]\)key=A[j]를 정렬된 접두 구간의 올바른 위치에 넣고, 큰 원소들을 오른쪽으로 한 칸씩 밀 뿐입니다. 순서는 바뀌지만 원소의 다중집합(multiset)은 보존되고, 새 접두 구간 A[0..j]는 정렬됩니다. 따라서 I(j+1)이 참입니다.

종료 (Termination/Terminierung)

반복문이 끝나면 반복 조건이 거짓이므로 \(j=n\)j=n입니다. I(n)은 A[0..n-1], 즉 전체 배열이 정렬되어 있고 원래 원소들을 보존한다는 말입니다. 이것이 사후조건입니다.

객관식 함정과 바로잡기

끝에서만 참이면 불변식인가?

교정: 불변식은 선택한 반복 시점마다 참이어야 합니다. 끝에서만 참이면 사후조건 후보일 뿐입니다.

정렬된 접두 구간만 말하면 충분한가?

교정: 정렬 증명에는 정렬됨과 원소 보존이 함께 필요합니다. 빈 배열도 정렬되어 있을 수 있기 때문입니다.

인덱스 하나 차이 오류: A[0..j]

교정: InsertionSort의 바깥 반복 직전에는 A[j]가 아직 삽입할 키입니다. 처리된 접두 구간은 보통 A[0..j-1]입니다.

종료를 “끝난다”라고만 쓰기

교정: 반복 조건이 거짓이라는 사실이 어떤 수학적 결론을 주는지, 예를 들어 \(j=n\)j=n을 명시해야 합니다.

부분 정확성과 전체 정확성을 같다고 보기

교정: 부분 정확성은 종료를 가정합니다. 전체 정확성에는 종료 증명이 추가됩니다.

너무 강한 불변식

교정: 강한 문장은 좋지만 처음부터 참이 아니거나 반복문 본문이 보존하지 못하면 불변식이 아닙니다.

구두 답안과 능동 회상

반복 불변식과 사후조건의 차이를 한 문장으로 말해 보세요.
InsertionSort의 바깥 반복 직전 I(j)를 정렬 조건과 다중집합 조건으로 말하세요.
초기화에서 왜 A[0..0]이면 충분한가요?
유지 단계에서 키 삽입이 정렬된 접두 구간과 다중집합 보존을 어떻게 유지하나요?
종료 단계에서 반복 조건이 거짓이라는 사실을 왜 반드시 언급해야 하나요?
부분 정확성과 전체 정확성을 정확성(Korrektheit)·종료성(Terminierung)과 연결해서 설명하세요.
새 연습: Minimum(A)의 불변식 “min은 A[0..i-1]의 최솟값이다”를 세 단계로 증명해 보세요.

추가 학습용 AI 프롬프트

Vorlesung/01Introduction.pdf, Übung/AuD26_Sheet01.pdf, Übung/AuD26_Sheet01-Sol.pdf, Übung/AuD26_Sheet01-GrpSol.pdf를 첨부한다. AUD 시험에 맞춰 반복 불변식과 정확성을 한국어로 가르친다. Schleifeninvariante, Vorbedingung, Nachbedingung, Initialization, Maintenance/Fortsetzung, Termination/Terminierung, partial correctness, total correctness 용어는 괄호로 함께 표시한다. I(j): A[0..j-1] 정렬 및 다중집합 보존을 이용해 삽입 정렬을 증명한다. 잘못된 불변식, 인덱스 하나 차이 오류, 반복 조건이 거짓인 종료 상태, 구두 증명 표현을 한 번에 한 문항씩 연습한다.

출처 파일

`Vorlesung\01Introduction.pdf`
`Übung\AuD26_Sheet01.pdf`
`Übung\AuD26_Sheet01-Sol.pdf`
`Übung\AuD26_Sheet01-GrpSol.pdf`
`data\aud_chunks.jsonl`
`data\aud_topic_map.md`

연결 개념 (Related concepts)

후속 튜터 학습 프롬프트

마지막 생성: 2026-08-03 03:24