DP(동적 프로그래밍)

동적 프로그래밍은 하위의 작은 문제들을 풀고 이를 이용해서 더 큰 문제를 풀어나가는 방법입니다.

모든 동적 프로그래밍 알고리즘은 격자(grid)로부터 시작합니다.

 

동적 프로그래밍의 특징

 

모든 답안에는 격자가 있습니다.

• 격자의 각 칸에는 최적화하고자 하는 값을 적습니다(최대화 또는 최소화). 배낭 문제의 경우에는 모든 물건의 총 가치를 썼습니다.
• 각 칸은 원래 문제에 대한 하위문제이고, 다른 문제를 하위문제로 가질 수 있습니다. 원래의 문제를 어떻게 하위문제로 나눌 수 있을지 생각해야합니다. 그러면 각각의 축이 어떻게 되어야 하는지 알아내는 데 도움이 됩니다

 

대표적인 문제로는 배낭채우기 문제가 있습니다.

물건이 3개일 때,

스테레오 $3000 4kg

노트북 $2000 3kg

기타 $1500 1kg

 

dp[][]

물건 / 무게	1	2	3	4
스테레오	0	0	0	$3000
노트북	0	0	$2000	$3000
기타	$1500	$1500	$2000	$3500

 

dp[i][j]의 최대값 1. 지금까지 구한 dp[i-1][j]의 값 중에서 가장 최대값

또는

2. 현재 물건의 가치 + 남은 물건의 가치(dp[i-1][j-물건의 무게])

 

---

 

배낭채우기 문제에서 물건을 일부만 훔친다면? -> 탐욕 알고리즘으로 풀 수 있습니다.

 

여행 일정 최적화 문제?

관광지,소요시간,얼마나 보고 싶은지를 나타낸 점수가 주어졌을때

이 표를 바탕으로 어떤곳을 돌아보아야 하는지 구하는 문제? -> 배낭채우기 문제와 같습니다.

 

 

https://code.plus/course/41

알고리즘 기초 1/2