[알고리즘 문제 해결 전략] 02 알고리즘 분석 - 알고리즘의 정당성 증명review

도입

단위 테스트는 알고리즘에 문제가 있음을 증명할 수 있지만 없음을 증명할 수 없다.

알고리즘의 정확한 증명을 위해서는 각종 수학적인 기법이 동원되어야 한다.

알고리즘 증명을 공부해야 하는 이유 : 증명이 알고리즘을 유도하는 데 결정적인 통찰을 담고 있기 때문.

 

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

수학적 귀납법 : 반복적인 구조를 갖는 명제들을 증명하는 데 유용하게 사용되는 증명 기법

단계 나누기 -> 첫 단계 증명 -> 귀납 증명

반복문 불변식 (loop in - variant ) : 반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지 명시하는 조건

이진 탐색에서

int binsearch (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문안에 들어왔다-> hi와 lo 차이가 2 이상 난다. ->mid는 항상 두 값 사이 (만약 1 차이 난다면 mid는  lo이다.)

lo=mid , hi=mid 둘 중 아무것을 해도 불변식 1 유지

A [mid]<x 인 경우 ->  x≤A [hi] , A [mid] < x ≤ A [hi] , lo <mid이므로   A [lo]<x≤A [hi]  도 성립

A [mid]>x 인 경우 ->  A [lo]≤ x ] , A [lo] <x ≤ A [mid] , mid <hi이므로   A [lo]<x≤A [hi]  도 성립

 

삽입 정렬과 반복문 불변식

불변식 a: A [0.. i-1]은 이미 정렬되어 있다.

불변식 b:A [j+1.. i]의 모든 원소는 A [j]보다 크다. (while문 안에서)

(초기 조건이 이해가 잘 안 간다) (A [j-1]>A [j]이니까 이 둘을 swap 하고 j를 1줄이면 b는 계속 참이 된다.)

불변식 c:A [0.. i] 구간은 A [j]를 제외하면 정렬되어 있다. (while 문 안에서)

불변식 b, c를 통해 a가 성립함을 보임

 

이해가 될 듯 말 듯하다.

귀류법

우리가 원하는 바와 반대되는 상황을 가정하고 논리를 전개해서 결론이 잘못됐음을 찾아내는 증명 기법.

책장 쌓기 

     M  W             Ma+ Wa > Mb+Wa 보다 큰 상황  

A   6   6

B   7   4

A가 B위에 올라갈 수 있다는 것은 Mb ≥ Wa + x(x는 A위에 올라가 있는 상자들의 무게의 합) 

(B가 들 수 있는 무게가 A 보다 더 크다면 본인의 무게는 크 차이보다 작아야 위의 상황이 성립한다.)

즉 Mb와 Wa의 차이보다 Ma와 Wb의 차이는 항상 크거나 같다. 그러므로 다음식이 성립한다.

Ma> x + Wb

그렇게 때문에 우리가 원하는 W+M의 순서대로 답을 쌓았을 때 가장 높은 탑을 얻지 못하는 경우는 존재하지 않는다.

순환 소수 찾기

무한 소수라는 사실을 인식하는 방법은 비둘기집의 원리를 쓰면 된다.

a=(a% b)*10에서 a% b는 언제나 0~b-1 사이의 값이다. 그렇게 때문에 이 결과가 b가지 보다 많게 되면 중복되는 경우가 생긴 것이다. 즉  무한히 순환되는 소순환 소수이다.

책 : 알고리즘 문제 해결 전략

저자 : 구종만

 

어려운 내용이 많았는데 천천히 예시를 들었을 때 이해되는 것이 있고 모호한 것이 있었다.

반복문 불변식이 너무 어려웠다. 

문제를 풀 때 항상 반복문에서 조건이 성립하는 경계를 정하는 것이 어려웠는데

반복문 불변식을 이해하면 문제를 풀기 더  좋아질 것 같아서 다음에 또 복습해야겠다.