'메모이제이션' 태그의 글 목록

메모이제이션

[C][순환][반복] 이항 계수 계산 2018.09.24
[C][순환][반복] 피보나치 수열 계산 2018.09.20

[C][순환][반복] 이항 계수 계산

2018. 9. 24. 23:15

이항 계수(Binomial coefficient)는 다음과 같이 표현할 수 있다.

${\binom nk}={\begin{cases}n!/\left(k!(n-k)!\right)&0\leq k\leq n\\0&k<0\\0&k>n\end{cases}}$

또한 이항 계수에 대해 다음과 같은 식이 성립한다.

${\binom nk}={\binom n{n-k}}$ (반복 알고리즘에 사용)

${\binom nk}+{\binom n{k+1}}={\binom {n+1}{k+1}}$ (순환 알고리즘에 사용)

이항 계수를 계산하는 프로그램을 반복 알고리즘과 순환 알고리즘을 만들어보자.

먼저 반복 알고리즘을 사용하는 방법이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
 
int factorial(int n) {
    int i, result = 1;
    for(i = n; n > 0; n--)
        result *= n;
    return result;
}
 
int main(void) {
    int n, k, result;
    n = 5; k = 2;
    result = factorial(n) / (factorial(k) * factorial(n-k));
    printf("%dC%d = %d\n", n, k, result);
    return 0;
}
Colored by Color Scripter
cs

이항 계수 정의 그대로 팩토리얼을 사용하여 프로그램을 만들어 볼 수 있다.

다만 이 방법은 비효율적으로 느껴진다.

팩토리얼은 값이 커질 수록 실행하는 연산의 수가 급격히 커지기 때문이다.

따라서 다음과 같은 프로그램도 만들어 보았다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
 
int factorial(int n) {
    int i, result = 1;
    for(i = n; n > 0; n--)
        result *= n;
    return result;
}
 
int nCk(int n, int k) {
    if(k == 0 || k == n) return 1;
    else if ((0 < k) && (k < n)) {
        int i, numerator = 1;
        if(k > n/2) k = n - k;
        for(i = 1; i <= k; i++, n--)
        numerator *= n;
        return numerator / factorial(k);    
    }
    else return 0;
}
 
int main(void) {
    int n, k, result;
    n = 7; k = 5;
    result = nCk(n, k);
    printf("%dC%d = %d\n", n, k, result);
    return 0;
}
Colored by Color Scripter
cs

이 프로그램은 우리가 일반적으로 이항 계수를 구할 때의 방식과 동일하게 작동한다.

예를 들어 7C5를 구한다고 하자.

우리는 이항 계수의 성질을 이용하여 7C2를 구할 것이다.

또한 7C2를 구할 때에도 7! / (2! * 5!)을 계산하는 대신 7 * 6 / 2! 을 계산할 것이다.

7! = 7 * 6 * 5! 이니 굳이 일일히 팩토리얼을 계산하지 않고 약분을 하면 되기 때문이다.

따라서 위 프로그램도 팩토리얼을 최소한으로 계산하도록 하였다.

다음으로는 순환 알고리즘을 사용해보자.

이항 계수의 성질을 사용하면 쉽게 만들 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
 
int nCk(int n, int k) {
    if(k == 0 || k == n) return 1;
    else if ((0 < k) && (k < n)) 
        return nCk(n-1, k-1) + nCk(n-1, k);
    else return 0;
}
 
int main(void) {
    int n, k, result;
    n = 7; k = 5;
    result = nCk(n, k);
    printf("%dC%d = %d\n", n, k, result);
    return 0;
}
Colored by Color Scripter
cs

위 프로그램은 순환 알고리즘을 사용하였기 때문에 동일한 계산을 반복한다는 문제점을 가지고 있다.

이러한 비효율적인 방법 대신, 메모이제이션(Memoization)을 활용해 프로그램을 만들어 보자.

메모이제이션이란 한 번 그 값을 계산하였다면 값을 저장해두어, 다시 계산해야 할 때 계산하는 대신 값을 바로 가져오는 방법이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#define MAX_SIZE 100
 
int nCk(int n, int k) {
    static int arr[MAX_SIZE][MAX_SIZE];
    if(arr[n][k] > 0) return arr[n][k];
    else if(k == 0 || k == n) return arr[n][k] = 1;
    else if ((0 < k) && (k < n)) return arr[n][k] = nCk(n-1, k-1) + nCk(n-1, k);
    else return 0;
}
 
int main(void) {
    int n, k, result;
    n = 7; k = 5;
    result = nCk(n, k);
    printf("%dC%d = %d\n", n, k, result);
    return 0;
}
 
Colored by Color Scripter
cs

한 번 계산을 하면 배열 arr에 값을 삽입해두고 나중에 동일한 값을 계산해야 될 시 그 값을 그대로 사용한다.

이 방법을 통해 우리는 동일한 계산을 여러 번 반복하지 않아도 된다.

'C언어 > 자료구조' 카테고리의 다른 글

