다이나믹 프로그래밍 관련문제

증가하는 부분 수열

 

 

 

플랫폼	링크	요약	풀이	복습
백준	https://www.acmicpc.net/problem/1965	증가하는 부분 수열 중에서 최대 길이 구하는 문제	https://sen-zoo.tistory.com/45	점화식 세우는 방법

 

---

배낭 알고리즘

 

알고리즘 설명

배낭 알고리즘은 다이나믹 프로그래밍을 사용하는 대표적인 알고리즘 유형 중 하나이다.
배낭 알고리즘은 최대한의 가치를 찾는데 쓰이는 알고리즘이다.

 

위 예시처럼 4개의 물건이 있고 각 물건은 무게와 가치를 가진다. 그리고, 물건들을 배낭에 담을 수 있는데 배낭에 담을 수 있는 최대 용량이 존재한다.

 

처음에는 이런 문제를 그리디 방법으로 접근했다. 무게당 가치가 높은 물건을 배낭에 담으면 배낭에 담을 수 있는 최대가치를 구할 수 있지 않을까? 라고 생각했다. 하지만 이렇게 접근한다면 앞에서 선택한 물건 떄문에 뒤에 있는 물건을 담지 못하는 경우가 있다.

 

배낭의 최대 용량이 10이라고 하자.

물건	무게	가치	가치/무게
A	6	60	10
B	5	50	10
C	10	80	8

위와 같은 경우일 때, 그리디 방식으로 접근한다면 무게당 가치가 가장 높은 물건 A만 배낭에 담을 수 있게 된다. 하지만 최대 가치는 물건 C를 담았을 경우이다.

 

그래서 배낭 알고리즘에서는 현재 배낭에 담는 물건이 이후의 선택에 영향을 주기 때문에 이 부분도 고려해야 한다.

 

다시 배낭 알고리즘으로 돌아온다면, 배낭에 물건을 담을 때, 두가지로 나누어 생각해 볼 수 있다.
현재 물건을 배낭에 넣을 수 있는가? 없는가?

만약, 배낭에 넣을 수 있다면 넣는 것이 최대 가치인가 넣지 않는 것이 최대 가치인가?

 

이를 구하기 위해서 2차원 배열을 생성해 보았다.

 

여기서 행은 물건을 의미하고, 열은 배낭의 최대 용량을 의미한다.

배낭의 최대 용량을 1부터 늘리고, 현재 배낭의 최대용량에서 물건을 하나씩 고려하면서 배낭에 넣을 것인지 안 넣을 것인지를 고려할 것이다.

 

• 배낭의 최대 용량이 1인 경우
  • 물건을 넣지 못하므로 가치는 0이다.
• 배낭의 최대 용량이 2인 경우
  • 물건을 넣지 못하므로 가치는 0이다.
• 배낭의 최대 용량이 3인 경우
  • 물건1을 고려했을 때 물건을 넣지 못하므로 0이다.
  • 물건2를 고려했을 때 물건을 넣지 못하므로 0이다.
  • 물건3을 고려했을 때 물건을 넣을 수 있으므로 6이다.
  • 물건4를 고려했을 떄 물건을 넣을 수 없으므로 물건 3을 넣은 가치 그대로인 6이다.
• 배낭의 최대 용량이 4인 경우
  • 물건1을 고려했을 때 물건을 넣지 못하므로 0이다.
  • 물건2를 고려했을 때  물건을 넣을 수 있으므로 8이다.
  • 물건3을 고려했을 때 배낭의 최대 용량인 4보다 무게가 작으므로 넣을 수 있다. 하지만, 이미 배낭에는 물건2가 들어있는데 어떤 물건을 배낭에 담아야 최대 가치를 구할 수 있을까를 고려해야 한다. 즉, 기존에 들어있는 물건2를 빼고 물건3을 넣었을 때의 가치와 물건3을 넣지 않았을 때의 가치를 비교해서 최대 가치를 얻을 수 있는 물건을 배낭에 담아야 한다.
    • 기존에 들어있는 물건2를 빼고 물건3을 넣었을 때의 가치를 생각해봐야 한다. 배낭에 물건3을 담았을 때 배낭의 최대용량은 (배낭의 최대용량 - 물건3의 무게)가 된다. 그리고 물건2까지 고려해야하기 때문에 했을때 dp[2][배낭의 최대용량 - 물건3의 무게] 가 된다. 그리고 물건3은 배낭에 담겨있기 때문에 물건3의 가치를 더해주어야 한다.
      이를 점화식으로 나타내면 다음과 같다.
      dp[3][배낭의 최대용량] = 물건3의 가치 + dp[2][배낭의 최대용량-물건3의 무게]
    • 물건3을 넣지 않았을 때의 가치는 다음과 같다. 물건3을 넣지 않았으므로 배낭의 최대 용량은 4이다. 또한, 물건3까지 고려하므로 이를 점화식으로 나타내면 다음과 같다.
      dp[3][배낭의 최대용량] = dp[2][배낭의 최대용량]

그래서 위의 2차원 배열에서 주황색 칸의 점화식은 아래와 같다.

dp[3][4] = Math.max(dp[2][4], 6 + dp[2][1])

즉, dp[2][4]의 가치가 더 높으므로 물건2를 담았을 때가 최대 가치이다.

 

이렇게 2차원 배열을 채우다보면 배낭에 물건을 담아서 얻을 수 있는 가치의 최대를 구할 수 있다.

 

 

플랫폼	링크	요약	풀이	복습
백준	https://www.acmicpc.net/problem/7579	배낭 알고리즘(DP)	https://sen-zoo.tistory.com/46	배낭 알고리즘에서 '배낭의 최대 무게', '물건의 무게', '물건의 가치'가 문제에서 어떠한 의미로 변환될 수 있는지
백준	https://www.acmicpc.net/problem/2629	배낭 알고리즘(DP)	https://sen-zoo.tistory.com/47	dp에서 구하고자 하는 값이 '합' 뿐만이 아닌 '차이'도 고려하는 문제
백준	https://www.acmicpc.net/problem/9084	배낭 알고리즘(DP)	https://sen-zoo.tistory.com/48	사용할 수 있는 동전의 개수에 제한이 없는 상황에서 경우의 수를 구하는 문제
백준	https://www.acmicpc.net/problem/1535	배낭 알고리즘(DP)	https://sen-zoo.tistory.com/49	물건을 한번만 사용할 수 있는 배낭문제
백준	https://www.acmicpc.net/problem/1106	배낭 알고리즘(DP)		물건을 여러번 사용할 수 있는 배낭문제