알고리즘의 정당성 증명1 [알고리즘 문제 해결 전략] 02 알고리즘 분석 - 알고리즘의 정당성 증명review 도입 단위 테스트는 알고리즘에 문제가 있음을 증명할 수 있지만 없음을 증명할 수 없다. 알고리즘의 정확한 증명을 위해서는 각종 수학적인 기법이 동원되어야 한다. 알고리즘 증명을 공부해야 하는 이유 : 증명이 알고리즘을 유도하는 데 결정적인 통찰을 담고 있기 때문. 수학적 귀납법과 반복문 불변식 수학적 귀납법 : 반복적인 구조를 갖는 명제들을 증명하는 데 유용하게 사용되는 증명 기법 단계 나누기 -> 첫 단계 증명 -> 귀납 증명 반복문 불변식 (loop in - variant ) : 반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지 명시하는 조건 이진 탐색에서 int binsearch (const vector&A,int x){ int n =A.size(); .. 2022. 5. 22. 이전 1 다음