Computer science/알고리즘 & 자료구조

[Algorithm] 다이나믹 프로그래밍 (Dynamic Programming)

lonnie(동현) 2021. 2. 7. 14:31


다이나믹 프로그래밍


  •  다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간의 효율성을 비약적으로 향상시키는 방법입니다.
  •  이미 계산된 결과는 별도의 메모리 영역에 저장하여 필요할 때 꺼내서 사용하도록 합니다.
  •  다이나믹 프로그래밍의 구현은 탑다운(Top-down), 보텀업(Bottom-up) 방식으로 구성됩니다.
  •  다이나믹 프로그래밍은 동적 (실행되는 도중에를 의미한다) 계획법이라고도 부릅니다.
 다이나믹 프로그래밍을 이용해서 문제를 해결할 때, 사용하는 배열 이름을 캐시(cahse), 메모(memo), 테이블(table), DP 혹은 D라고 설정합니다. 

다이나믹 프로그래밍의 조건


1. 최적 부분 구조(Optimal Substructure)

큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 구조를 의미합니다.

2. 증복되는 부분 문제

동일한 작은 문제를 반복적으로 해결해야 하는 문제를 뜻합니다.

Top-Down 방식 - 메모이제이션(Memoization)


  •  메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나입니다.
  •  탑 다운 방식으로 하향식이라고도 부릅니다.
  •  한번 계산한 결과를 메모리 공간에 메모하는 기법입니다. 따라서 같은 문제를 다시 호출하면 메모한 결과를 그대로 가져오게 됩니다. 값을 기록해놓는다는 점에서 캐싱(Cashing)이라고도 합니다.
  •  결과를 담아 놓기만 하고 활용하지 않을 수도 있습니다.
  •  탑다운 방식은 구현 과정에서 재귀 함수를 이용합니다.
  •  큰 문제를 해결하기 위해서, 작은 문제들을 재귀적으로 호출하여 작은 문제가 해결되었을 때 큰 문제의 답까지 얻을 수 있도록 코드를 작성합니다.

Bottom-up 방식


  • 다이나믹 프로그래밍의 전형적인 형태입니다.
  • 보텀 업 방식은 상향식이라고 부릅니다.
  •  아래쪽에서부터 작은 문제를 하나씩 해결해나가면서 먼저 계산했던 문제들의 값을 활용해서 그다음의 문제까지를 해결한다는 점이 특징입니다.
  • 보텀 업 방식은 구현 과정에서 반복문을 이용합니다.
  • 보텀 업 방식에서 사용되는 결과 저장용 리스트는 DP 테이블이라고 부릅니다.
728x90
반응형