다이나믹 프로그래밍 기초

오늘부터는 다이나믹 프로그래밍 (DP)와 관련되어서 문제를 쭉 풀어보려고 한다. 

다이나믹 프로그래밍의 구현 방식에는 크게 두가지 방법이 있다.

 

1. Top-down 방식 : 재귀를 활용해서, 큰 문제를 작은 문제로 쪼개는 방식 (ex 피보나치)

2. Bottom-up 방식 : 반복문을 활용해서, 작은 문제를 모아 큰 문제를 해결하는 방식

 

이 두 방식의 시간차이는 경우에 따라 다르게 때문에, 일단 둘중에 하나를 먼저 골라서 공부하면서 익숙해지는 것이 중요하다고 한다.

 

기본적으로는 스택오버플로우와 같은 문제가 발생한다면 이는 시간차이라기보다는 코드의 문제일 가능성이 크기 때문에 일단 기초적인 수준에서는 둘중 하나를 중점적으로 공부하는 것이 중요하다는 것!

 

다이나믹 문제 풀이의 전략으로는 "문제에서 구하려는 답을 문장으로 나타내는 것" 이다. 이를 점화식이라고 한다.

 

이제 문제를 통해서 해당 내용을 정리해보고, 풀어볼 것이다!