Treejin's Note

동적 계획법(Dynamic Programming)

• 전체 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용하여 큰 문제를 해결하는 방식이다.
  • 부분 문제를 정의한다.
  • 재귀적인 구조를 활용할 수 있는 점화식 만든다.
  • 작은 문제를 해결한 방법으로 전체 문제를 해결한다.
• 메모이제이션(Memoization) 기법 사용
  • 프로그램 실행 시 이전에 계산한 값을 저장하고, 필요할 경우 계산과정 없이 저장된 값을 이용함으로써 전체 실행 속도를 빠르게 하는 기술이다.
• EX. 피보나치 수열

분할 정복(Divide and Conquer)

• 문제를 나눌 수 없을 때까지 분할하고 각각을 풀고 다시 조합함으로써 문제를 해결하는 방식이다.
• 하향식 접근법을 이용한다.
• 문제가 나누어질 때, 각각의 문제는 중복되지 않는다. => 메모이제이션을 사용하지 않는다.