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



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


 (반복 알고리즘에 사용)


 (순환 알고리즘에 사용)


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


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


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;
}
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;
}
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;
}
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;
}
 
cs


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

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



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

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

하노이의 탑(The Tower of Hanoi)은 수학적인 퍼즐이자 게임이다. 하노이의 탑은 세 개의 기둥과, 이 기둥에 꽂을 수 있는 서로 다른 크기의 원판들로 구성된다. 원판들은 한 기둥에 정렬 되어 있는데, 아래에서 위로 갈 수록 원판의 크기가 작아진다. 퍼즐의 목표는 전체 원판들을 다른 하나의 기둥으로 옮기는 것인데, 이 때 다음과 같은 간단한 규칙을 따라야 한다.

  • 한 번에 하나의 원판만을 옮길 수 있다.
  • 원판을 옮길 때는 맨 위의 원판을 다른 기둥으로 옮겨야 한다.
  • 큰 원판을 작은 원판 위에 올릴 수 없다.
원판의 개수가 커질 수록 문제가 복잡해지기 때문에 순환적으로 접근해보자.
순환 알고리즘에서는 순환이 이루어질 때 마다 문제의 크기가 작아진다.
하노이의 탑에서는 옮겨야 하는 원판의 수가 문제의 크기이자 줄여야 하는 대상이다.
그러기 위해 먼저 대략적인 알고리즘을 살펴보겠다.

기둥 A, B, C가 존재하고 기둥 A에 있는 원판을 기둥 C로 옮기는 것을 목표로 한다.
먼저 원판이 한 개인 경우, 이 때는 그저 원판을 A에서 C로 옮기면 그만이다.
원판이 두 개 이상(n개)이면 일단 맨 밑에 있는 원판을 제외한 모든 원판들을 B로 옮긴다.
그 후 맨 밑의 원판을 C로 옮기고, B에 있는 남아있는 원판들을 다시 C로 옮기면 된다.
이 때 B에 남아 있는 원판들을 다시 C로 옮기는 것은 결국 n-1개의 원판을 기둥 B에서 A를 사용해 C로 옮기는 것과 같다.
즉 다시 한 번 이 알고리즘을 실행하되 문제의 크기인, 옮겨야할 원판의 개수는 n개에서 n-1개로 감소하였다.
순환을 하게 되면서 문제의 크기가 줄어든 것이다.

다음으로는 위의 알고리즘을 이용해 실제 코드를 작성해보았다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
 
void hanoi(int n, char from, char temp, char to) {
    if(n == 1) printf("원판 1 // %c ==> %c\n", from, to);
    else {
        hanoi(n-1, from, to, temp);
        printf("원판 %d // %c ==> %c\n", n, from, to);
        hanoi(n-1, temp, from, to);
    }
}
 
int main(void) {
    int n = 3;
    char from = 'A', temp = 'B', to = 'C';
    
    hanoi(n, from, temp, to);
    
    return 0;
}
cs


하노이의 탑을 계산하는 프로그램의 시간 복잡도를 구하는 과정은 다음과 같다.
먼저 하노이의 탑에서 n개의 원판을 옮기는데 필요한 연산의 수를 구해보자.
이 때 A(n)을 필요한 연산의 수라고 할 것이다.
위의 알고리즘에서 우리는 n개의 원판을 옮길 때 n-1개의 원판을 먼저 옮기고, 그 후 가장 아래의 1개의 원판을 옮긴 다음, 다시 n-1개의 원판을 옮겼다.
이를 식으로 바꿔주면 A(n) = A(n-1) + 1 + A(n-1) = 2A(n-1) + 1 이다.

이 때 A(n-1) = 2A(n-2) + 1 이므로 이를 대입하면 A(n) = 2 ^ 2 * A(n-2) + 2 + 1 이고,
또 A(n-2)는 2A(n-3) + 1임을 이용해 우리는 A(n) = 2^3 * A(n-3) + 4 + 2 + 1 인 것을 알 수 있다.
이 과정을 반복하다보면 결국 A(n) = 2^n-1 * A(1) + ....  + 2^2 + 2^1 + 2^0 이 된다. 
A(1)은 1이니, A(n)은 n개의 항을 가지고, 초항이 1, 공비가 2인 등비수열의 합이다.
따라서 총 연산의 개수는 A(n) = 1*(2^n - 1) / 2 - 1 = 2^n - 1이고, 시간복잡도는 O(2^n)가 된다.

A(n) = 2A(n-1) + 1에서 점화식을 이용할 수 도 있다.
A(n+1) = 2A(n) + 1 일 때 A(n+1) + 1 = 2(A(n)+1)이다.
B(n) = A(n) + 1이라 가정하였을 때, B(n+1) = 2B(n)이다.
이 때 B(n)은 첫째 항이 B(1) = A(1) + 1 = 2 이고 공비가 2인 등비수열이다.
따라서 B(n) = 2 * 2^(n-1) = 2^n 이고 B(n) = A(n) + 1이므로, 총 연산의 개수 A(n)은 2^n - 1이고, 시간복잡도는 O(2^n)가 된다.


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

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

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

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



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


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;
}
 
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;
}
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;
}
 
