[코드트리 챌린지] 7주차 - DP Ⅱ

0) 들어가기 앞서

지난 6주차는 투 포인터를 학습하였고, 많은 난관을 맞이했다. 또한 TreeSet과 같은 자료구조에 대해 알지 못해 해설을 참고하는데도 어려움이 있었다.

1) 실력 진단 결과

예상대로 실력진단 결과 점수가 낮아졌다. 이전에 완료하지 못한 유형을 다시 풀이할 수 있게 되어 오히려 좋다. 학습 조언에 따라 이번 주차는 IL단계의 DP 유형 아이템을 적절히 고르는 문제 부터 학습한다!

실력 진단 테스트에서 출제된 DP유형 문제를 복기하여 다시 풀이 해보았다.

• 개선할 점
  1. 문제를 제대로 읽지 않았다. 도착지점이 (n,1) 즉, [n-1][0] 이라는 것을 놓쳤다.
  2. '-1' 을 지나지 않도록 하기 위한 방법으로 if grid[i][j] == -1 : dp[i][j] = -sys.maxsize 와 같이 시도하였었다.
• 풀이
  • 현재 좌표의 값이 -1 인 경우, 현재 좌표로 지나올 수 있는 두 경로가 모두 -1 인 경우, 둘 중 하나의 경로가 -1 인 경우, 앞선 경우들이 아닌 경우(즉, -1을 지나지 않은 경우) 로 분기하여 DP를 진행했다.
  • 시간복잡도는 O(n^2) 으로 풀이했다.

2) DP Ⅱ

동전 거슬러주기, 배낭 채우기, 부분수열 구하기 등 주어진 리스트의 원소들을 적절히 선택하여 전체 해를 구하는 유형이다. 코드트리에서는 '아이템을 적절히 고르는 문제' 유형이다.

크게, (1) 주어진 원소를 중복해서 사용해도 되는 경우와 (2) 주어진 원소를 한 번만 사용해야 하는 경우로 구분된다.

DP배열을 0이 아닌 -sys.maxsize 등으로 초기화 해주는데, -sys.maxsize 의 경우 '아직 최초의 솔루션을 찾지 못함'을 뜻하는 반면, 0의 경우 '한 번 검증을 했으나 그 결과 0임'을 뜻하기 때문이다.
내가 작성한 토론탭 질문글의 답변에 의하면 문제에 따라 0으로 초기화 되어, 마치 이를 시작값으로 간주해, 조건을 충족할 수 있는 상태로 취급될 수 있다고 한다. 따라서 0이 아닌 -sys.maxsize 등으로 초기화 하는 것이 안전하다고 결론을 내렸다.

문제1

• 동전 거슬러주기 (링크 : https://www.codetree.ai/missions/2/problems/coin-change?&utm_source=clipboard&utm_medium=text)

리뷰

• 주어진 원소를 중복해서 사용해도 되는 경우에 해당된다. 이 경우, DP 배열을 정방향으로 순회하며 주어진 원소가 조건을 충족하도록 고른다(대입한다).

# 예시 코드
import sys
n, m = map(int, input().split())
coins = list(map(int, input().split()))

dp = [sys.maxsize] * (m+1)
dp[0] = 0

for i in range(1, m+1):
    for coin in coins:
        if i >= coin:
            dp[i] = min(dp[i], dp[i - coin] + 1)


print(dp[m] if dp[m] != sys.maxsize else -1)

문제2

• 부분 수열의 합이 m (링크 : https://www.codetree.ai/missions/2/problems/the-sum-of-the-subsequences-is-m?&utm_source=clipboard&utm_medium=text)

리뷰

• 주어진 원소를 한 번만 사용해야 하는 경우에 해당된다. 이 경우, 바깥 for문을 주어진 원소를 순회하는 동안 내부 for문에서 DP 배열을 역방향으로 순회하며 주어진 원소가 조건을 충족하도록 고른다(대입한다).
• 이것이 가능한 이유는 거꾸로 for문이 진행되어 동일한 원소를 2번 갱신하지 않기 때문이다.

# 예시 코드
import sys
n, m = map(int, input().split())
arr = list(map(int, input().split()))
dp = [sys.maxsize] * (m+1)
dp[0] = 0

for a in arr:
    for j in range(m, -1, -1):
        if j >= a:
            if dp[j-a] == sys.maxsize:
                continue
            
            dp[j] = min(dp[j], dp[j-a] + 1)


print(dp[m] if dp[m] != sys.maxsize else -1)