DP(Dynmic Programming) 알고리즘

• DP. 즉 Dynamic Programming은 여러가지 알고리즘 문제들을 풀다보면 간간히 사용하는 경우가 많다.
• 핵심 내용은 이전에 계산한 값을 다음 실행에 써먹을 수 있고 이러한 계산들이 쌓여서 결과를 도출한다는 것이다.
• 한마디로 입력값이 이전 계산값이고 출력값이 현재 구하려는 값이다.

백준의 14501번 : 퇴사 문제를 예시로 들어서 보자.

이 문제는 삼성 역량 테스트 문제로도 나온 문제로 대기업 코테에서도 DP 관련 문제가 나올 수 있다는 것을 알아두자.

 

문제 예시(1)

dp

45(35+10)

45

45(35+10)

35(15+20)

15

0

0

0

♦ 아이디어 방향

1. 그 전에 해당된 날짜의 이익, 상담하는 데에 걸리는 일수를 알고 있어야 다음을 진행할 수 있다.

2. 그 전 값을 기억하는 알고리즘 DP 알고리즘을 사용하여 문제를 푼다.

 

3. 이익의 최대를 생각하여야 하고 더한 일수가 주어진 최대 일수 n을 넘지 않아야 하므로 역으로 구한다.

 

이런 식으로 DP를 활용할 수 있다.

 

대부분 DP 문제들의 특징은 일정한 간격으로 떨어진 값들의 합 등의 결과값이나 정해진 범위에서 나열된 값들을 이용하여 푸는 문제들이 많다. 따라서 문제를 풀 때 내가 구하려는 결과의 식이 이전 결과를 계속 사용하여 풀어야 하는 문제라면 DP 알고리즘을 먼저 떠올려 보자.