[고급-1] 관계기반 알고리즘 설계

[관계기반 알고리즘 설계]

학습목표

-탐색기반과 관계기반 설계의 차이점을 이해할 수 있다.

-관계기반 설계를 위한 수학적 귀납법을 이해할 수 있다.

-수학적 귀납법을 재귀함수로 구현하는 방법을 이해하고 실제 문제에 적용할 수 있다.

1. 관계기반 설계 수학적 귀납법

1. 탐색기반설계 : 해 집합 탐색.

2. 관계기반설계 : 해를 구하는 행위를 하나의 함수로 표현 후 이 함수들의 관계 이용해서 해를 구함.

01 문제의 정의 및 상태를 함수로 정의

02 함수들간의 관계를 점화식 혹은 이와 유사한 형태로 표현

3. 수학적 귀납법

자연수n에 대한 명제 P(n)이 모든 자연수에 대해서 성립함을 증명하기 위한 수학의 증명법 중 하나.

01 P(1)이 성립함을 보인다. -Basis

02 P(k)가 성립한다고 가정하고 P(k+1)이 성립함을 보인다. -induction

문제의 입력에 대해 문제에서 해를 귀납적 관계를 이용하여 구하는 문제해결 방법

01 입력값이 n인 문제의 해를 f(n)으로 정의

02 f(1)을 직접 구하여 출력. -Basis

03  f(k)를 이미 구해두었다고 가정하고 f(k)를 통해 f(n)을 구하여 출력한다. -induction

4. 귀납법을 이용한 재귀함수의 설계 : 1~n까지 합

방법_1 : 함수들과의 관계를 점화식 혹은 이와 유사한 형태로 표현.

01 f(n)의 정의 : f(n) = 1에서 n까지의 합

02 f(1)을 직접 구함. : 1에서 1까지의 합은 1이 된다. -Basis

03 f(k)가 이미 구해졌다고 가정하고 f(n) 구한다.(보통 k는 n-1의 값 혹은 n/2으로 정의) -induction

f(9) = 1+2+3+4+5+6+7+8+9

f(1) = f(9)+10

int f(int n){
    if(n==1)
        return 1;
    return f(n-1)+n;
}

방법_2 : f(k)에서 k를 n/2로 정의한다.

f(10)구할때, f(5)를 안다고 가정하면,

f(10)=f(5)+6+7+8+9+10

=f(5)+(5+1)+(5+2)+(5+3)+(5+4)+(5+5)

=f(5)+(1+2+3+4+5)+(5+5+5+5+5)

=f(5)+f(5)+(5*5)

=2f(5)+5^2

int f(int n){
    if(n==1)
        return 1;
    return 2*f(n/2)+((n+1)/2)*((n+1)/2);
}

4번째 중에서 (n+1)/2는 짝수와 홀수 둘 다 고려한 것이다.(만약 짝수만 고려 했다면, (n+1)/2 대신 n/2를 썼다.)

 -방법 1과 방법 2의 계산량 비교

방법 1 : 입력 데이터 값에 비례하는 계산량 필요.

방법 2 : 입력 데이터 값 에 비례하는 계산량 필요.

-> 방법 2가 방법1보다 훨씬 적게 함수를 호출하는 것을 볼 수 있다.

5. 귀납법을 이용한 재귀함수의 설계 - 진법변환 : 10진수 n을 k진법으로 출력하는 프로그램.

(1) f(n,k) = 10진법 수 n을 k진법으로 출력

(2) f(n,k) = n (n<k) 또는 f(n,k) = 아무것도 출력하지 않음. -Basis

(3) f(n,k) = f(n/k,k),printf("%d", n%k) (n>=k) - induction

<1: k의 값이 16 미만일 때

void f(int n, int k){
    if(n<k)
        printf("%d", n%k);
    else{
        f(n/k, k);
        printf("%d", n%k);
    }
}
 

<2: k의 값이 16 이상일 떄

char d[21] = "0123456789ABCDEFGHIJ";
 
void f(int n, int k){
    if(n<k)
        printf("%d", d[n%k]);
    else{
        f(n/k, k);
        printf("%d", d[n%k]);
    }
}