뚝딱햄 탈출기

다이나믹 프로그래밍?다이나믹 프로그래밍이란 하나의 문제를 단 한 번만 풀도록 하는 알고리즘이다. DP와 다르게 분할 정복은 동일한 문제를 다시 푼다.예를 들어 피보나치 수열을 분할 정복을 통해 푼다면 특정 숫자를 구하기 위해 그 n-1와 n-2 에 계속 접근한다.즉, 반복적인 데이터 계산이 발생한다.DP 사용할 수 있는 경우큰 문제를 작은 문제로 나눌 수 있다.작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.위의 조건을 만족할 때 다이나믹 프로그래밍을 사용하면 효율적으로 문제를 해결할 수 있다.다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 문제를 풀 때, 주어진 문제가 다이나믹 프로그래밍 유형임을 파악해야한다...