알고리즘이 존재가능한 모든 입력에 대해 정확하게 동작한다는 사실을 증명할 수 없다. 따라서 알고리즘의 정확한 증명은 각종 수학적인 기법을 기반으로 되야한다.


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



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


귀납법은 크게 3가지로 나뉜다.

  • 단계 나누기 = 증명하고 싶은 사실을 여러 단계로 나눈다.

  • 첫 단계 증명 = 첫 단계에서 증명하고 싶은 내용이 성립함을 보인다. 

  • 귀납 증명 = 첫 단계에서 증명하고 싶은 내용이 성립하면, 다음 단계에서도 성립함을 보인다.

알고리즘은 어떠한 형태로든 반복적인 요소를 가지고 있기 때문에, 귀납법은 알고리즘의 정당성을 증명할 때 가장 유용하게 사용되는 기법.


반복문 불변식 = 반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는지..


불변식을 이용한 반복문의 정당성은 다음과 같이 증명한다


  • 반복문 진입시에 불변식이 성립함을 보인다.

  • 반복문 내용이 불변식을 깨뜨리지 않음 보인다. 시작할 때 불변식이 성립하면, 끝에서도 성립한다

  • 반복문 종료시에 불변식이 성립하면 항상 우리가 정답을 구했음 보인다.

*불변식이 깨졌을 때 프로그램을 강제 종료함으로써 알고리즘에 문제가 있는지 없는지를 판단할 수 있다. 다만 엄청나게 많이 실행되는 반복문 안에 단정문을 배치하는 것은 삼가는 것이 좋다.


귀류법



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


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


비둘기집의 원리



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




'3학년 > 알고리즘' 카테고리의 다른 글

6장 알고리즘 설계 패러다임  (0) 2018.11.22
5장 알고리즘의 정당성 증명  (0) 2018.11.22
문제 해결 전략 질문들  (0) 2018.11.16
백준 알고리즘 2294번  (0) 2018.01.16
백준 알고리즘 2870번  (0) 2018.01.15
백준 알고리즘 1003번  (0) 2018.01.15

+ Recent posts