DP(Dynamic Programming)

1. DP(동적 프로그래밍)이란?

연산 속도와 메모리 공간을 최적으로 활용할 수 있는 알고리즘을 작성하게 해주는 방법이다.

• 큰 문제를 작은 문제로 나누어 푸는 기법 (분할 정복 기법)
• 같은 문제를 여러 번 계산하지 않도록 해줌
• DP의 전형적인 형태는 Bottom-Up 방식

2. Top-Down vs Bottom Up

우선 두 문제 모두 공통점은 큰 문제를 부분으로 나누어 푼다. 하지만,

• Top-Down: 가장 큰 문제를 작은 문제를 호출 하여 답을 찾는 코딩 기법(메모이제이션)
• Bottom-up: 가장 작은 문제들로부터 답을 구해가며 전체 문제의 답을 찾는 코딩 기법
  바텀업 방식은 재귀를 피하는 방법으로, 재귀가 콜 스택을 쌓을 때 발생하는 메모리 비용(memory cost)를 절약해준다. 공간이 부족해져버리는 Stack overflow error을 피할 수 있다.
  즉, 재귀 알고리즘은 끝에서부터 거꾸로 실행하고 바텀업 방식은 시작점부터 출발한다고 할 수 있다.

우리가 흔히 아는 피보나치 수열 문제를 구현하면서 그 차이점을 확인해보자.

컴퓨터 과학에서는 주로 0번째 항이 0인 피보나치 수열을 사용한다. ( 0, 1, 1, 2, ... )

int memo[100]{}; //메모이제이션 공간. 전역 변수이므로 0으로 초기화
int fibonacci(unsigned int n)
{
 if (n<=1) //0번째, 1번째 피보나치 수
   return n;
 if (memo[n]!=0) //메모가 있는지 확인(0으로 초기화되었으므로 0이 아니라면 메모가 쓰인 것임)
   return memo[n]; //메모 리턴
 memo[n]=fibonacci(n-1) + fibonacci(n-2); //작은 문제로 분할
 return memo[n];
}

이는 Top-Down 방식으로 재귀 호출을 이용해서 구현했다. fibonacci(4)를 구하는 큰 문제는 fibonacci(3)과 fibonacci(2)를 구하는 작은 문제로 나눌 수 있다. fibonacci(3)을 구하는 작은 문제는 fibonacci(2)와 fibonacci(1)을 구하는 더 작은 문제로 나눌 수 있다...따라서 fibonacci(n)을 구하는 큰 문제를 풀 수 있다.

int f_data[N] = {1, 1}; // N은 정의하기 나름
int last_pos = 1; // 마지막으로 계산한 지점. 이 코드에선 이미 f_data[1]까지 정의되어있기 때문에 1로 초기화한다.
int f(int n) //피보나치 수열의 제 n항을 구한다. 배열의 관점에서는 n-1번째 요소를 구하는 것.
{
    int i;
    if(f_data[n-1] == 0)  // 아직 구한 적이 없으면 구한다
    {
        for(i=last_pos+1; i<n; ++i)
        {
            f_data[i] = f_data[i-1] + f_data[i-2];
        }
        last_pos = n-1;
    }
    return f_data[n-1];
}

이는 Bottom-Up 방식으로 반복문을 사용해 구현했다. 첫 번째 피보나치 수를 구하는 문제와 두 번째 피보나치 수를 구하는 문제를 풀면 세 번째 피보나치 수를 구하는 문제를 풀 수 있다. 두 번째 피보나치 수를 구하는 문제와 세 번째 피보나치 수를 구하는 문제를 풀면 네 번째 피보나치 수를 구하는 문제를 풀 수 있다....이걸 반복하면 n번째 피보나치 수를 구할 수 있다.

이렇게 두 코드를 비교하면 두 방식의 차이점이 더 잘 와닿는다.
탑다운 방식은 피보나치 수열과 같은 점화식을 이해하기 쉽지만 메모리 사용량이 낭비된다.
따라서 바텀업 방식을 사용하면 재귀 호출을 하지 않으니 시간과 메모리 사용량을 줄일 수 있다.

3. 그렇다면 Top-Down vs Bottom-UP 각각 어떤 문제에서 사용해야 할까?

→ Generally, I recommend the top-down solution when either of the following is true:
1. It's not easy to see in what order the sub-problems should be solved if you were going to solve them bottom-up. This is sometimes the case if the relationship between the sub-problems is complicated.
2. It's possible that only a small number of sub-problems will be used as part of the solution. For example, the answer to your problem is F(k) and F(0) is the base case, but you're not sure that you need to know every value between F(0)...F(k) to solve the problem.

1. 서브 문제끼리의 관계가 복잡하다면, 즉 Bottom-Up 방식으로 푸는데 서브문제가 잘 풀리지 않으면 Top-down 방식으로 접근해라.
2. 서브 문제 전체의 크기에 비해 메일 문제에 관여하는 수가 적을 때 Top-Down으로 접근해라.

즉, 한줄로 정리해보면 서브 문제가 복잡해서 점화식이 직관적으로 와닿지 않으면 Top-Down 방식으로 접근해보고 메모리의 효율성을 고려할 필요가 있을 때는 Bottom-Up 방식으로 접근하는 것이 좋다.

쌩초보인 나는 우선 좀 비효율적이어도 재귀함수로 프로그램을 작성해 보고 메모제이션적용이 가능하다면 코드를 개선해나가는 방식으로 접근하는게 좋을 것 같다...^^

참고: https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95
https://semaph.tistory.com/16
https://loosie.tistory.com/172
https://stackoverflow.com/questions/6164629/what-is-the-difference-between-bottom-up-and-top-down
https://aerocode.net/129