본문 바로가기
자료구조

Dynamic Programming(동적 계획법)이란?

by 태풍사랑 2020. 4. 28.

Dynamic Programming(동적 계획법)이란?

  • 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말
  • 특정 범위까지의 값을 구하기 위해 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법
  • 구체적 알고리즘보다는 문제해결 패러다임에 가까움

cf) Divide and Conquer(분할정복)과 비슷?

  • 분할정복 -> 큰 문제를 해결하기 어려워 작은 문제로 나누어 푸는 방법 => 작은 문제에서 반복이 일어나는 부분이 없음
  • 동적 계회법 -> 작은 부분 문제들의 반복(답이 바뀌지 않음)을 이용해 풀어가는 방법
  • 차이법 => 작은 문제가 중복이 일어나는지 안일어나는지

Dynamic Programming 방법

  • 모든 작은 문제들은 한번만 푼다
  • 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 그 결과값을 이용

Dynamic Programming 조건

  • 작은 문제의 반복이 일어나는 경우
  • 같은 문제의 정답이 구할때마다 같은 경우

피보나치

  • 동적 계획법의 대표적인 예시

[재귀함수 형태의 피보나치 수열]

  • 피보나치 수열은 재귀함수의 형태로 표현된다
f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2) when n > 2
  • 실제로 컴퓨터가 계산하기에는 매우 부적합한 형태 ->프로그램 메모리의 스택에 데이터가 쌓여 함수가 계속 호출되면 메모리에 쌓이는 것들이 증가 => 숫자가 조금만 커져도 시간/공간 복잡도가 지수 스케일로 증가!(Exponentioal Explosion) (공간 복잡도의 경우 스택 오버플로우가 발생해 프로그램이 튕귈 수 있음)

[동적 계획법 형태의 피보나치 수열]

  -반복계산을 막기 위해 이전에 계산했던 값들을 배열에 저장(Top-down, Bottom-up ...)

    ⓐTop-down

  • 위에서 내려오는 것 = 큰 문제부터 시작해 계속 작은 문제로 분할해 가면서 푸는 것
  • 장점 : 코드의 가독성 증가
  • 단점 : 작성이 어려움
int memo[100]; //메모이제이션 공간. 전역 변수이므로 0으로 초기화
int fibonacci(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];
}

  ⓑBottom-up

  • 바닥에서 올라오는 것
  • 작은 문제부터 시작해서 작은 문제를 점점 쌓아 큰 문제를 푸는 것
  • 장점 : 풀기 쉬움
  • 단점 : 코드의 가독성 저하
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];
}

=> 숫자를 저장하는 공간이 필요한 대신 O(n)의 시간 복잡도로 구현할 수 있음

'자료구조' 카테고리의 다른 글

링크드 리스트  (0) 2022.03.04
큐(Queue)란?  (0) 2020.04.21
스택(stack)이란?  (0) 2020.04.21

댓글