자료구조 시작 전 알기 (4) Arrays, Algorithms, Complexity, and Recursion

일단 들어가기 앞서서 앞으로 증명에 자주 사용할 수학적 귀납법에 대해 알아보자.

 

수학적 귀납법 ( 명제 :  P(n)이 있을때 )

 

•  기본형 : p(1)이 참이고, p(n-1) ->  p(n) 이 참이면 p(n)은 모든 자연수 n에 대하여 참이다.
•  강한 형태 : p(1)이 참이고, p(1)^p(2) ^ ....^p(n-1) ->  p(n) 이 참이면 p(n)은 모든 자연수 n에 대하여 참이다.

수학적 귀납법은 크게 Base 와 Step 부분으로 나뉜다.

 

먼저, 기본형에 대해 보자면 base: p(1) 인 것이 참이라는 것을 보이고

step : p(n-1) ->  p(n) 가 참이라고 보이면, p (n) 은 모든 자연수 n에 대해 참이라고 증명이 가능하다.

 

base 와 step은 서로 독립적이고, 보통 base는 참인것을 금방 알수 있으며, 포인트가 되는 것은 step 부분이 참인 것을

알아내는 것이다. 그런데 step 에서 p(n-1) ->  p(n) 이 전체가 참이기만 하면 된다.

무슨 말이냐 하면 p(n-1)과 p(n) 둘다 참일 필요는 없다는 뜻이다. 

 

그렇다면 p(n-1) ->  p(n) 전체가 참인 것하고 p(n-1), p(n) 둘 다 참인 것이

다른 것인가? 그렇다. 왜 그렇게 되는지는 명제에 관한 내용을 보면 이해가 갈 것이다.

 

명제 P -> Q 의 의미

• P -> Q
  • P 가 참 , Q가 참 -> 전체는 참
  • P가 참, Q가 거짓 -> 전체는 거짓
  • P가 거짓, Q가 참 -> 전체는 참
  • P가 거짓, Q가 거짓 ->전체는 참 

일반적인 상식에서 문제가 되는것이 P가 거짓일 경우이다. 예를 들어서 생각해보자.

키가 크면 농구를 잘한다가 항상 사실이라고 가정을 해보자

그러면 키가 작으면 농구를 못한다는 이야기가 사실이 되는가?

아니다. 키가 크면 농구를 잘한다가 참일 경우에는, 키가 작으면 이라는 전제가 의미가 없다.

키가 작을 경우에 참 거짓을 보통은 따지지 않는다.

 

예시를 몇개 들어 가면서 이야기 해보자.

 

교수님께서 중간고사를 잘 보면 치킨을 사준다고 하셨다고 하자.

그렇게 중간고사를 보고 성적이 좋게 나와서 교수님이 치킨을 사주셨다고 하자. 이 경우에는 문제가 있는가? 없다.

성적이 좋게 나왔는데 교수님이 치친을 사주지 않으셨다. 문제가 있다.

성적이 나쁘게 나와서 교수님이 치킨을 사주는 일이 없었다. 이 경우에도 문제가 없다.

마지막으로 성적이 좋게 나오지 않았는데 교수님이 치킨을 사주셨다. 이 경우는 어떠한가? 문제가 있는가? 없는가? 조금 혼란이 있을 것이다.일반적인 사람의 대화는 몇가지 암묵적인 것이 깔려 있기 때문이다. 보통 성적이 좋으면 치킨을 사주겠다라는 말에 성적이 나쁘면 그럴일 없다 라는 것이 깔려있다고 생각한다. 그러나 그런것들을 다 제외 하고 논리로만 따졌을 때는 문제가 없다. 교수님이 성적이 나쁘면 치킨을 사주지 않겠다라는 말씀을 따로 언급하지 않으셨기 때문이다.

 

한가지 더 보자.

 

if n > 3 이면,  n^2(n제곱) > 9

 

항상 사실인 명제이다.

그런데 n=1이면 다음명제가 사실인가? n=1 이면 아무의미가 없기 떄문에 명제 자체는 사실이다.

 

그런 의미에서 step 부분이 참이면 그것만 가지고 참이라고 증명할 수 있게 된다.

 

그래서 우리는 step 부분을 증명 할때 p(n-1) ->  p(n) 에서 p(n-1) 이 참일때만 증명할 수 있으면 base 부분과 합쳐서 증명을 할 수 있다.

 

강한 형태는 1 일때 2일때 .... n-1 전부 사실일떄 p(n) 이 참이라는 것이 나오면 명제도 참이다 라는 의미이다.

 

이제 위의 내용을 바탕으로 간단한 알고리즘 2개를 보고 정확한지 빠른지 알아보자.

 

int sum(int x)
 {
    
    int i, S;
    S=0;
    for (i =1; i<= x; i++)
        S += i ;
    
    return S;
}

루프를 돌면서 1부터 x까지의 합을 알 수가 있다.

1부터 x 까지 다 더하고 있기 때문에 더한 값을 리턴한다는것에 대해 다른 이견이 나올수 없으므로 정확성 판단은 되었다.

 

시간은 얼마나 걸릴까?

 

루프가 돌아가는 x만큼의 시간을 쓰게 될것이다.

 

 
int sum(int x)
 {
    if (x <=0 ) return 0;
    return x + sum(x-1);    
 }

 

위의 코드를 재귀적으로 다음과 같이 작성할 수 있을 것이다.

쉽게는 이렇게 이해 할 수 있을 것이다. 예를 들어서 x=4 이면 5번째 줄에서 sum(3) 이 호출되고. sum(3)은 sum(2)를 호출하는 식으로 해서 거슬러 올라가 보면 0 부터 4까지의 합이 리턴되는 것을 알 수 있다.

 

그러나 이런식으로는 모든 재귀를 이해할수 없게 된다. 따라서 수학적 귀납법으로 증명해보자

 

증명하고 싶은 것 : sum(x) 는 1+2+3+4+...+x 를 리턴한다. (항상)

 

Base : P(1)이 참이다. "sum(1)이 리턴하는 값은 1이다."를 증명하면 된다. 실제 코드에 1을 대입해보자. 그러면 1을 리턴함을 알수가 있다.

 

Step : P(x-1) -> P(x) 이 참이다. sum(x-1)이 1+2+3+4+...+x-1 를 리턴하면, sum(x)는 1+2+3+4+...+x 를 리턴한다를 보여주면 된다.

코드를 보면 sum(x)는 x+sum(x-1)의 값을 리턴함. sum(x-1)의 리턴값은 1+2+3+..+(x-1) 과 같다고 가정했으므로 sum(x)는 1+2+...+(x-1)+x = 1+2+...+x를 리턴하는 것을 확인할수 있음.

 

이제 Complexity 를 생각해보자.

 

Complexity( 시간 복잡도 )

T(n) = 1+T(n-1) = 1+1+..+T(n-2) = ... = n 

따라서 T(n) = O(n) (n과 비슷하다는 뜻 Big-O 계산법, 나중에 관련해서 설명하겠다 그냥 상수시간을 가진다고 생각하자.)

 

다음 포스터에서는 다른 예제로 연습해 보는 시간을 가지겠다.