알고리즘1-2 수학적 귀납법과 재귀

수학적 귀납법의 기본형:

p(1)이 참이고 P(n-1) -> P(n)이 참이면,

P(n)은 모든 자연수 n에 대해서 참이다.

n은 짝수다.

n은 2보다 크다.

 

BASE가 참이고 STEP이 참인 것이 증명됐다.

P(1) -> P(2)

P(2) -> P(3)

...

P(N-1) -> P(N) 으로 짐작할 수 있다.

 

(전체가 "참"이라는 사실만 이용)

 

---

수학적 귀납법의 강한 형태:

p(1)이 참이고 P(1)^P(2)^...^P(N-1)->P(N)이 참이면,

P(n)은 모든 자연수 n에 대해서 참이다.

 

---

 P -> Q 의 의미?

1. 참 참 참

2. 참 거짓 거짓

3. 거짓 참 참

4. 거짓 거짓 참

 

ex) 100점 받으면 -> 치킨 사줄게 

1. 100점 받아서 치킨 사줌 (참 = 약속 지킴)

2. 100점 받았는데 치킨 안사줌(거짓 = 약속 안지킴)

3. 100점 못받았는데 치킨 사줌 (참 = 약속 어긴 것이 아님)

4. 100점 못받았는데 치킨 안사줌 (참 = 약속 어긴 것 아님)

 

의미가 있든 없든 참/거짓은 따로 있다.

1조원이 있으면 1억씩 줄게(의미가 없지만 사실일 수 있음)

 

P가 거짓일 때는 증명할 것이 없다. (항상 참)

따라서 수학적 귀납법에서는 P가 참일 때만 다룬다.

=> 재귀와 연결된다.

 

---

수학적 귀납법을 재귀에 적용

동작: 1+2+3+...+x 

 

P(X) : 항상 SUM(X)는 1+2+3+...+X 임을 보여야 한다

BASE: P(1)이 참이다.

STEP: P(X-1) -> P(X)

 

SUM(X-1)이 1+2+...+(X-1)을 리턴한다. (사실)

(참일수도 있고 거짓일 수도 있지만 거짓일 때 증명할 것이 없으므로 참이라고 생각하면 된다. - 증명이 필요없는 식)

 

SUM(X) = X+SUM(X-1)의 값을 리턴하므로

사실을 이용하면 SUM(X) = 1+2+...+(X-1)+X를 리턴함을 쉽게 확인할 수 있다!

 

 

 

같은 동작을 하는 재귀 코드

재귀를 읽을 수 있다면 이해하기 더 쉽다.

 

증명할 때도 정답이 리턴된다고 그냥 믿으면된다.

SUM(X-1) => 1부터 X-1까지의 합이 리턴된다고 그냥 믿으면 된다.

X+SUM(X-1)은 그냥 1부터 X까지의 합이겠구나~하면 된다.

 

---

시간 복잡도

T(N)이란 아까 SUM함수가 N 입력을 받았을 때 돌아가는 시간을 의미한다.

 

1(상수)+ N-1을 넣고 돌렸을 때의 시간

상수시간 + SUM에 N-1을 넣고 돌렸을 때의 시간

=> T(N)은 사실이다.

 

이 식을 계속 풀면 N이라는 값이 나오고

T(N) = O(N)

 

---

이진 탐색

정렬된 배열에서 특정 값의 인덱스를 찾고자 한다.

 

재귀코드. search를 해서 x가 있으면 배열의 인덱스 리턴, 없으면 -1 리턴

다시 말하면,

 

동작: 

만약 어떤 i에 대해서 a[i]=x라면 i를, 아니라면 -1리턴한다.

base: n=0인경우 어떤 i에 대해서 a[i]=x가 성립할 방법이 없고 함수는 항상 -1 리턴한다.

step: 

1. a[m]=x인 경우 m을 리턴한다.

2. a[m]>x인 경우 a[m], a[m+1]...a[n] 중에는 x와 같은 값이 없다.

a[i]=x인 경우가 있다면 i는 0,1...m-1중 하나이다. 

search(a,m-1,x)가 정확하다고 가정하면,

i는 0,1...m-1 중 리턴 or -1 리턴

3. 2번과 유사

 

일단 search()는 재귀니까 정확하다고 그냥 믿고 코드를 읽는다.

재귀를 따라 들어가지 않는 것이 포인트.