11. [Java] DP (Dynamic Programming : 동적 계획법)

DP (Dynamic Programming : 동적 계획법)

• N-a번째 답(값)을 이용하여 N번째 답을 구하는 알고리즘
• Memoization 
  한 번 구한 값을 배열 등에 저장(메모)해두고, 다음에 같은 값이 필요하면 메모해 둔 값을 사용하는 것으로 시간적 효율성을 증가시킨다.
• 일반적으로 N번째 답(값)을 구하기 위해 기존에 구해둔 N-a번째 답(값)을 사용하므로, 초기값은 직접 구해서 세팅하는 경우가 많다.
• 주로 For문과 DP값을 저장하는 배열로 구현하며 재귀함수로 구현하기도 한다.

📌 DP 접근 방법

• N-1번째 혹은 N-2번째 답(값)을 이용하여 N번째 답(값)을 구할 수 있을까 고민해본다.
• 경우의 수 구하는 문제가 DP문제인 경우가 상당히 많다.
• 일종의 점화식을 이용해서, 초기값 1번째 혹은 2번째 값까지는 직접 세팅하고, 이후 i번째 값들은 i-1 혹은 i-2번째 값을 이용하여 구한다.
• 따라서, 초기값 세팅과 점화식을 작성하는 것이 포인트이다.

📝 DP 예시 (피보나치 수열 구하기)

위와 같이 재귀함수로 피보나치 수열을 구하게 되면, 동일한 연산이 반복됨을 알 수 있다.

DP의 핵심은 동일한 계산을 다시 하지 않는 것에 있다.

 

대표적인 DP 문제

거스름돈 문제

배낭 문제

타일링

플로딩드-워셜 (최단 거리)