알고리즘의 정당성 증명들 (귀납법, 귀류법, 비둘기집의 원리, 순환소수 찾기, 구성적 증명)

귀납법

귀납(歸納, induction)은 개별적인 특수한 사실이나 현상에서 그러한 사례들이 포함되는 일반적인 결론을 이끌어내는 추리의 방법이다

 

귀납법을 이용해 우리는 다음과 같이 반복문의 정당성을 증명할 수 있다

 

1. 초기 조건 : 반복문 진입시에 불변식이 성립함을 보인다

2. 유지 조건 : 반복문 내용이 불변식을 깨뜨리지 않음을 보인다

3. 반복문 종료시에 불변식이 성립하면 반복문이 항상 정답을 구함을 보인다

 

예시로 이진 탐색으로 반복문 불변식을 살펴보자

snupi.tistory.com/62

[Java code] 이진 탐색(binary search) - 선형 이하 시간(sublinear time) 알고리즘

public static int binSearch(int[] arr, int x) {
	int n = arr.length;
	int lo = -1, hi = n, mid;
    
	while(lo+1 < hi) {
		mid = (lo+hi)/2;
        
		if(arr[mid] < x)
			lo = mid;
		else
			hi = mid;
	}
	return hi;
}

 

1. 초기 조건

while문이 시작할 때 lo, hi는 각각 -1, n으로 초기화된 상태이다

n = 0이라면 while문을 건너뛰기 때문에 불변식 1은 항상 성립한다

arr[-1] = 음의 무한, arr[n] = 양의 무한이라고 가정하므로 불변식 2 또한 항상 성립한다

 

2-1. 불변식 1

while 내부에서 lo와 hi는 차이가 2 이상이므로 mid는 항상 두 값 사이에 위치한다

따라서 mid를 어디에 대입하건 불변식 1은 항상 성립한다

 

2-2. 불변식 2

- arr[mid] < x인 경우 : arr[mid] < x ≤ arr[hi]이므로, lo에 mid를 대입해도 불변식은 성립한다

- x ≤ arr[mid]인 경우 : arr[lo] < x ≤ arr[mid]이므로, hi에 mid를 대입해도 불변식 2는 성립한다

 

---

 

귀류법

귀류법은 수학이나 자연과학에서 애호되는 논증법의 하나이다. 위의 귀류법은 한 명제 A의 부정으로부터 모순을 끌어내어 A의 부정이 옳지 않다는 것을 증명한다. 즉, A가 성립함(참)을 말해 주는 증명 방법이다. 이때 증명의 최종목적은 A의 증명에 있으며, 직접적으로는 A를 증명하지 않고, 우선 귀류법에 의하여 A의 부정을 부정하는 것을 시도해 보는 간접적인 방법을 사용한다.

 

귀류법은 대게 어떤 선택이 항상 최선임을 증명하고자 할 때 많이 이용된다

우리가 선택한 답보다 좋은 답이 있다고 가정한 후에, 그런 일은 있을 수 없음을 보이면 최선의 답을 선택했음을 보일 수 있기 때문이다

 

---

 

비둘기집의 원리

이 원리는 '비둘기 일곱 마리가 여섯 개의 집에 들어 있으면 비둘기가 두 마리 또는 그 이상 들어 있는 집이 적어도 하나 있다.'는 것이다

 

예를 들어 순환 소수 찾기가 있다

a/b 분수를 실수 연산을 쓰지 않고 소수 형태로 출력하려 한다고 하자

그런데 이 소수가 무한 소수라는 사실을 어떻게 알 수 있을까?

 

이는 비둘기집의 원리로 쉽게 해결할 수 있다

소수를 구할 때에 a%b 연산에서 결과는 언제나 [0, b-1]임을 알 수 있다

따라서, 순환소수는 b가지의 결과만 가질 수 있으니 소수 b자리 전에 결과가 중복되는 경우가 반드시 있게 된다

 

---

 

구성적 증명(Constructive Proof)

구성적 증명(構成的證明, constructive proof)은 일정 조건을 만족하는 대상의 존재성(존재 정리)을, 그 대상을 구체적으로 만들어내어 증명하는 방법이다

 

이는 흔히 우리가 원하는 어떤 답이 존재한다는 사실을 증명하기 위해서 사용된다

위의 방법들과는 다르게, 답의 실제 예를 들거나 답을 만드는 방법을 실제로 제시하는 증명이다

 

예로는 안정적 결혼 문제가 있다

이는 다음과 같다

---

n명의 남성과 여성이 단체 미팅에서 만났다

모든 사람은 자신이 원하는 상대방의 우선순위를 마음 속에 정했다

가능한 우선순위가 높은 이성끼리 짝지어질 수 있도록 하는 방법이 항상 존재할까?

​

알고리즘은 다음과 같다

 

ㅡ

1.

여성들이 모두 자신이 가장 선호하는 남성의 앞에 가서 프로포즈를 합니다. 남성이 그 중 가장 마음에 드는 여성을 고릅니다.

선택받지 못한 여성들은 제 자리로 돌아갑니다.

​

2.

짝을 갖지 못한 여성들은 다음으로 가장 우선순위가 높은 남성에게 다가가 프로포즈합니다. 남성들은 짝이 있더라도 가장 마음에 드는 여성을

고릅니다.

​

3.

더 프로포즈할 여성이 없을 때까지 2번 항복을 반복합니다.

ㅡ

 

이 알고리즘들이 우리가 원하는 답을 구할 수 있음을 보이려면 다음 세 가지를 증명해야 한다

 

- 종료 증명

여성들은 퇴짜 맞을 때마다 우선순위가 더 낮은 남성에게 프로포즈하기 때문에,

각 여성이 최대 n명의 남성들에게 프로포즈한 이후엔 더 이상 프로포즈할 남성이 없으므로 이 과정은 언젠가 반드시 종료한다

​

- 모든 사람들이 짝을 찾는지 증명

프로포즈를 받은 남성은 그 중 한사람을 반드시 선택하기 때문에 프로포즈를 받은 남성은 반드시 짝이 있다

귀류법을 적용하여 짝을 찾지 못한 남, 녀가 있다고 가정하자

하지만 여성은 우선순위가 높은 순서대로 한 번씩 프로포즈 하기 때문에,

짝을 찾지 못한 그 남성에게도 한 번은 프로포즈 했어야 하고, 남성은 프로포즈를 받아들였어야 한다

따라서 가정에 모순이 발생한다

​

- 짝들의 안정성

또한 귀류법으로 증명한다

결과적으로 짝이아닌 두 남녀가 서로 자신의 짝보다 상대방을 선호한다고 가정하자

하지만 여성은 지금 자신의 짝 이전에 그 남성에게 반드시 프로포즈했어야 하기 때문에, 프로포즈 받았던 여성과 마음에 들지 않는 여성과 최종적으로 짝이 되는 경우는 생길 수 없다

따라서 가정에 모순이 발생한다

 

---