![]()
자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 1. 재귀 이진 탐색 앞서 반복문을 통한 이진탐색을 보았는데 아래는 재귀를 통한 이진탐색입니다. // binary search with Recursion int binarySearch(int a[], int n, int target) { // Base if(n target) return binarySearch(a, m - 1, target); else return m + binarySearch(a + m + 1, n - m, target); ..
자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 알고리즘의 완전성을 증명하는 것은 중요합니다. 완전성을 증명하는 방법에는 여러가지가 있습니다. 알고리즘의 단계별로 하나하나 들어가서 이해하고 완전성을 확인하는 방법도 있습니다. 하지만 이는 그리 좋은 방법은 아닙니다. 해당 글에서는 수학적 귀납법을 사용하겠습니다. 1. 수학적 귀납법 임의의 공리 P가 존재한다고 할 때, 수학적 귀납법의 기본형은 다음과 같습니다. P(0) 가 성립한다. (* Base) 임의의 n 에 대하여 만약 P(n) 이 성립한다면, P(n+1) 역시 성립한다. (* Step) 수학적 귀납법의 강한 형태도 존재합니다. P(0), P(1), P(2) ... P(n-1) 이 성립한다. P(n) 이 성립한다면, P(n+1) 역시 성립..
