5장: 알고리즘의 정당성 증명 - 1 (127p ~ 142p)

<도입>

1. 알고리즘의 정당성 증명

1. 알고리즘의 증명을 공부해야 하는 가장 큰 이유는 많은 경우 증명이 알고리즘을 유도하는 데 결정적인 통찰을 담고 있으며 결정적으로 필요한 깨달음이 증명에 담겨 있는 경우가 많기 때문이다.
2. 알고리즘의 증명을 공부하면 자신이 설계한 알고리즘의 정당성을 더 쉽게 증명할 수 있다.

 

<수학적 귀납법과 반복문 불변식>

1. 수학적 귀납법(mathematical induction)

• 단계 나누기: 증명하고 싶은 사실을 여러 단계로 나눈다.
• 첫 단계 증명: 첫 단계에서 증명하고 싶은 내용이 성립함을 보인다.
• 귀납 증명: 한 단계에서 증명하고 싶은 내용이 성립한다면, 다음 단계에서도 성립함을 보인다.

2. 반복문 불변식(loop invariant)

1. 반복문 진입시에 불변식이 성립함을 보인다.
2. 반복문 내용이 불변식을 깨뜨리지 않음을 보인다.
3. 반복문 종료시에 불변식이 성립하면 항상 우리가 정답을 구했음을 보인다.

• ex) 이진 탐색에서 초기 lo=-1, hi=n으로 잡음으로써 lo<hi, A[lo]<x<=A[hi]이고 이 불변식이 반복문 속에서 계속 유지되므로 lo+1=hi, A[lo]<x<=A[hi]임을 알 수 있다.

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

• 반복문에 단정문을 추가하면 해당 불변식이 깨졌을 때 프로그램이 강제 종료되므로 불변식의 유지에 문제가 있다는 것을 알 수 있다.

 

<귀류법>

1. 정의

• 원하는 바와 반대되는 상황을 가정하고 논리를 전개해서 결론이 잘못됐음을 찾아내는 증명 기법을 귀류법이라고 한다.
• 귀류법은 어떤 선택이 항상 최선임을 증명하고자 할 때 많이 이용된다. 우리가 선택한 답보다 좋은 답이 있다고 가정한 후에, 사실은 그런 일이 있을 수 없음을 보이면 우리가 최선의 답을 선택했음을 보일 수 있기 때문이다.

2. 책장 쌓기

• 버틸 수 있는 최대 무게 Mi, 자신의 무게 Wi가 있다.
• Mi + Wi가 큰 것 부터 아래에 놓아야 한다. 는 명제를 증명하자. Ma + Wa > Mb + Wb인데 a가 b위에 있다. 이때 a와 b의 위치를 바꿔도 됨을 보이자. Ma > Mb + Wb - Wa이다.
• a가 b위에 있으므로 Mb >= Wa + X이다. 따라서 Ma > Mb + Wb - Wa >= Wb + X
• 따라서 a와 b의 위치를 바꿀 수 있다. 따라서 Mi + Wi가 큰 것부터 아래에 쌓았을 때 가장 높은 탑을 얻지 못하는 경우는 존재하지 않음을 보일 수 있다.

 

<다른 기술들>

1. 비둘기집의 원리(Pigeonhole Principle)

• 정의: 10마리의 비둘기가 9개의 비둘기집에 모두 들어갔다면, 2마리 이상이 들어간 비둘기집이 반드시 하나는 있다.

2. 동전 뒤집기

• 100개의 동전이 바닥에 깔려 있는데 X개의 동전을 뒤집는 행위를 최소한 하여 모두 앞면을 위로 하려고 한다. 이때 답의 상한은 100이다. 앞면의 개수가 될 수 있는 것은 1~100 임으로 101번 뒤집으면 비둘기집의 원리에 따라 중간에 반드시 중복이 발생하므로 이 답은 최선의 답이 아니기 때문이다.

3. 구성적 증명(constructive proof)

• 답이 존재한다는 사실을 논증하는 것이 아닌 답의 실제 예를 들거나 답을 만드는 방법을 실제로 제시함으로써 증명하는 방법

4. 안정적 결혼 문제

• 종료 증명: 각 여성은 퇴짜 맞을 때마다 지금까지 프로포즈했던 남성들보다 우선순위가 낮은 남성에게 프로포즈한다. n명의 남자에게 모두 프로포즈한 이후엔 더 이사 프로포즈할 남성이 없으므로 이 과정은 반드시 종료한다.
• 모든 사람들이 짝을 찾는지 증명: 남성은 우선순위가 높은 여성을 선택함으로 프로포즈를 받았다면 항상 짝이 존재해야 한다. 귀류법을 적용하여 남녀 한 사람씩 짝을 찾지 못했다고 가정하자. 여자는 이 남성에게 한 번 프로포즈하여 남성은 짝이 있어야 하므로 모순이다. 따라서 짝을 찾지 못하는 사람은 있을 수 없다.
• 짝들의 안정성: 이 과정의 결과로 짝을 지었는데 짝이 아닌 두 남녀가 서로 자신의 짝보다 상대방을 더 선호한다고 가정하자. 여성은 지금 자신의 짝 이전에 그 남성에게 프로포즈했어야 됐고 그런데도 짝지어지지 않은 것은 더 맘에 드는 여성에게 프로포즈를 받았기 때문이다. 남성은 더 맘에 드는 여성이 나타났을 때만 짝을 바꾸므로, 프로포즈 받았던 여성보다 맘에 들지 않는 여성과 최종적으로 짝이 되는 일은 없다. 따라서 짝이 아닌 두 남녀가 서로 자신의 짝보다 상대방을 더 선호할 수는 없다.

 

 

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.