재귀적으로 문제 해결하기 (1)

재귀적으로 문제 해결하기.

재귀적으로 문제를 푼다는 것은 무엇일까? 가장 대표적인 예인 피보나치 문제를 떠올려보자.

피보나치 수열

f(n+2) = f(n) + f(n+1) 를 만족하는 수열을 피보나치 수열이라고 한다. 수로 표현하면

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 과 같다.

n을 입력받아 n번째 피보나치 수를 구하여라.

이 문제를 아래와 같이 푼다면 재귀적으로 푼 것이다.

long long fibo(int n){
    if ( n == 1 || n == 2 )
        return 1;
    else
        return fibo(n - 1) + fibo(n - 2);
}

• 쉽게말해, 함수 내에서 호출된 함수를 또 호출하는 것이 재귀이다.

• 탈출조건이 있어야 한다.

  • ( 여기에선 n == 1 || n == 2 이다. )

• 답을 구하기 위한 식을 잘 설계해야 한다.

  • ( 여기에선 fibo(n) = fibo(n-1) + fibo(n-2) 이다. )

• 함수 파라미터로 어떤 것을 넘길지 잘 설계해야 한다.

그런데 위와 같이 짜면 하나 문제를 발견할 수 있다. 아래 예를 보자.

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

• 위는 fibo(5) 를 호출했을 때, 함수들이 어떻게 호출되는지를 보여준다.

• 먼저 fibo(5) 를 호출하면, fibo(4)와 fibo(3) 을 호출한다.

• 그리고 각각 fibo(4) 는 fibo(3)과 fibo(2)를, fibo(3)은 fibo(2)와 fibo(1) 을 호출한다.

• 호출의 깊이를 tab 단위로 구분하였다.

fibo(3) 에 대한 연산은 fibo(5)를 호출할 때, fibo(4)를 호출할 때, 이렇게 2번 중복하여 진행된다. 이를 중복 계산이라고 하는데, fibo(3)의 값을 한 번 구하면, 그 값은 바뀌지 않는데도 다른 함수에서 또 여러분 호출한다는 것이다.

fibo(3) 에 대한 값을 최초에 연산할 때, 이를 별도로 저장한 뒤, 추후에 이 값이 어딘가에서 또 쓰일 때, 연산을 또 하는 것이 아니라 저장된 값을 읽으면 되지 않을까? 그러면 연산하는 시간을 훨씬 줄일 수 있을 것 같다.

아래와 같이 코드를 다시 써볼 수 있겠다.

#define MAXN 200
​
long long fibo(int n){
    static long long memo[MAXN];
    
    if ( memo[n] > 1 )
        return memo[n];
    
    if ( n == 1 || n == 2 )
        return memo[n] = 1;
    else
        return memo[n] = fibo(n - 1) + fibo(n - 2);
}

• n에 대한 값이 memo[n] 에 있는지 확인한다. 있으면 갖다 쓰고, 없으면 원래대로 연산한다.

• n에 대한 값을 연산 후 memo[n] 에 저장한다.

이와 같은 방법을 메모이제이션이라고 한다. 중복계산이 있는 재귀문제 시, 중복계산을 없애고 수행속도를 월등히 빠르게 만드는 유명한 방법이다.

금액맞추기

지폐의 종류와, 지불해야 하는 액수를 입력받아서, 몇 가지 지불방법이 있는지를 출력하는 프로그램을 작성하라. 단, 지폐의 종류는 50가지를 넘지 않는다.

[실행 예]

input number of bills : 6

input bills : 1 2 5 10 20 50

input money: 100

4562

이 문제를 재귀적으로 파악하여 해결해보자.

1. 문제 재귀적으로 파악하기

먼저 위 예를 가지고 살펴보자.

100만원을 만드는 방법은 어떤 방법이 있을까? 지폐의 종류가 가장 큰 것부터 하나씩 경우의 수를 세어보자.