cs


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

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

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


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



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

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

프로그래밍 언어에서 되풀이하는 방법으로는 반복(iteration)과 순환(recursion)이 있다.

반복은 for나 while 등의 반복 구조를 사용해 반복하는 것을 말하며, 대부분의 경우 순환에 비해 간명하고 효율적이다.

그러나 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 순환은 반복에 비해 알고리즘을 훨씬 명확하거나 간결하게 나타나낼 수 있는 장점을 가지기도 한다.


순환 중에서 끝에서 이루어지는 순환을 꼬리 순환(tail recursion)이라 하고, 앞에서 이루어지는 순환을 머리 순환(head recursion)이라 한다. 

꼬리 순환은 반복 알고리즘으로 쉽게 바꾸어 쓸 수 있으나, 머리 순환이나 함수 내부 여러 군데에서 자기 자신을 호출하는 경우(multi recursion) 쉽게 반복 알고리즘으로 바꿀 수 없다.

일반적으로 동일한 알고리즘을 꼬리 순환과 머리 순환 중 어떤 것으로든 바꿀 수 있다면, 꼬리 순환을 선택하여야 한다.


이번에는 거듭제곱 값 계산을 통해 순환 알고리즘이 반복 알고리즘보다 빠른 경우를 살펴 보겠다.

간단하게 생각 할 수 있는 반복 알고리즘을 사용해 코드를 작성해보았다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
 
double power_iteration(double x, int n) { // x는 밑, n은 지수이다.
    int i;
    double r = 1.0;
    for (i = 0; i < n; i++)
       r = r * x;
    return (r);
}
 
int main(void) {
    double base = 2.0;
    int exponent = 10;
    double result;
    
    result = power_iteration(base, exponent);
    printf("계산 결과: %.2f\n", result);
    
    return 0;
}
cs


다음으로는 순환 알고리즘을 통해 코드를 작성하겠다.

순환에서 중요한 것은 순환을 할 때마다 문제의 크기가 작아진다는 것이다.

거듭제곱에서는 어떻게 크기를 줄일 수 있을까?


먼저 x^n 이라는 거듭제곱이 있을 때 n이 짝수라고 생각해보자.

이 때 지수를 줄일 수 있는 방법은 x^n 을 (x^2)^(n/2)로 표현하는 것이다.


n이 홀수일 때는 n이 짝수가 될 수 있도록 해주면 된다.

x^n 은 곧 x * x^(n-1)이고 n이 홀수이므로 n-1은 짝수이다.

x^(n-1)은 거듭제곱 꼴이고 지수가 짝수이므로, 위에서 사용한 방법을 사용하면 (x^2)^((n-1)/2))라고 할 수 있다.

즉 n이 홀수인 경우 x^n은 x * (x^2)^((n-1)/2))이다.


이러한 개념을 이용해 코드를 작성하면 다음과 같다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
 
double power_recursion(double x, int n) { // x는 밑, n은 지수이다.
    if (n == 0) return 1;
    else if ((n % 2) == 0) // n이 짝수인 경우
        return power_recursion(x*x, n/2);
    else return x * power_recursion(x*x, (n-1)/2); // n이 홀수인 경우
}
 
int main(void) {
    double base = 2.0;
    int exponent = 10;
    double result;
    
    result = power_recursion(base, exponent);
    printf("계산 결과: %.2f\n", result);
    
    return 0;
}
cs


글을 시작할 때 대부분의 경우에는 반복이 순환보다 효율적이다고 하였다.

하지만 이 경우는 순환이 더 효율적이다.

어째서일까?


이는 아까 언급한 바와 같이 순환 호출이 이루어 질 때마다 문제의 크기가 작아지기 때문이다.

예를 들어 n을 100이라고 가정하자.

이 때 n의 크기는 호출 할 때 마다 100 -> 50 -> 25 -> 12 -> 6 -> 3 -> 1 로 작아진다.

즉 순환 알고리즘의 시간 복잡도는 O(logn)이다.


반면 반복 알고리즘일 때는 n이 100이라면 100번의 연산이 이루어진다.

따라서 반복 알고리즘의 시간 복잡도는 O(n)이다.


이번 예제를 통해 일반적인 경우와 달리 순환 알고리즘이 반복 알고리즘보다 효율적인 경우를 살펴보았다.



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

[C][순환][반복] 이항 계수 계산  (0) 2018.09.24
[C][순환] 하노이의 탑 계산  (0) 2018.09.23
[C][순환][반복] 피보나치 수열 계산  (0) 2018.09.20

+ Recent posts

티스토리툴바