구종만님의 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"을 기반으로 공부한 내용입니다.
📕 목차

1. 수학적 귀납법과 반복문 불변식
2. 귀류법
3. 다른 기술들

1. 수학적 귀납법과 반복문 불변식

 

• 수학적 귀납법(mathematical induction)
• 반복문 불변식(loop invariant)
• 이진 탐색과 반복문 불변식
• 삽입 정렬과 반복문 불변식
• 단정문을 이용해 반복문 불변식 강제하기

 

📌 수학적 귀납법(mathematical induction)
  • 반복적인 구조를 갖는 명제들을 증명하는데 유용하다.
  • 귀납법 증명은 크게 3단계로 나눈다.
    1. 단계 나누기
      • 증명하고 싶은 사실을 여러 단계로 나눈다.
      • ex1. 100개의 도미노가 순서대로 있다.
      • ex2. 텅 빈 N개의 세로줄에서 가로 줄을 하나 긋는 것을 한 단계로 친다.
    2. 첫 단계 증명
      • 첫 단계에서 증명하고 싶은 내용이 성립함을 보인다.
      • ex1. 첫 번째 도미노는 직접 손으로 밀어서 쓰러뜨린다.
      • ex2. 텅 빈 N개의 세로줄에서 항상 맨 위/맨 아래 선택지가 1:1 대응이 된다.
    3. 귀납 증명
      • 다음 단계에서도 성립함을 보인다.
      • ex1. 한 도미노가 쓰러지면 다음 도미노 역시 반드시 쓰러진다.
      • ex2. 가로줄을 하나 그어서 세로줄을 연결해도 1:1 대응 속성이 유지된다.

 

📌 반복문 불변식(loop invariant)
// (*) 불변식은 여기서 성립해야 한다.
while (조건식) {
    // 반복 내용 시작
    ...
    // 반복 내용 끝
    // (**) 불변식은 여기서도 성립해야 한다.
}
  • 반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는 길에 잘 있는지를 명시하는 조건
  • 원하는 결과를 얻기 위해서는 반복문이 항상 식이 변하지 않고 성립해야 한다.
  • 불변식을 이용한 반복문 정당성 증명
    1. 반복문 진입시에 불변식 성립을 보인다.
    2. 반복문 내용이 불변식을 깨뜨리지 않음을 보인다. 시작할 때 불변식이 성립했다면 끝날 때도 불변식이 항상 성립함을 보여야 한다.
    3. 반복문 종료시에 불변식이 성립하면 항상 정답을 구했음을 보인다.

 

📌 이진 탐색과 반복문 불변식
// 코드 5.1 이진 탐색

// 필수 조건: A는 오름차순으로 정렬되어 있다
// 결과: A[i-1] < x ≤ A[i]인 i를 반환한다
// 이때 A[-1] = -∞, A[n] = +∞라고 가정한다
int binarySearch(const vector<int>& A, int x) {
    int n = A.size();
    int lo = -1, hi = n;
    // 반복문 불변식 1: lo < hi
    // 반복문 불변식 2: A[lo] < x ≤ A[hi]
    // (*) 불변식은 여기서 성립해야 한다.
    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        if (A[mid] < x)
            lo = mid;
        else
            hi = mid;
        // (**) 불변식은 여기서도 성립해야 한다. 
    }
    return hi;
}

불변식이 while 종료까지 성립했다고 가정하자.

  • lo + 1 = hi : while문이 종료했으니 lo + 1 ≥ hi인데, 불변식에 의해 lo < hi이므로 lo + 1 = hi일 수밖에 없다.
  • A[lo] < x ≤ A[hi] : 애초에 불변식이 성립한다고 가정했으므로, 당연히 참이다.

따라서 우리가 원하는 결과값 i는 언제나 hi라는 답을 반환한다. (정당성 증명)

 

🟡 전체 작업을 단계로 나누어 보기

  1. 초기 조건
    • while문이 시작할 때, lo와 hi는 각각 -1과 0으로 초기화된 상태
    • n=0이라면 while문이 실행 안 되므로 불변식 1은 언제나 참
    • A[-1]과 A[n]을 각각 음/양의 무한대로 가정했으므로 불변식 2도 참
  2. 유지 조건 : while 내부가 불변식을 깨뜨리는가?
    • 불변식1
      • while 문 내부로 들어왔다면 hi와 lo 차이가 2 이상이라는 의미
      • mid는 언제나 두 값의 사이에 위치하므로 불변식이 유지된다.
    • 불변식2
      • A[mid] < x : x≤A[hi]는 반복문 시작할 때 참이으므로, A[mid]<x≤A[hi]도 성립한다. 따라서 lo에 mid를 대입해도 불변식은 언제나 성립
      • x ≤ A[mid] : 위와 반대로 생각해보면 hi에 mid를 대입해도 불변식 2는 언제나 성립한다.

 

