[알고리즘] 동적계획법

피보나치 수열

: 첫째, 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열

 

동적계획법이란?

: 복잡한 문제를 간단한 여러 개의 하위 문제로 나누어 푸는 방법

이 때, 하위 문제의 답을 저장하여 중복 연산을 하지 않음.

 

동적계획법 문제의 특성

중복되는 부분문제 : 작은 하위 문제들이 중복되어 나타난다.

최적 부분 구조 : 최적해는 부분 문제의 최적해로부터 구할 수 있다.

 

시간 복잡도

간단한 재귀호출 : 계산하는 양이 대략 2배씩 늘어남. 계산양이 많아지면 느려짐

동적계획법: 각 항들은 딱 1번씩만 계산이 됨. n번째 항을 구하기 위해선 n만큼만 시간을 들이면 됨.

 

공간 복잡도

: 하위 문제들의 답을 저장해놓기 때문에 하위 문제의 수만큼 저장공간 필요

 

동적계획법을 구현하는 테크닉

        점화식

        : 복잡한 문제를 작은 하위문제로 표현한 식

        예) f(n) = f(n-1)+f(n-2)

 

1. 구하고자 하는 값이 무엇인지 정의한다.

      f(n): n번째 피보나치 수열

2. 구하고자 하는 값을 부분문제들로 표현한다.f(n) = f(n-1)+f(n-2)

       피보나치 수열의 n번째 항은 n-1항과 n-2항의 합이다.

방법

1. top-down (재귀호출식 방법)

        = 작은문제를 풀어 return해준다.

        = 큰 문제를 작은 문제로 나눈다.

2. bottom-up (반복문식 방법)

        = 크기를 조금씩 늘려서 문제를 푼다.

        = 작은 문제부터 차례로 풀어 적는다.

동적계획법 문제풀이 방법 요약

1. 구하고자 하는 값이 무엇인지 정의하기
2. 구하고자 하는 값을 부분문제로 구성된 식으로 표현하기
3. 점화식을 재귀호출, 반복문 식으로 코드로 작성하기