재귀적으로 문제 해결하기 (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) 에 대한 값을 최초에 연산할 때, 이를 별도로 저장한 뒤, 추후에 이 값이 어딘가에서 또 쓰일 때, 연산을 또 하는 것이 아니라 저장된 값을 읽으면 되지 않을까? 그러면 연산하는 시간을 훨씬 줄일 수 있을 것 같다.
아래와 같이 코드를 다시 써볼 수 있겠다.
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 에 대한 코드는 다음과 같다.
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;
}