[C][순환] 하노이의 탑 계산 (0)	2018.09.23
[C][순환][반복] 피보나치 수열 계산 (0)	2018.09.20
[C][순환][반복] 거듭제곱의 값 계산 (1)	2018.09.20

[C][순환][반복] 피보나치 수열 계산

2018. 9. 20. 23:46

피보나치 수열(Fibonacci Sequence)을 계산하는 프로그램을 순환 알고리즘과 반복 알고리즘을 통해 만들어보겠다.

피보나치 수열의 정의는 다음과 같다.

F_{n}:={\begin{cases}0&{\mbox{if }}n=0;\\1&{\mbox{if }}n=1;\\F_{n-1}+F_{n-2}&{\mbox{if }}n>1.\\\end{cases}}

위 정의를 보면 피보나치 수열 정의 자체가 피보나치 수열을 포함하는 순환적인 구조로 이루어져 있다는 것을 알 수 있다.
이에 순환 알고리즘을 사용하여 코드를 작성해보았다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
 
int fibonacci(int n) {
    if(n == 0) return 0;
    else if(n == 1) return 1;
    else return (fibonacci(n-1) + fibonacci(n-2));
}
 
int main(void) {
    int num = 7;
    int result;
 
    result = fibonacci(num);
    printf("%d번째 fibonacci 수열 값: %d", num, result);
    return 0;
}
 
Colored by Color Scripter
cs

위의 코드에서 fibonacci 함수는 보기에 이해하기 쉽고 간편해보인다.

하지만 실제로 이 함수는 매우 비효율적이다.

n의 값이 커질 수록 호출 되는 횟수가 매우 많이지기 때문이다.

여기서는 fibonacci(7)을 계산하였는데,

fibonacci(7)을 구하기 위해서는 fibonacci(6)와 fibonacci(5)의 값이 필요하고,

fibonacci(6)을 구하기 위해서는 fibonacci(5)와 fibonacci(4)가,

fibonacci(5)를 구하기 위해서는 fibonacci(4)와 fibonacci(3)이 필요하다.

즉 한 번 fibonacci 함수를 호출을 하면 두 번의 fibonacci 함수를 호출하게 된다.

따라서 피보나치 수열을 계산하는 순환 알고리즘의 시간 복잡도는 O(2^n)이다.

추가로 메모이제이션(Memoization)을 사용해 위 프로그램을 수정해보겠다.

메모이제이션이란 한 번 그 값을 계산하였다면 값을 저장해두어, 다시 계산해야 할 때 계산하는 대신 값을 바로 가져오는 방법이다.

이 방법을 동일한 피보니치 수를 다시 계산하는 것을 방지할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#define MAX_SIZE 100
 
int fibonacci(int n) {
    static int arr[MAX_SIZE];
    if(n < 2) return n;
    if(arr[n] > 0) return arr[n];
    else return arr[n] = fibonacci(n-1) + fibonacci(n-2);
}
 
int main(void) {
    int num = 10;
    int result;
 
    result = fibonacci(num);
    printf("%d번째 fibonacci 수열 값: %d", num, result);
    return 0;
}
Colored by Color Scripter
cs

다음으로는 반복 알고리즘을 사용하여 코드를 작성해보았다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
 
int fibonacci1(int n) {
    if(n < 2) return n;
    else {
        int i, tmp, cur = 1, last = 0;
        for (i = 2; i <= n; i++) {
            tmp = cur;
            cur += last;
            last = tmp;
        }
        return cur;
    }
}
 
int fibonacci2(int n) {
    if(n < 2) return n;
    else {
        int i, tmp, cur = 1, last = 0;
        for (i = 2; i <= n; i++) {
            tmp = last;
            last = cur;
            cur += tmp;
        }
        return cur;
    }
}
 
int main(void) {
    int num = 7;
    int result1, result2;
    
    result1 = fibonacci1(num);
    result2 = fibonacci2(num);
    printf("%d번째 fibonacci1 수열 값: %d\n", num, result1);
    printf("%d번째 fibonacci2 수열 값: %d", num, result2);
    return 0;
}
 
Colored by Color Scripter
cs

위의 코드에서 fibonacci1과 fibonacci2 모두, 반복 알고리즘을 사용해서 피보나치 수열을 계산하는 함수이다.

다만 구현 과정에서 어떠한 방법을 선택하여도 상관 없다는 것을 보여주기 위해 두 개다 만들어보았다.

for문을 사용하였기 때문에, 피보나치 수열을 계산하는 반복 알고리즘의 시간 복잡도는 O(n)이다.

이번 예제를 통해 문제의 정의가 순환적으로 되어있는 경우에도 순환 알고리즘보다 반복 알고리즘의 효율성이 뛰어날 수 있다는 것을 알아보았다.

'C언어 > 자료구조' 카테고리의 다른 글

[C][순환][반복] 이항 계수 계산 (0)	2018.09.24
[C][순환] 하노이의 탑 계산 (0)	2018.09.23
[C][순환][반복] 거듭제곱의 값 계산 (1)	2018.09.20

PREV 1 NEXT

공대 다니는 문과생