함수는 프로그램 소스 코드에서 일정한 동작을 수행하는 코드들을 말한며, 프로그래머가 직접 만들어 쓰는 함수는 사용자 정의 함수라고 한다. 어떤 함수를 호출했을 때, 자기 자신을 다시 호출하여 작업을 수행하는 방식을 재귀함수라고 하며, 재귀 호출이나 되부름이라고도 한다.
재귀함수를 처음 보면 기묘한 구조와, 기괴한 실행 방식 때문에 충격과 공포에 빠질 수 밖에 없다. 하지만, 재귀함수는 생각보다는 쉽다. 재귀함수는 마치 점화식처럼 자기 함수와의 관계를 맺는 것으로, 우리가 흔히 보는 피보나치 수열, 팩토리얼 등이 재귀함수와 관련이 있다. 백문이 불여일견, 재귀함수로 무엇을 할 수 있을지 보자.
#include <stdio.h>
int f(int k)
{
if(k<=2) return 1;
return f(k-1) + f(k-2):
}
int main()
{
int n;
scanf("%d", &n):
printf("%d", f(n));
return 0:
}
이 이상한 코드는 무엇일까? 피보나치 수열의 점화식이 존재하고, f(0)~f(2)가 1인 것으로 미루어 보아 이것은 피보나치 수열를 재귀함수로 나타낸 것이다. 아름다운 코드지만, 이것은 흔히 "순진한 방법"이라고 부르는, 착하지만 모자란 친구이다. 실제로, 이 방법의 시간복잡도는 O(n²)으로, 입력값이 커질수록 시간이 기하급수적으로 오래 걸린다. 그렇다면 조금 더 똑똑하게 푸는 방법은 없을까?
이 코드에서 시간복잡도를 크게 만드는 요소가 무엇일까? 이 코드에서는 연산하는데 시간이 오래 걸리는 함숫값들을 매번 연산하기 때문에 불필요한 시간을 낭비한다. 따라서, 한 번 연산한 함숫값은 어떠한 변수에 저장해두고, 그 값이 나왔을 때 바로 꺼내 쓴다면 시간을 크게 절약할 수 있을 것이다. 이 때, 함숫값이 매우 많으므로 배열을 이용한다면 쉽게 많은 값을 저장할 수 있을 것이다. 아래는 배열을 이용해 시간 복잡도를 줄인 예시이다.
계단 수 가 입력되면, 계단을 1,2,3개 오를 수 있는 경우의 수를 1000으로 나눈 나머지를 출력하는 프로그램이다.
#include <stdio.h>
int memo[1000000]= {};//재귀함수의 값을 저장할 배열, 전역 배열로 만들어 0으로 초기화, 더 큰 사이즈의 배열 생성 가능
int f(int k)
{
if(memo[k]!=0) return memo[k];//배열에 저장된 값이 있으면 바로 호출
else if(k == 0) return memo[0] = 1;
else if(k < 0) return 0;
else if(k == 1) return memo[1] = 1;
else if(k == 2 ) return memo[2] = 2;//3개 까지 오를 수 있으므로 f(2)까지 고려해야 함
else return memo[k] = (f(k-1) + f(k-2) + f(k-3))%1000;//연산했으면 저장해두기
}
int main()
{
int k;
scanf("%d", &k);
printf("%d", f(k)%1000);
}
이렇게 하면, 코드가 매우 효율적이게 되어 오를 수 있는 경우의 수가 3개가 되었음에도 10000 이하의 범위에서 1초 이내에 동작할 수 있다. 이렇게 배열에 저장해 시간 복잡도를 줄이는 방법을 메모이제이션이라고 한다. 다음은 메모이제이션을 이용한 풀어보면 좋은 문제들이다.
코드업 1930 Supersum
코드업 3702 파스칼의 삼각형 2
코드업 3733 우박수 길이 large
풀이도 올릴 것이다!