DP(Dynamic Programming)이란? - 스티커, 동전, LCS, 행렬 곱셈 순서

wnajsldkf·2023년 5월 1일
0

Algorithm

목록 보기
55/58
post-thumbnail

동적 프로그래밍이란?

동적 프로그래밍은 큰 문제를 풀 때, 큰 문제의 일부인 작은 문제를 푸는 과정에서 발생하는 중복을 해결하는 방법이다.

이때 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있는 것을 최적 부분 구조(Optimal Substructure)를 가졌다고 표현한다.

대표적인 예시로 피보나치 수열이 있다.

피보나치 수열은 다음의 정의를 갖는다.

f(n) = f(n-1) + f(n-2)

f(1) = f(2) = 1

즉, n은 n-1과 n-2 피보나치 수를 모두 갖고 있다.

만약 이 문제를 재귀호출로 푼다면 어떨까?

fib(n)
{
	if (n == 1 or n == 2)
		then return 1
	else return (fib(n-1) + fib(n-2))
}

이렇게 푸는 방식은 매우 비효율적인 방식이다.

예를들어, fib(5)를 구하면 fib(1)과 fib(2)도 중복으로 계산해야 한다.

숫자가 더 커진다면 중복 호출의 정도는 더 심해질 것이다.

만약 fib(3)을 매번 호출하지 않고, 실행 결과를 잠시 저장해두고 필요할 때 사용하는 것은 어떨까?

이렇게 부분 결과를 저장해두고 사용하는 것이 동적 프로그래밍의 핵심이다.

또 중복 호출로 인해 비효율적인 연산을 여러번 발생하는 경우는 동적 프로그래밍을 사용하기 적합한 예시다.

동적 프로그래밍 구현하기

bottom-up

아래에서 위로 저장해가면서 해를 구하는 것을 말한다.

fibo(n)
{
	f[1] <- f[2] <- 1;
	for i <- to n
		f[i] <- f[i-1] + f[i-2];
	return f[n];
}

top-down

중복된 재귀호출을 피하기 위해 한 번 호출한 것을 메모해두고 사용하는 방식을 말한다. 이때 메모하는 행위를 Memoization이라고 한다.

fibo(n)
{
	if(f[n] != 0) then return f[n];
	else {
		if (n = 1 or n = 2)
			then f[n] <- 1
			else f[n] <- fib(n-1) + fib(n-2);
		return f[n];
	}
}

동적 프로그래밍 적용 예시

대표적인 동적 프로그래밍 문제를 살펴보자.

P9465. 스티커

이 문제는 스티커를 떼어낼 때마다 점수를 매길 때, 점수의 최댓값을 구하는 것이다.

스티커를 떼어낼 때 제한 조건은 다음과 같다.

  • 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 뗄 수 없다.

이러한 제약 조건을 고려하여 노란색 별이 표시된 스티커를 제거한다면, 1) 직전에 스티커를 제거한 경우2) 직전에 스티커를 제거하지 않은 경우 를 확인할 수 있다. 이때 두 가지 경우에서 더 큰 경우를 저장하는 것이다.

빨간색 별도 마찬가지다.

이 규칙을 재귀적으로 나타내면 다음과 같다.

dp 배열은 큰 해를 구하기 위해 계산한 작은 문제들을 저장하는 최적 부분 구조 배열이고, arr 배열은 스티커 점수를 저장한다.

만약 i가 1이라면,

dp[0][0] = arr[0][0]

dp[1][0] = arr[1][0]

i가 2라면

dp[0][1] = dp[1][0] + arr[0][1]

dp[1][1] = dp[0][0] + arr[1][1]

i가 3 이상이라면

dp[0][i] = max(dp[1][i-1] + arr[0][i], dp[1][i-2] + arr[0][i])

dp[1][i] = max(dp[0][i-1] + arr[1][i], dp[0][i-2] + arr[1][i])

이렇게 스티커를 떼어가다가 최종적으로 dp[0][n-1]과 dp[1][n-1] 중에 더 큰 것이 답이다.

⭐️ 코드

t = int(s.readline())

for i in range(t):
	n = int(s.readline())
	
	arr = [list(map(int, s.readline().split())), list(map(int, s.readline().split()))]
	
	for k in range(1, n):
		# 두번째 값까지는 대각선 값 더해주기
		if k == 1:
			s[0][k] += s[1][k-1]
			s[1][k] += s[0][k-1]
		# 세번째 값부터 대각선과 대각선 왼쪽을 살펴본다.
		else:
			s[0][k] += max(s[1][k-1], s[1][k-2])
			s[1][k] += max(s[0][k-1], s[0][k-2])
	print(max(s[0][n-1], s[1][n-1]))

P9084. 동전

이 문제는 여러 단위의 주어진 동전을 가지고, 목표 금액을 만들 수 있는 경우의 수를 구하는 것이다.

예를들어, 2원과 4원으로 10원을 만들어보자.

첫번째로 2원만 사용하겠다.

2원으로 0원을 만드는 방법은 2원이 0개만 있으면 되기 때문에 방법이 한 가지이다.

다음은 2원과 4원을 함께 사용한다.

2원과 4원을 가지고 8원을 만드는 방법은 다음과 같다.

  • 2 + 2 + 2 + 2
  • 2 + 2 + 4
  • 4 + 4

일단 8원에서 내가 가진 4원을 뺀 나머지 금액인 4원으로 만들 수 있는 가지수를 확인하는 것이다.

즉, dp[8] = dp[8-4] = dp[4]가 되어 dp 테이블에서 인덱스 4 값을 갖는다.

