다이나믹 프로그래밍의 정의, 동적 계획법, 탑다운 방식, 바텀업 방식

이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다.

한낱 미물이 신을 따라하고자 합니다.

아이패드로 공부해놓고 블로그로 옮기면서 작성하는거 귀찮아서 미루다가 다시 업로드.

 

---

정의

 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법.
 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않게함
 한 번 해결했다면 두 번 해결하지 않도록 함.
 시간 복잡도를 획기적으로 감소시키는데 영향을 줌.

 

 다이나믹 프로그래밍의 구현은 일반적으로 탑다운과 바텀업으로 구성됨.
 탑다운 : 위->아래, 하향식으로도 말함.
 바텀업 : 아래->위, 상향식으로도 말함.

 동적 계획법이라고도 부름. 다이나믹 프로그래밍을 직역한 것.
 

 

---

일반적인 프로그래밍 분야에서의 동적의 의미란?
 - 자료구조에서의 동적 할당은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미.
 - 반면 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용. 
  

 다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있음.
 - 최적 부분 구조
  큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아 큰 문제 해결 가능하다

 - 중복되는 부분 문제
  동일한 작은 문제를 반복적으로 해결해야 한다.

 대표적인 예시 : 피보나치 수열 (앞 수 더하기), 점화식(인접 항들의 관계식 의미)
 피보나치 수열을 점화식으로 표현
 n번째 a = n-1번째의 a + n-2번째의 a

 단순 재귀 함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가진다.
 여러 횟수로 반복 호출되는 경우가 생김.

 이 방식으로 f(30)을 계산하면 10억가량의 연산을 수행하게 됨. 

 

 

---

 탑다운 방식 : 메모이제이션. 
  - 한 번 계산된 결과를 메모리 결과에 메모함.
  - 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
  - 값을 기록해 놓는다는 점에서 캐싱이라고도 한다.

 

 바텀업 방식 : 전형적인 다이나믹 프로그래밍 방식.
  - 결과 저장용 리스트는 DP 테이블이라고 부름.
  - 반복문을 사용하는 편
 

 메모이제이션은 '이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미.
  - 따라서 메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아님.
  - 한 번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수 있음.

 

---