📌 삽입 정렬과 반복문 불변식
// 코드 5.2 (불변식이 추가된) 삽입 정렬 알고리즘

void insertionSort(vector<int>& A) {
    for (int i = 0; i < A.size(); ++i) {
        // 불변식 a: A[0..i-1]는 이미 정렬되어 있다.
        // A[0..i-1]에 A[i]를 끼워넣는다.
        int j = i;
        while (j > 0 && A[j - 1] > A[j]) {
            // 불변식 b: A[j+1..i]의 모든 원소는 A[j]보다 크다.
            // 불변식 c: A[0..i] 구간은 A[j]를 제외하면 정렬되어 있다.
            swap(A[j - 1], A[j]);
            j--;
        }
    }
}
  1. 초기 조건
    • 반복문이 시작할 때 i=0이면 해당 구간은 비어 있으니 항상 정렬되어 있다고 가정할 수 있다.
  2. 불변식 유지
    • for문의 내용이 종료할 때, 이 불변식이 깨지지 않고 유지됨을 보이려면 while문 정당성 증명이 필수적이다.
    • while문 정당성 증명은 불변식 (b)와 (c)를 통해 증명할 수 있다.
      • j=0이면, 불변식 (b)에 의해 A[j]가 A[0..i] 구간 중 가장 작은 수가 된다. 불변식 (c)와 합쳐 보면 A[0..i] 구간 전체가 정렬되었음을 알 수 있다.
      • j>0 && A[j-1] ≤ A[j] 라면, 불변식 (b)와 합쳐 A[j-1] ≤ A[j] < A[j+1]가 된다. 불변식 (c)와 합쳐 보면 A[0..i] 구간 전체가 정렬되었음을 알 수 있다.

 

🟡 (b)와 (c)가 항상 성립함을 증명하기

  • (b) 초기 조건 : while문 진입 시 A[j+1 ⋯ i] 구간은 빈 구간이므로 (b)는 참이다.
  • (b) 유지 조건 : while문 내용 실행되었다는 말은 A[j-1]>A[j]이므로, 이 둘을 교체하고 j를 1 줄여도 (b)는 여전히 참이다.
  • (c) 초기 조건 : 불변식 (a)에 의해 A[0 ⋯ i-1]는 정렬되었으므로 while문 진입 시에 (c)는 언제나 참이다.
  • (c) 유지 조건 : A[j]와 이전 원소를 swap해도 상대적 순서는 변하지 않으므로 (c)는 언제나 참이다.

위 증명은 while문이 언제나 A[0 ⋯ i]를 정렬된 상태로 남겨둔다는 것을 보여준다.

 

📌 단정문을 이용해 반복문 불변식 강제하기

불변식이 깨졌을 때, 단정문으로 프로그램을 강제 종료하는 코드를 추가하면 좋을 것이다.

다만, 속도에 지장을 주므로 반복횟수가 많은 곳에 단정문을 배치하는 것은 삼가하라.

 

2. 귀류법

 

• 귀류법
• 책장 쌓기
• 귀류법을 이용한 증명들

 

📌 귀류법

source에서 sink까지 운행하는 열차가 조금이라도 더 많은 손님을 태우기 위해, 몇몇 승객을 쫓아내야 한다고 가정하자.

쫓아내는 사람의 수를 최소화하고 싶다면, 가장 멀리 가는 사람들을 쫓아내는 것이 현명하다.

왜 그럴까?

 

가장 멀리 가는 사람(이하 A)을 내쫓지 않고, 도중에 내리는 사람(이하 B)을 쫓아냈다고 가정해보자.

A대신 B를 쫓아냈을 때, 쫒겨나는 사람의 수가 더 적을 수가 있을까? 그런 일은 불가능하다.

B는 어차피 가만히 냅두었어도 도중에 내렸을 승객이므로, 그 뒤에 변화가 없을 수는 있지만 적어도 다른 승객이 탈 수 있는 가능성은 있었다.

하지만 A는 긴 시간 동안 자리를 차지하고 있으므로 그만큼 더 많은 승객을 태울 수 있을 기회가 적다.

 

알고리즘에서 귀류법이란 대개 우리가 선택한 답보다 좋은 답이 있다고 가정한 후에, 그 가정이 거짓임을 보이는 것이다.

 

