다이나믹 프로그래밍

다이나믹프로그래밍

• 메모리공간을 약간 더 사용하면서 연산속도를 비약적으로 증가 시킬 수 있는 방법
• 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법
• 조건 
  • 큰 문제를 작은 문제로 나눌 수 있다.
  • 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
• 메모제이션 (캐싱)
  • 다이나믹프로그래밍을 구현하는 방법 중 한 종류로, 한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다.
  • 단순히, 한 번 구한 정보를 리스트에 저장하는 것이다.
• 다이나믹프로그래밍과 분할 정복의 차이점
  • 다이나믹프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다.
  • 분할 정복은 한번 변경된 정보는 더 이상 변경되지 않는다.
• 탑다운 (메모제이션)
  • 재귀함수를 이용하여, 큰 문제를 해결하기 위해 작은 문제를 호출
• 바텀업 (결과 저장용 리스트사용 "DP테이블")
  • 반복문을 이용
• 해당 문제의 중복여부를 확인하여, 다이나믹프로그래밍 방식으로 풀 수 있는지 확인해보자.
• 가능하다면, 재귀함수를 이용하는 탐다운 방식보다는 반복문을 사용하는 보텀업 방식으로 구현하는 것을 권장한다.
  • 재귀함수의 스택크기가 한정되어있을 수 있기 때문이다.