콘텐츠로 이동

14.8   연습 문제

14.8.1   개념 확인

1.   언제 동적 계획법을 사용하는 것이 적합한가

한 학생이 “점화식을 쓸 수만 있으면 동적 계획법을 사용해야 한다.”라고 말했다. 다음 세 작업에 동적 계획법, 백트래킹, 또는 dp 테이블을 만들지 않는 반복문이나 수학 공식 중 어느 방법이 더 적합한지 판단하고, 핵심 이유를 하나씩 적어 보자.

  1. 액면가가 [1, 3, 4]인 동전으로 금액 6을 만들 때 필요한 동전의 최소 개수를 구한다. 각 동전은 반복해서 사용할 수 있다.
  2. [1, 2, 3]의 모든 순열을 출력한다.

  3. \(1 + 2 + \dots + n\)을 계산한다.

    동적 계획법이 적합하다고 판단한 작업에서는 dp[i]가 무엇을 나타내는지도 설명하라.

참고 답안

  1. 동적 계획법이 적합하다. dp[i]를 금액 i를 만드는 데 필요한 동전의 최소 개수로 정의한다. i 이하인 각 동전 c에 대해 dp[i-c] + 1을 후보 답으로 삼고, 이 후보들 중 최솟값을 선택하면 된다. 서로 다른 선택에서 같은 금액을 반복해서 만나며, 더 큰 금액의 최적해도 더 작은 금액의 최적해로 구성할 수 있다. 금액 6의 답은 2이며, 3 + 3으로 만들 수 있다.

  2. 백트래킹을 사용해야 한다. 문제에서는 순열 6개를 모두 하나씩 생성해야 한다. 백트래킹은 하나를 선택하고 탐색을 이어 간 뒤, 선택을 취소하고 다른 분기를 시도하는 과정을 체계적으로 수행할 수 있다. 어떤 방법을 쓰더라도 이 순열들을 실제로 출력하려면 열거 과정을 생략할 수 없다.

  3. 반복문이나 등차수열의 합 공식을 사용하면 된다. S(i) = S(i-1) + i라는 점화식을 쓸 수는 있지만, S(i)를 계산할 때는 더 작은 값 S(i-1) 하나에만 의존한다. 각 부분합을 한 번만 계산하면 되고 중복되는 부분 문제가 없으므로 dp 테이블을 만들 필요가 없다. ‘점화식을 쓸 수 있다’고 해서 ‘동적 계획법이 필요하다’는 뜻은 아니다.

2.   배낭 테이블의 한 칸은 어떻게 계산하는가

0-1 배낭 문제에서 물건의 무게는 wgt = [1, 2, 3], 가치는 val = [5, 11, 15]이며, 배낭 용량은 4다. dp[i][c]는 앞의 물건 \(i\)개만 고려하고 배낭 용량의 상한이 \(c\)일 때 얻을 수 있는 최대 가치를 나타낸다. 배낭을 반드시 가득 채울 필요는 없다.

지금은 상태 dp[3][4]만 계산한다. dp[2][4] = 16, dp[2][1] = 5임을 알고 있다.

  1. 세 번째 물건을 선택하지 않을 때 후보 가치는 얼마인가?
  2. 세 번째 물건을 선택하면 용량이 얼마나 남으며, 후보 가치는 얼마인가?
  3. dp[3][4]는 얼마로 정해야 하는가? 이는 어떤 물건들을 선택한 결과인가?
참고 답안

  1. 세 번째 물건을 선택하지 않으면 앞의 두 물건에 대한 결과를 그대로 사용하므로 후보 가치는 dp[2][4] = 16이다.

  2. 세 번째 물건의 무게는 3이므로 넣은 뒤 남는 용량은 \(4-3=1\)이다. 후보 가치는 dp[2][1] + 15 = 5 + 15 = 20이다.

  3. 16과 20을 비교하면 dp[3][4] = 20을 얻는다. 이는 첫 번째와 세 번째 물건을 선택한 결과로, 총무게는 \(1+3=4\), 총가치는 \(5+15=20\)이다.

    이 상태의 계산은 0-1 배낭 문제에서 한 번의 ‘선택하거나 선택하지 않거나’ 비교를 보여 준다.