1) 50만원을 0장 쓰는 방법. => 나머지 화폐로 100만원을 만드는 경우의 수.

2) 50만원을 1장 쓰는 방법 => 나머지 화폐로 50만원을 만드는 경우의 수.

3) 50만원을 2장 쓰는 방법 => 나머지 화폐로 0만원을 만드는 경우의 수.

느낌이 조금 올 것 같다. 재귀를 다시 한 번 상기해보자. 재귀는 큰 문제를 작은문제로 잘게 나누는 것이다. 위의 경우 6개의 지폐로 100만원을 만드는 방법이 5개의 지폐로 100만원을 만드는 3개의 경우의 수로 나뉘었다.

2. 식을 정의하고, 관계 찾기

생각을 좀 더 잘 정리하면, 아래와 같이 개념적으로 정리할 수 있다.

라고 정의하자. 그러면,

와 같은 식을 성립하는 것을 알 수 있다.

저 식은 이해가 안간다면, 겁먹지 말고 하나씩 생각해보자. 결코 어렵지 않다.

• 먼저, bills[n - 1] 은 지폐중 가장 큰 값의 지폐를 말한다.

• 우리는 이 가장 큰 지폐를 i=0 부터 1, 2, .. 해서 우리가 만들고자 하는 m 만원을 넘지 않게 최대한까지 사용해볼 것이다. 이를 표현한 것이 위 식이다. i = 0 부터 m / bills[n-1] ( = bills[n-1] 를 사용할 수 있는 최대 수) 까지 재귀식을 반복하는 것이다.

• i = 0 부터 하나씩 i 를 증가해갈 때 마다, 즉 다시말해, 가장 큰 지폐를 하나씩 증가하며 사용할 때마다, m 에서 이 값 뺀 값을 나머지 지폐를 조합하여 만들어야 한다. 이를 표현한 것이 pay(m - bills[n - 1] * i, n - 1) 이다.

3. 코드로 구현하기

이제 이를 코드로 다시 표현해보면,

int pay(int money, int bills[], int n){
    int cnt = 0, i, t;
​
    /**** Important ****/
    if( n == 1 ){
        if( money % bills[0] == 0 )
            return 1;
        else
            return 0;
    }
    /*******************/
​
    t = money / bills[n-1];
​
    for(i=0 ; i<=t ; i++)
        cnt += pay(money - bills[n-1] * i, bills, n - 1);
​
    return cnt;
}

important 라고 주석 친 부분은, 나도 다소 헷갈렸었던 부분인데, 이 재귀가 언제 끝나고, 그 때에 무엇을 할 것인지에 대한 것이다.

• 재귀에서 계속해서 감소하는 파라미터는 n이다. 따라서 이 부분을 조건 삼아 재귀 탈출문을 만들어야 한다.

• 가장 높은 지폐부터 가장 낮은 지폐순으로 진행함으로 (이건 지폐가 오름차순으로 정렬되었다고 가정할 때이다.), 마지막의 경우 n == 1 일 때이고, 이 때 넘어온 파라미터로 money가 가장 낮은 지폐 bills[0] 으로 나뉘어 지는지 알아야 한다.

• bills[0] 은 마지막 남은 지폐이다. 나뉘어 진다면, 가능한 경우이므로 1을 리턴하여 최종적인 cnt 에 더해주고, 나뉘어지지 않는다면 불가능한 경우이므로, 0을 리턴하여 카운트 하지않는다.

main 에 대한 코드는 다음과 같다.

#include "stdio.h"
#define MAXN 50
​
int main(){
    int num_bills, money, i;
    int bills[MAXN];
​
    printf("input number of bills: ");
    scanf("%d", &num_bills);
    printf("input bills: ");
    for(i=0; i<num_bills; i++)
        scanf("%d", bills+i);
    printf("input money: ");
    scanf("%d", &money);
​
    printf("%d\n", pay(money, bills, num_bills));
​
    return 0;
}

이로써 문제를 해결했다.