크래프톤정글 4주차; TIL 2 - DP 동전 문제, LCS, 파이썬에서 2차원 배열 주의사항, 배낭 문제

2022-11-20

동적계획법; 계단 오르기와 동전 문제

참고: Chan-Su Shin | 알고리즘 - 동적계획법 소개

무엇?

DP 알고리즘 강의 예제 계단 오르기 문제와 백준 9084번의 동전 문제를 비교해보고 풀어보기

• 계단 오르기 문제
  1. 계단을 한 칸, 혹은 두칸으로만 오를 수 있다고 가정
  2. n 칸에 오를 수 있는 경우의 수 구하기
• 백준 9084 동전 (예제2로 설명)
  1. 1, 5, 10원 짜리 동전이 있다고 가정
  2. 해당 동전들로 20원을 만들 수 있는 경우의 수 구하기

왜?

동전 문제의 힌트를 계단 오르기 예제에서 얻을 수 있었음.

어떻게?

• 계단 오르기 문제

  1. n칸에 도착한 모습을 그려본다.
  2. 우리는 한 칸이나 두 칸만 오를 수 있기 때문에, 그곳에 도착하려면 우리는 n칸에서 한 칸 뒤인 n-1칸, 혹은 두 칸 뒤인 n-2칸에 있었을 것이다.
  3. 따라서, n칸에 도착하는 경우의 수는 n-1칸까지 도착했을 때의 경우의 수와, n-2칸까지 도착했을 때의 경우의 수의 합이다.
  4. 이를 식으로 표현하면; 경우의수[n] = 경우의수[n-1] + 경우의수[n-2]

• 동전 문제

  1. 위와 비슷하게, 20원을 만들기 위해서 우리가 가지고 있는 동전을 생각해본다.
  2. 우리가 20원어치를 만들어내기 한 단계 전은 다음과 같은 세 가지 경우가 있었을 것이다.
     1. 20원에서 1원을 뺀 19원인 경우
     2. 20원에서 5원을 뺀 15원인 경우
     3. 20원에서 10원을 뺀 10원인 경우
  3. 따라서 우리가 구하고자 하는 최종 경우의 수는 19원, 15원, 10원일 때의 경우의 수와 관련이 있다.
     • 예를 들어, 내가 9원을 만들고 싶다고 가정하자.
       우리는 1원과 5원을 이용할 수 있지만, 먼저 1원만으로 만드는 경우, 5원만으로만 만드는 경우를 생각해본다.
       1원으로 9원을 만들 수 있는 경우는 하나밖에 없다. 1원을 9개 사용하는 것이다.
       그러면 5원으로만 9원을 만드려면 어떻게 할까? 만들 수 없다.
       하지만 방법이 있는데, 4원을 만들어 내면 된다. 5 + 4 = 9가 되므로.
       그럼 4원은 어떻게 만드냐면, (우리가 이미 구해놨을) 4를 만들어내는 경우의 수를 이용하면 된다.
       이 경우엔 1원 네개로 만드는 한 가지 방법만이 있을 것이다.
       따라서 9원을 만드는 경우의 수는 이 합인 두 가지다.
  4. 여기까지 생각해냈다면, 제일 중요한 것은 올바른 순서대로 경우의 수를 계산하는 것이다. ('위상정렬 대로’라고 강의에서 말했었다. 들을 때는 완전히 이해하지 못했는데…)
  5. 가장 작은 가치(1원)의 돈부터 20원까지의 경우의 수를 계산하고, 그 다음 가치(5원)의 돈의 경우의 수를 모두 구한다. 그리고 앞서 구한 경우의 수(1원일 때 구한 경우의 수)에 더한다. 가장 큰 가치의 돈인 10원으로 만들 수 있는 경우의 수를 모두 구하여 미리 구한 경우의 수에 더한다; 돈[k] = 돈[k] + 돈[k-c]

• 내가 놓친 부분
  19원, 15원, 10원과 연관이 있을거라고 생각했다. 하지만 단순히 저 세 가지 경우의 수를 한번에 다 더하는 것으로는 답이 나오지 않았다!
  강의를 들으면서 작은 문제의 솔루션을 ‘올바른 순서대로’ 구하는 것이 중요하다고 했는데, 이 부분을 생각해내는데 오래 걸렸다. ㅠㅠ

import sys

T = int(sys.stdin.readline())

for _ in range(T):
    N = int(sys.stdin.readline())
    coins = list(map(int, sys.stdin.readline().split()))
    M = int(sys.stdin.readline())

    # 경우의 수를 담은 DP 테이블
    table = dict.fromkeys(range(1,M+1), 0)

    # 돈의 가치에 따라 경우의 수 계산하기
    for c in coins:      
        for k in table.keys():  
            if k == c:          # 동전과 돈의 가치가 같을때, 경우의 수는 하나밖에 없음
                table[k] += 1
            elif k > c:         # 돈의 가치가 동전의 가치보다 클 때, 미리 구한 경우의 수에 동전의 가치만큼 뺀 값의 경우의 수를 더함
                table[k] += table[k-c]

    print(table[M])

2022-11-21

동적계획법; LCS 문제

참고: https://www.youtube.com/watch?v=EAXDUxVYquY&list=PLsMufJgu5932XYejsOwcUDJ2F75f56nrl&index=26

무엇?

다이나믹 프로그래밍으로 백준 9251번 LCS 문제 해결하기

• 두 문자열의 LCS(longest common subsequence, 최장 공통 부분 수열)의 길이 찾기
  1. 두 문자열이 A, B가 주어진다(문자열의 길이는 서로 다를 수 있다)
  2. 공통되는 부분 문자열 중 가장 킨 길이를 찾는다.
     • 공통 부분 문자열이란, 길이가 1, 2 … n이면서 A, B 공통으로 포함되는 문자열을 말함
     • 문제에서 ACAYKP와 CAPCAK의 길이가 1인 공통 부분 문자열: A, C, P, K
     • 길이가 2인 공통 부분 문자열: AC, AK, AP, CP 등 …

왜?

어떻게?

• 해 분석
  • 문자열 A, B와 길이를 나타내는 i, j이 있을 때, A_i = A₁, A₂, A₃ … A_i이고 B_j = B₁, B₂, B₃ … B_j이라고 생각해보자.
  • 따라서, LCS(i, j) = A[:i+1]과 B[:j+1] 의 LCS
  • 그러면 우리가 알고자 하는 것은 n과 m이 각각 A와 B의 길이 일때의 LCS임
  • 임의의 A_i와 B_j를 가정하고, 비교할 때 나올 수 있는 경우는 다음 두 가지이다.
    1. 마지막 문자 a_i와 b_j가 같은 경우
       • 마지막 문자를 LCS 문자로 추가할 수 있고, 이미 구해 놓았을 LCS 길이에 +1을 할 수 있다
       • 따라서, LCS(i, j) = LCS(i-1, j-1) + 1
    2. 마지막 문자 a_i와 b_j가 다른 경우
       • a_i와 b_j는 LCS의 마지막 문자열이 될 수도 있고 안 될 수도 있다. 하지만 둘 다 LCS의 마지막 문자열이 될 수는 없음
       • 따라서, A_i와 B_j-1의 LCS 길이, A_i-1과 B_j의 LCS 길이 중 더 긴 것을 LCS(i, j)로 정한다.
       • LCS(i, j) = max(LCS(i, j-1), LCS(i-1, j))
  • ▽ DP 테이블!!
    
• 추가
  • DP 이차원 테이블을 만들 때 베이스 조건을 만들어주기 위해 행과 열의 인덱스 0은 모두 0으로 초기화
  • LCS 값을 넣어주는 것은 인덱스 행과 열의 인덱스 1부터 시작
    • LCS = [[0] * (len(B)+1) for _ in range(len(A)+1)] 이런 식으로 해야 함! 처음에 LCS = [[0] * (N+1)] * M 이렇게 만들었더니 LCS[1][2] 인덱스를 수정하면 모든 행의 인덱스 2의 값이 수정되었다. 포인터 관련 때문인 거 같음… ?!
  • LCS의 길이 말고 실제 LCS 문자열을 알고 싶다면, LCS[i][j] = LCS[i-1][j-1] + 1이 된 케이스를 추적하면 됨(마지막부터 거꾸로 역추적한다, DP 이차원 테이블 상에서 대각선으로 값을 내려 받은 문자, 여러개 있을 수도 있음)

파이썬에서 2차원 배열 만들 때 조심할 점

참고: https://9kilometer.postype.com/post/3215792

무엇?

왜?

위의 LCS 문제를 풀면서 파이썬 이차원 배열 만드는데 [[element] * numcols]] * numrows 방식으로 했다가 원하는 결과가 안 나와서 찾아보았다.
DP 테이블을 이차원으로 만들어야 할 때가 있으므로~~

