재귀와 동적 프로그래밍

재귀로 풀기 적당한 문제

'n번째 ~를 계산하는 알고리즘'

'첫 n개를 나열하는 코드'

'모든 ~를 계산하는 메소드'

--

접근법

1. 상향식 접근법

가장 간단한 경우에 대한 풀이법보터 발견한 후 점진적으로 늘려간다.

2. 하향식 접근법

문제들을 어떻게 하면 부분적으로 나눌 수 있는지 생각해본다.

나뉜 부분문제들이 서로 겹치지 않도록 주의한다.

3. 반반 접근법

절반씩 재귀적으로 탐색해나가는 방법

ex) 병합 정렬

--

재귀적 해법 vs 순환적 해법

재귀적 알고리즘은 공간 효율성에 좋지 않다.

허나 순환적으로 구현된 코드가 더 복잡할 때가 많다.

--

동적 계획법

재귀적 알고리즘과 반복적으로 호출되는 부분 문제를 찾는 것이 관건.

상향식 접근을 동적 프로그래밍, 하향식 접근을 메모이제이션이라고 함.

--

피보나치 수 구하기

1. 하향식 동적 프로그래밍(메모이제이션)

#include<cstdio>
int fib(int i);
int num[46];
int main()
{
    printf("46번째 피보나치 수는 %d이다.", fib(45));
}
int fib(int i)
{
    if (i == 0 || i == 1)
        return 1;
    if (num[i] == 0)
        num[i] = fib(i - 1) + fib(i - 2);
    return num[i];
}

2. 상향식 동적 프로그래밍

#include<cstdio>
int fib(int i);
int num[46];
int main()
{
    printf("46번째 피보나치 수는 %d이다.", fib(45));
}
int fib(int i)
{
    num[0] = num[1] = 1;
    for (int j = 2; j <= i; ++j)
        num[j] = num[j - 1] + num[j - 2];
    return num[i];
}