3.   배낭 용량은 어떤 순서로 갱신해야 하는가

0-1 배낭 문제에 물건이 하나뿐이며, 무게는 2, 가치는 5다. 배낭 용량은 4다. 각 물건은 최대 한 번만 선택할 수 있고, 초기 일차원 배열은 dp = [0, 0, 0, 0, 0]이다.

한 학생이 이 물건을 처리하면서 용량을 2부터 4까지 갱신했다.

  • dp[2]를 갱신한 뒤 5를 얻었다.
  • dp[3]을 갱신한 뒤에도 5를 얻었다.
  • dp[4]를 갱신할 때 방금 구한 dp[2]를 다시 사용하여 dp[4] = 10을 얻었다.
  1. dp[4] = 10이라는 결과가 올바른가? 이유는 무엇인가?
  2. ‘각 물건은 최대 한 번만 선택할 수 있다’는 조건에 따르면 dp[4]는 얼마여야 하는가?
  3. 각 물건을 처리할 때 용량을 큰 것부터 작은 것 순으로 갱신해야 하는가, 그 반대인가? 그렇게 하면 어떤 문제를 피할 수 있는가?
참고 답안

  1. 올바르지 않다. 가치 10은 가치가 5인 이 물건을 두 번 넣은 것과 같으므로, ‘각 물건은 최대 한 번만 선택할 수 있다’는 조건에 어긋난다.

  2. 배낭에는 이 물건 하나만 넣을 수 있으므로 올바른 dp[4] 값은 5다.

  3. 용량을 큰 것부터 작은 것 순으로, 즉 4, 3, 2 순으로 갱신해야 한다. 그러면 dp[c]를 계산할 때 읽는 dp[c-2]는 아직 현재 물건을 처리하기 전의 결과이므로, 같은 회전에서 현재 물건을 반복해서 사용하지 않게 된다.

14.8.2   프로그래밍 연습

1.   계단을 오르는 방법의 수

계단은 총 n칸이다. 한 번에 1칸 또는 2칸만 올라갈 수 있으며, 정확히 n번째 칸에 도착해야 한다. 서로 다른 방법이 모두 몇 가지인지 계산하라. n >= 1이며, 각 걸음에서 1칸을 오르는지 2칸을 오르는지에 따라서만 방법을 구분한다. 일차원 동적 계획법 배열을 사용하라. 상태 두 개만 유지하는 공간 최적화 방식은 아직 사용하지 마라.

풀이 힌트
  1. i번째 칸에 도착하는 마지막 걸음은 1칸 또는 2칸을 오르는 것뿐이다.
  2. 따라서 dp[i] = dp[i-1] + dp[i-2]다.
  3. n이 1과 2인 경우를 먼저 처리한 뒤, 세 번째 칸부터 테이블을 채운다.

LeetCode

2.   0-1 배낭 문제

길이가 같은 배열 wgt와 val이 주어진다. i번째 물건의 무게 wgt[i]는 양의 정수이고, 가치 val[i]는 음이 아닌 정수다. 배낭 용량 cap은 음이 아닌 정수다. 각 물건은 최대 한 번만 선택할 수 있다. 총무게가 cap을 넘지 않는 조건에서 배낭에 넣을 수 있는 최대 총가치를 구하라. 일차원 동적 계획법으로 구현하라.

풀이 힌트
  1. 길이가 cap + 1인 배열 dp를 초기화한다. dp[c]는 용량 상한이 c일 때의 최대 가치를 나타낸다.
  2. 물건 i를 처리할 때 ‘선택하지 않는 경우’의 dp[c]와 ‘선택하는 경우’의 dp[c-wgt[i]] + val[i]를 비교한다.
  3. 같은 회전에서 현재 물건을 반복해서 선택하지 않도록 용량을 반드시 큰 것부터 작은 것 순으로 갱신해야 한다.
댓글로 의견이나 질문, 제안을 남겨 주세요