알고리즘 공부/종만북 요점정리
2022. 2. 26.
알고리즘의 정당성 증명 (귀류법 / 반복문 불변식)
수학적 귀납법 이용하기 - 문제 단계 나누기 - 첫번째 내용 증명 - 귀납 증명 첫번째 내용의 증명이 성립하며, 그 다음단계에서도 그 문제가 성립한다는 것을 보이면 해당 내용이 귀납적으로 마지막까지 성립함을 알 수 있습니다. EX ) 100개의 도미노의 예시 알고있는 내용 1. 첫번째 도미노는 사람이 밀어 넘어뜨린다. 2. 한 도미노가 넘어지면, 그 다음 도미노도 반드시 넘어진다. Q . 마지막 도미노가 넘어지는가? A : 1개의 도미노를 한계의 단계로 생각 (문제 단계 나누기) B : 첫번째 도미노가 넘어짐을 증명(첫번째 내용 증명) C : 한 도미노가 넘어질 때 다음 도미노가 넘어짐을 보임(귀납 증명) 알고있는 사실을 기반으로 위의 내용을 증명하면, 귀납적으로 마지막 도미노 또한 넘어짐을 증명할 수 ..