📌 책장 쌓기

🟢 문제 상황

  • 각 책장의 버틸 수 있는 무게 \(M_{i}\), 자신의 무게 \( W_{i} \)
  • 책장을 가장 높이 쌓으려면 어떻게 해야 할까?
  • 단, \( \sum_{j \in above(i)}W_{j} \leq M_{i} \)
  • 가장 무거운 책장을 기준으로 정렬하는 것이 최선일까, 가장 튼튼한 책장을 기준으로 정렬하는 것이 최선일까?

 

🔴 정답

  • 견딜 수 있는 최대 무게와 자신의 무게 합인 \(M_{i} + W_{i}\)를 기준으로 정렬하는 것이 최선이다.

 

🔵 증명

  1. \(M_{i} + W_{i}\)가 더 큰 A가 B 위에 쌓여있는 구조라고 가정하자. (기존 가정과는 반대 상황)
  2. 이 둘의 위치가 언제나 바뀔 수 있다고 가정하자. 그러면 \(M_{i} + W_{i}\)가 큰 것이 밑에 가도록 쌓아도 최선의 답을 얻을 수 있다는 증거가 된다.
    • B는 애초에 밑에 있었으니, 위로 당연히 올라갈 수 있다.
    • A는 기존 무게 + B의 무게를 견딜 수 있을까? (증명 시작)
  3. \(M_{A} + W_{A} > M_{B} + W_{B}\)에서 A의 무게를 우변으로 이항하면 \(M_{A}  > M_{B} + W_{B} - W_{A}\)
  4. (1)의 가정에 의해 \(M_{B} \geq W_{A} + X\)가 성립하므로, \(M_{A}  > M_{B} + W_{B} - W_{A} \geq (W_{A} + X) + W_{B} - W_{A} \)
  5. \( M_{A} > X + W_{B} \), 따라서 A도 B와 나머지 모든 상자들을 지탱할 수 있음을 보인다.
  6. \(M_{i} + W_{i}\)를 기준으로 쌓았을 때 가장 높은 탑을 얻지 못하는 경우는 존재하지 않는다.

 

📌 귀류법을 이용한 증명들

알고리즘 결과가 최선(최단 경로, 가장 높은 탑)임을 보이기 위해 각 단계에서 최선의 선택을 함을 귀류법으로 증명하고, 각 단계에서 최선의 선택을 한다면 다음 단계에서도 최선의 선택을  할 수 있음을 귀납법으로 증명할 수 있다.

 

3. 다른 기술들

 

• 비둘기집의 원리
• 동전 뒤집기
• 순환 소수 찾기
• 구성적 증명
• 안정적 결혼 문제

 

📌 비둘기집의 원리(Pigeonhole Principle)
10마리의 비둘기가 9개의 비둘기 집에 모두 들어갔다면, 2마리 이상이 들어간 비둘기 집이 반드시 하나는 있게 마련이다.

얼핏 보면 대답하기 힘든 질문에 대해 대답하는 데 유용하게 쓰인다.

 

서울 시민 중에 머리털 개수가 정확히 같은 두 사람이 존재할 수 있을까?

서울 인구를 1000만 명으로 가정하고, 평균 머리털 개수가 10만 가닥인데, 가장 많은 사람이 100만 가닥이라 가정하자.

천만 마리의 비둘기가 백만 개의 비둘기 집에 들어갔다면, 반드시 같은 비둘기 집에 들어간 비둘기가 두 마리 이상 있기 마련이다.

 

따라서 머리털 개수가 정확히 같은 두 사람은 반드시 존재한다.

 

📌 동전 뒤집기

100개의 동전이 F개는 앞면, 100-F개는 뒷면이 위로 놓여져 있다.

동전들을 모두 앞면으로 뒤집고 싶은데, 한 번 뒤집을 때 반드시 X개의 동전을 한꺼번에 뒤집어야 한다. (같은 동전을 두 번 이상 뒤집어도 상관없다.)

뒤집는 횟수를 최소화하고 싶을 때 답의 상한은 얼마인가?

 

정답은 100이다.

  1. 동전을 한 번 뒤집을 때마다 보이는 앞면의 개수를 적는다 치자.
  2. 동전을 101번 뒤집었다면 F까지 합쳐 102개의 숫자를 적게 된다.
    • 앞면의 개수는 0부터 100까지 101가지 값만을가질 수 있다.
    • 비둘기집 원리에 따라 중간에 반드시 중복이 발생할 수밖에 없으므로 최선이 아니다.

 

