7주차 코딩테스트 요점(dp)

1. 계단 오르기(백준 2579)

# 32424KB   36ms

import sys

n = int(sys.stdin.readline().strip())

list1 = [0]

for i in range(n):

    list1.append(int(sys.stdin.readline().strip()))

dp_max = [0]*(n+1)

if n >= 1:

    dp_max[1] = list1[1]

if n >= 2:

    dp_max[2] = list1[1] + list1[2]

def dp(n):

    if (dp_max[n] != 0) or (n==0):

        return dp_max[n]

    if n>=3:

        dp_max[n] = max((dp(n-2)+list1[n]), (dp(n-3) + list1[n-1]+ list1[n]))

        return dp_max[n]

print(dp(n))

위 코드는 계단오르기 문제(백준 2579)문제를 탑다운 방식의 dp(동적 계획법) 방법으로 푼 코드 입니다. 

처음계단 밟았을때 (1칸오르기)와 두번째 계단 밟았을때(1칸 1칸오르기)를 초기 값으로 주고 각 계단을 밟을 때의 값을 2칸전에서 2칸올라 이번 계단을 밟을때, 3칸전에서 2칸 1칸 올라 이번계단을 밟을때의 큰 값으로 주는 방식입니다. 여기서 중요한 점은 이번 계단을 밟는 경우의 수를 2개만 계산 한 이유는 1칸 1칸 1칸 연속으로 밟을 수 없어 (2칸 1칸 1칸) (2칸) 만 계산 하면 다 계산 됩니다. 시작이 무조건 2칸으로 시작하면 저번 마지막 오른 계단의 수는 고려하지 않아도 됩니다. 시작이 2칸인 경우는  (2칸 1칸 1칸) (2칸)만 고려하면 됩니다. 

그러하고 n == 0 즉 시작지점과 dp_max[n] 이 0이 아닌경우(계산이 된 경우)는 return하여 아래에서부터 채워져 최종 결과를 return합니다. 

 

탑다운 방식에서는 재귀를 사용하여 문제를 풀고, 이미 계산된 값을 메모이제이션(memoization) 기법을 통해 저장해두고 재사용합니다.

2. 평범한 배낭(백준 12865)

# 32424KB   36ms

import sys

n, k = sys.stdin.readline().strip().split(' ')

k = int(k)

items = []

for _ in range(int(n)):

    w, v = map(int, sys.stdin.readline().strip().split(' '))

    items.append((w,v))

max_bag = [0] * (k+1)

def bag(k):

    for w, v in items:

        for i in range(k, w-1, -1):

            max_bag[i] = max(max_bag[i], max_bag[i-w] + v)

           

bag(k)

print(max_bag[k])

위 코드는 평범한 배낭 문제(백준 12865)문제를 바텀업 방식의 dp(동적 계획법) 방법으로 푼 코드 입니다. 

물건의 수 n과 배낭의 용량 k, 각 물건의 무게 w와 가치 v를 받습니다. 물건의 무게와 가치는 items 라는 리스트 안에 튜플로 저장합니다. 그 후 아이템을 하나씩 꺼내 for문을 돌리게 됩니다. 그 후 무게를 역순으로 하여 최대 값을 계산합니다. 

역순으로 계산한다는 점이 중요한 포인트 입니다.! 

위 정리와 같이 역순으로 하지 않으면 같은 아이템을 여러번 고를 수 있게 됩니다. 처음에는 정순으로 계산하고 뽑은 아이템의 인덱스를 리스트에 담아 그 인덱스가 있으면 집지 않는 식으로 하였지만 결국 실패 하였습니다.  위 표와 같이 역순으로 계산하면 dp[6], dp[4], dp[2] 모두 10이라는 값으로 들어가게 됩니다. 그 후 다른 아이템을 집음으로써 최대 값을 계산하게 됩니다. 또한 아이템을 무게 7을 먼저 집어서 3과 4를 집은걸 계산하지 못하는것도 아닙니다. 나중에 다시 계산되어 큰 값으로 들어가기 때문입니다. 

이번 문제는 계단 오르기와 다르게 함수 한번 사용으로 bag_max 리스트의 값을 모두 각 무게의 최대 가치로 채운 후 bag_max[k]의 값을 출력하는 방식입니다. 

 

바텀업 방식의 dp문제는 재귀를 사용하지 않고 반복문을 통해 max_bag 배열을 갱신하는 방식입니다. 

 

3. LCS(백준 9251)

LCS문제는 단어수*단어수로 2차원 배열을 만든 후 각 칸의 최대 값을 채워 나가는 방식으로 풀었습니다. 첫 세로줄과 가로줄은 처음 단어 기준으로 단어가 나오기 전에는 0 나온 후에는 1로 채우고 시작합니다. 그 후 각 칸은 인덱스에 맞는 단어들이 같으면 대각선 값에서 +1 다르면 위와 왼쪽값중 max값을 택합니다. 그렇게 끝까지 채운후 마지막 값을 출력하면 됩니다. 

제가 원래는 인덱스의 단어들이 같으면 위와 왼쪽 값의 max에 +1인줄 알았으나 이방법은 비교단어가 2개인데 3이상의 값이 나올수 있다는 점을 알았습니다. 대각선에서 +1 하는 이유는 원래 벼엘에서 단어가 동시에 추가되었을때 같으면 +1 이기 때문입니다. 또한 2차원 배열이 아닌 1차원 배열로 계속 초기화 및 갱신하면서 하는 방법도 있다고 합니다.