[알고리즘] 동적 프로그래밍 (Dynamic Programming)

 

동적 프로그래밍이란?

• 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법
• 하나의 문제를 단 한 번만 풀도록 하는 알고리즘 기법

조건

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다

 

피보나치수열

아래의 코드는 재귀를 사용해서 n-1번째 수를 구하는 코드입니다

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

위 코드를 사용해서 f(5)의 호출 과정을 그림으로 표현하면 아래와 같다

피보나치 수열

위의 사진을 보면 fibo(2) 함수가 3번 호출되어서 중복된 것을 확인할 수 있다

 

메모제이션 (Memoziation)

동적 프로그래밍 구현 방법 중 하나로 한 번 구한 결과를 메모리 공간에 저장해 두고 다시 활용하는 방법으로 중복을 줄이는 방법

int data[100] = {0,};
//메모제이션

int fibo(int n)
{
  if (n<=2) 
    return 1;
  if (data[n]==0)
    data[n] = fibo(n-1) + fibo(n-2);
  return data[n];
}

 

TOP-DOWN

큰 문제를 해결하기 위해 작은 문제를 호출한다는 개념

int data[100] = {0,};

int fibo(int n)
{
  if (n<=2) 
    return 1;
  if (data[n]==0)
    data[n] = fibo(n-1) + fibo(n-2);
  return data[n];
}

 

BOTTOM-UP

반복문을 사용해서 작은 문제부터 차근차근 답을 도출한다는 개념

int fibo(int n)
{
  data[0] = 0;
  data[1] = 1;
  for (int i=2; i<=n; i++)
    data[i] = data[i - 1] + data[i - 2];
  return data[n];
}

 

출처

[네이버 블로그] 20. 다이나믹 프로그래밍(Dynamic Programming) - 안경잡이개발자

https://blog.naver.com/ndb796/221233570962

20. 다이나믹 프로그래밍(Dynamic Programming)