✒️ 100개의 동전 중 앞면이 보이는 동전 57개가 있고, 한 번에 2개의 동전만 뒤집을 수 있다면?

귀납법으로 해결할 수 있다.

초기 상태에서 F = 57이므로 홀수이다. (불변식 성립)
한 번에 2개의 동전을 뒤집을 때, 앞면의 수는 여전히 홀수다. (불변식 성립)
따라서 앞면의 수 T는 언제나 홀수로 유지되므로 100개(짝수)가 될 수가 없다.

 

📌 순환 소수 찾기
// 코드 5.3 순환 소수 찾기

// 분수 a/b의 소수 표현을 출력한다.
// a >= 0, b > 0이라고 가정한다
void printDecimal(int a, int b) {
    int iter = 0;
    while (a > 0) {
        // 첫 번째와 두 번째 사이에 소수점을 찍는다.
        if (iter++ == 1) cout << '.';
        cout << a / b;
        a = (a % b) * 10;
    }
}

분수 a/b가 주어질 때 실수 연산을 쓰지 않고, 분수를 소수 형태로 출력하려 한다고 하자.

무한 소수인 경우를 걸러내려면 어떻게 해야할까?

 

비둘기집의 원리를 사용해 쉽게 해결할 수 있다.

a%b의 결과는 언제나 [0, b-1]의 범위의 값을 가지므로, while문이 b+1번 반복될 때까지 함수가 종료하지 않았다고 가정하자.

a%b 결과는 b가지 결과만 가질 수 있으므로 결과가 중복되는 경우가 반드시 존재한다.

그 말은 즉슨, 같은 결과가 두 번째 등장할 때까지가 무한히 순환되는 순환 소수임을 알 수 있다.

 

📌 구성적 증명(constructive proof)
  • 우리가 원하는 어떤 답이 존재한다는 사실을 증명하기 위해 사용
  • 실제 예를 들거나 답을 만드는 방법을 제시하는 증명
  • 하늘을 나는 교통 수단을 증명하는 경우
    • 비구성적 증명: 양력의 법칙, 지구의 공기 밀도, 사용 가능한 재료 강도와 탄성들을 열거
    • 구성적 증명: 비행기를 만듦, 비행기를 만드는 법이 적힌 설명서 제시

 

📌 안정적 결혼 문제(Stable marriage problem)

언제나 서로를 더 선호하는 사람끼리 매칭해줄 수 있는가?

 

  1. 처음에는 여성들이 모두 자신이 가장 선호하는 남성의 앞에 가서 프로포즈를 한다. 남성이 제일 마음에 드는 여성을 고르면 나머지는 퇴짜를 맞고 제 자리로 돌아간다.
  2. 퇴짜를 맞은 여성들은 (상대의 짝의 여부와 상관없이) 다음으로 마음에 드는 남성에게 프로포즈를 한다. 남성들은 현재 자기 짝보다 더 맘에 드는 여성이 다가왔다면, 지금의 파트너에게 퇴짜를 놓고 새 여성에게 넘어간다.
  3. 더 프로포즈할 여성이 없을 때까지 반복한다. (미친 알고리즘이네)

 

1️⃣ 종료 증명

  • 여성은 퇴짜를 맞을 때마다 우선 순위가 낮은 남성에게 찾아간다.
  • 각 여성이 최대 n명의 남성들에게 순서대로 프로포즈한 이후엔 더이상 프로포즈할 남성이 없다.
  • 따라서 이 과정은 언젠가 반드시 종료된다.

 

2️⃣ 모든 사람들이 짝을 찾는지 증명

  • 프로포즈를 받은 남성은 반드시 한 사람을 선택한다.
  • 우선 순위가 높은 여성이 프로포즈해야 짝을 바꾸므로, 한 번이라도 프로포즈 받은 남성은 항상 짝이 있다.

 

3️⃣ 짝들의 안정성

  • 짝이 아닌 두 남녀가 서로 자신의 짝보다 상대방을 선호하는 경우
  • 여성은 반드시 현재 짝 이전에 그 남성에게 프로포즈 했어야 한다.
  • 그러나 매칭이 안 됐다면 해당 남성에게 우선순위가 밀렸다는 의미가 된다.
  • 남성은 더 맘에 드는 여성이 나타났을 때만 짝을 바꾸므로, 프로포즈 받았던 여성보다 맘에 들지 않는 여성과 최종적으로 짝이 되는 일은 없다.
저작자표시 비영리

티스토리툴바