2원만 가지고 만들 수 있는 경우의 수는 1가지이고, 2원과 4원을 함께 사용하여 만들 수 있는 경우의 수는 2가지 이므로 총 3가지 경우의 수를 갖는다.

⭐️ 코드(2차원)

from sys import stdin as s
import sys

T = int(s.readline())

dp = [0]*10001

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

	dp = [[0] * (M + 1)for _ in range(N + 1)]

	for i in range(N + 1):
		dp[i][0] = 1
	
	for j in range(1, N + 1):
		for k in range(1, M + 1):
			dp[j][k] = dp[j - 1][k]
			if k - coins[j - 1] >= 0:
				dp[j][k] += dp[j][k - coins[j - 1]]
	
	print(dp[N][M])

⭐️ 코드(1차원)

앞에서 계산한 동전 단위로 만들 수 있는 경우의 수를 모두 기억하지 않고, 값을 업데이트해도 된다.

from sys import stdin as s
import sys

T = int(s.readline())

dp = [0] * 10001

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

	dp = [0] * (M + 1)
	dp[0] = 1

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

P9251. LCS

LCS(Longest Common Subsequence)는 두 문자열에 공통적으로 나타나는 부분 순서를 말한다.

두 문자열을 살펴보자.

  • ACAYKP
  • CAPCAK

LCS 문제의 최적 부분 구조는 다음과 같다.

두 수열을 X, Y라고 하고 X 수열 인덱스를 m, Y 수열 인덱스는 n이다.

이때 1) X[m]과 Y[n]이 같은 경우2) 그렇지 않은 경우에 따라 LCS 길이는 다르게 업데이트된다.

1) X[m]과 Y[n]이 같은 경우

2)X[m]과 Y[n]이 다른 경우

이를 점화식으로 표현하면 다음과 같다.

그럼 두 수열을 비교하는 과정을 2차원 배열을 이용해 풀이하겠다.

다음은 위에서 구한 점화식이 반영된 2차원 배열이다. 이차원 배열의 부분 문제의 답을 저장하면서 풀이하여 나온 배열의 가장 마지막 원소인 dp[m][n]이 답이 된다.

⭐️ 코드

from sys import stdin as s
import sys

a = s.readline().rstrip()
b = s.readline().rstrip()

n = len(a)
m = len(b)

dp = [[0 for _ in range(m+1)] for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, m+1):
        if a[i-1] == b[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:   # 다르다면
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

for i in dp:
    print(*i)

print(dp[n][m])

P11049. 행렬 곱셈 순서

행렬은 행렬의 결합 법칙에 의해 어떤 순서로 계산을 해도 연산 결과가 같다.

이 문제 예시처럼 A의 크기가 5x3이고, B의 크키가 3x2, C의 크기가 2x6인 행렬곱을 계산하면,

  • AB X C 연산 횟수는 (AB의 행렬 연산) + (AB 행렬 연산 결과) X C 행렬로 5x3x2 + 5x2x6 = 30 + 60 = 90번이다.
  • A X BC 연산 횟수는 A 행렬 X (BC 행렬 연산 결과) + (BC 행렬 연산) 로 5 X 3 X 6 + 3 X 2 X 6 = 90 + 30 = 120번이다.

이때 행렬의 계산 비용을 가장 줄이려면 어떤 순서로 계산해야할까?

위 예시처럼 ABC 행렬에서 AB 행렬과 BC 행렬은 최적 부분 구조 관계를 갖는다. 따라서 각 행렬의 최소 비용과 두 행렬을 곱하는 비용을 더한 값이 답이 된다.

그렇다면 다음 행렬이 주어졌을 때 계산 과정을 알아보자.

  • 행렬 A: 5 x 3
  • 행렬 B: 3 x 2
  • 행렬 C: 2 x 6
  • 행렬 D: 6 x 5

각 좌표가 의미하는 바는 다음과 같다.

A 행렬과 B 행렬의 연산 횟수를 구한다.(5로 시작하여 2로 끝나는 행렬) 두 행렬 계산 방법은 AB만 존재한다.

B행렬과 C 행렬의 연산 횟수를 구한다.(3으로 시작하여 6으로 끝나는 행렬) 두 행렬 계산 방법은 BC만 존재한다.

A행렬, B행렬, C행렬의 연산 횟수를 구한다.(5로 시작하여 6으로 끝나는 행렬)

A행렬 X (B행렬 X C행렬), (A행렬 X B행렬) X C행렬을 하는 두 가지 방법이 있다. 이때 더 작은 값을 저장하면 된다.

A행렬, B행렬, C행렬, D행렬을 구하는 방법도 다음과 같다.

⭐️ 코드

python으로 제출하면 시간초과 발생한다.

from sys import stdin as s
import sys

s = open("input.txt", "rt")

n = int(s.readline())

matrix = [list(map(int, s.readline().split())) for i in range(n)]
dp = [[0] * n for i in range(n)]    # 행렬이 하나라면 비용이 0이다.

for cnt in range(n-1):
    for i in range(n-1-cnt):
        j = i + cnt + 1

        dp[i][j] = 2**31    # 가장 큰 수로 업데이트
        for k in range(i, j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + matrix[i][0]*matrix[k][1]*matrix[j][1])

print(dp[0][-1])

DP문제는 유형을 파악하는 것과 점화식을 찾는 부분에서 경험이 필요하다고 생각한다. 다양한 문제를 풀이하면서 주어진 시간 안에 적절한 점화식을 찾고 코드로 구현하는 역량을 키워보자.

Reference

profile
https://mywnajsldkf.tistory.com -> 이사 중

1개의 댓글

comment-user-thumbnail
2023년 5월 2일

잘 보고있어요~

답글 달기