어떻게?

리스트 컴프리헨션 방식으로 쓰거나, for-append 방식을 이용해야 함.

동적계획법; 백준 12865번 평범한 배낭

참고: 에드위드 파이썬으로 배우는 알고리즘 기초 | 22. 0-1 배낭 문제와 동적 계획법
https://www.acmicpc.net/board/view/93599

무엇?

동적계획법에서 유명한 냅색(knapsack) 문제!

왜?

어떻게?

강의에 나온 대로 재귀 버전으로 했다가 메모리 초과, 시간 초과로 반복문 사용으로 다시 찾아보았다.
아이템을 배낭에 담을 수 있는 경우에, (담았을 때 무게 제한을 넘지 않는 경우)
그것을 담기 전의 가치와 담은 경우의 가치를 비교하여 최댓값을 반환한다.

import sys

sys.setrecursionlimit(10**6)

N, K = map(int, sys.stdin.readline().split())
W = []   # 아이템의 무게 리스트
P = []   # 아이템의 가치

for _ in range(N):
    w, v = map(int, sys.stdin.readline().split())
    W.append(w)
    P.append(v)

# 재귀버전 → 백준에서는 시간 초과, 메모리 초과 뜸 
def knapsack2(i, K, W, P):      # 인덱스, 무게, 무게 리스트, 가치 리스트
    if (i < 0 or K <= 0):       # 아이템이 0개이거나 무게가 0일 때
        return 0
    if (W[i] > K):  # 아이템의 무게가 무게 제한보다 클 때
        return knapsack2(i-1, K, W, P)  # 아이템을 한 개 뺀 상태로 돌아감(배낭에 담지 않음)
    else:           # 아이템의 무게가 무게 제한과 같거나 작을 때
        left = knapsack2(i-1, K, W, P)        # left = 배낭에 담지 않았을 경우의 가치
        right = knapsack2(i-1, K-W[i], W, P)  # right = 배낭에 담았을 경우의 가치
        return max(left, P[i] + right)

profit = knapsack2(len(W)-1, K, W, P)
print(profit)


# 반복문 버전
# 참고: https://www.acmicpc.net/board/view/93599
sum_value = [0]*(K+1)
items = []

for _ in range(N):
    w, v = map(int, sys.stdin.readline().split())
    items.append((w, v))

for item in items:
    w, v = item

	for i in range(K, w-1, -1):   # 무게제한부터 해당 무게까지 -1씩 감소시키면서
        # 배낭에 담기 전의 최대 가치 + 담은 후의 최대 가치 중 최댓값
        sum_value[i] = max(sum_value[i], sum_value[i-w]+v)  

print(sum_value[-1])