알고리즘 문제 해결 전략 1권 4.6 수행 시간 어림짐작하기

프로그램의 동작 속도에 영향을 끼치는 요소는 입력의 크기와 시간 복잡도를 제외하고도 엄청나게 많음. 

1억이라는 기준은 가능한 한 보수적으로 정한 것임

 

4.7 계산 복잡도 클래스 : P, NP, NP-완비

일반적으로 다항 시간 알고리즘이나 그보다 빠른 알고리즘들을 빠르다고 말합니다

P문제처럼 같은 성질을 갖는 문제들을 모아놓은 집합을 계산 복잡도 클래스라고 부릅니다. 

다항 시간 알고리즘이 존재하는 문제와 존재하지 않는 문제로 문제들을 구분하기란 어렵습니다.

주어진 배열을 비교 정렬하는 문제와 최소치를 찾는 문제의 난이도를 비교하면, 정렬 문제는 최소치 문제 이상으로 어렵다고 말할 수 있습니다.

 

NP문제란 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제를 의미합니다.

이런 속성을 갖는 문제들의 집합을 NP-난해 문제라고 부릅니다. NP-난해 문제이면서 NP인 문제들을 NP-완비 문제라고 합니다. 

 

chapter 05 알고리즘의 정당성 증명

5.1 도입

이 장에서 다루는 기법들은 작성하는 프로그램의 정당성을 평가하는 데도 유용하게 쓰임

증명을 이해하는 편이 알고리즘을 사용하는 입장에서도 더 큰 공부가 됨

다른 알고리즘들의 증명을 공부하다 보면 나중에 자신이 설계한 알고리즘의 정당성을 더 쉽게 증명할 수 있다는 것도 또 다른 이유임. 많은 증명을 직접 따라해 보면 처음 보는 알고리즘이 과연 잘 동작할지, 그리고 어떻게 그것을 증명해야 할지에 대해 어렴풋이 알 수 있는 직관 같은 것이 생기기 때문임.

 

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

귀납법을 이용해 알고리즘의 정당성을 증명할 때는 반복문 불변식이라는 개념이 유용하게 쓰임. 

while문 종료시에 항상 성립한다는 것을 보일 수 있다면 이 알고리즘의 정당성은 증명한 셈임.

반복문 불변식은 이와 같이 알고리즘의 정당성을 증명하기 위한 좋은 도구임

 

5.3 귀류법

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

 

5.4 다른 기술들

while문이 b+1번 반복될 때까지 함수가 종료하지 않았다고 합시다. a%b의 결과는 b가지의 결과만 가질 수 있으니 결과가 중복되는 경우가 반드시 있겠지요. 그러면 같은 결과가 첫 번째로 등장했을 떄부터 두 번째 등장할 때까지가 무한히 순환되는 순환 소수임을 알 수 있습니다.