다이나믹 프로그래밍 (Dynamic Programming)

다이나믹 프로그래밍은 중복되는 연산을 줄이기 위한 방법이다. 

대표적인 예로 피보나치 수열이 있다. 

 

탑다운 방식과 보텀업 방식이 있다. 

 

탑다운 방식은 재귀를 사용하고,

보텀업 방식은 반복문을 사용한다. 

 

 

 

[어떤 문제에 적용이 될까?]

알고리즘 문제를 풀때, 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요하다.

가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토할 수 있다.

다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려해보자.

일단 재귀함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이

큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법을 사용할 수 있다.

일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많다.