[Algorithm] Dynamic Programming

Dynamic Programming

다이나믹 프로그래밍은 하나의 문제는 한 번만 풀고 저장해둔다!! 즉, 중복되는 연산을 줄이는 알고리즘이다.

 

다이나믹 프로그래밍은 다음 조건을 만족할 때 사용한다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

간단하게 DP[Dynamic Programming]은 피보나치 수열을 풀기위해 사용될 수 있다.

 

DP를 구현하는 방법 중 메모이제이션[Memoization] 기법을 사용할 수 있다. 이는 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 호출하면 메모해둔 값을 불러오는 기법이다.

 

DP를 구현하기 위한 구조를 보면 두가지로 나눌 수 있다. 

• Top-Down 방식 : 재귀 함수를 이용하고, 큰 문제를 풀기위해 작은 문제를 호출하여 값을 구하기 때문에 탑다운이다.
• Bottom-up 방식 : 반복문을 이용하고, 작은 문제를 풀고 점점 위로 올라가기 때문에 보텀업이다.

 

DP 문제인지 파악하기 위해서는 문제를 완전 탐생으로 접근했을 때 시간이 매우 오래 걸릴 때 생각할 수 있다.

이후 위의 조건들을 생각하여 문제에 적용해보는 것이다.