동적 프로그래밍에 대해 정리해보려고 한다.
꽤나 짜치는 동적 프로그래밍 이름의 유래.
기본 개념
동적 프로그래밍 (Dynamic Progamming, DP) 란 복잡한 문제를, 여러 개의 작은 하위 문제로 나누어 해결하고자 하는 알고리즘 설계 기법 중 하나이다.
각 하위 문제의 해결 결과를 저장하고, 재사용함으로써 전체 문제의 해결 시간을 단축 시킨다.
고로 중복되는 하위 문제가 많은 경우에 효과적이다.
구현 방법
동적 계획법을 구현하는 방법으로는 크게 두가지가 있다.
1. 탑 다운
2. 바텀 업
탑다운 방식은 큰 문제를 작은 문제로 나누어 해결하는 '분할 정복 방식' 에 '메모이제이션'을 추가한 형태이다.
재귀호출을 사용하여 구현된다.
바텀업 방식은 가장 작은 하위 문제부터 시작하여, 점차 큰 문제로 확장해 나가는 방식으로, 일반적으로 반복문을 사용하여 작은 문제부터 차례대로 해결하며, 이 과정에서 각 문제의 해결 결과를 배열에 저장하여 사용한다.
적용 예시
동적 계획법은 다양한 문제에 적용할 수 있지만 대표적으로 '피보나치 수열', '최장 증가 부분 수열(LIS)', '최소 편집 거리', '배낭 문제' 등이 있다.
작은 문제의 해결결과를 활용하여 큰 문제를 해결할 수 있는 구조? DP활용을 유념해봐야 한다.
문제 예시들
문제 접근:
정수 X를 입력 받고,
1. 3으로 나누어 떨어지면 3으로 나누고,
2. 2로 나누어 떨어지면 2로 나누고
3. 그렇지 않으면 1을 빼는
이 세가지 연산을 통해 X를 1로 만ㄷ르건데 연산을 사용하는 횟수의 최솟값을 구하는 문제이다.
우선 이 문제가 왜 DP로 푸는게 좋을까?
이 문제는 작은 수의 결과값을 이용해 큰 수의 정답을 만드는 구조이며,
중복 계산이 많고, 부분 문제의 최적해가 전체 문제의 최적해를 구성하기 때문에
DP에 매우 적합한 전형적인 문제
탑다운? 바텀업?
모든 수를 다 구하지 않아도 될 때 : Top-Down DP가 유리
모든 수를 다 구해야 할 때 : Bottom-Up DP가 유리
-> Bottom-Up 채택
바텀 업 해답 및 풀이
import sys
input = sys.stdin.readline
X = int(input())
dp = [0] * (X + 1) # dp[i] : i를 1로 만들기 위한 최소 연산 횟수 X+! 인 이유는 인덱스가 0 부터 시작이니까 조정해준 것
for i in range(2, X + 1):
# dp[i]를 dp[i-1] 이전 dp에 + 1 하는경우로 초기화
dp[i] = dp[i - 1] + 1
# X가 2로 나누어 떨어지면, 나누는 경우와 비교
if i % 2 == 0:
dp[i] = min(dp[i], dp[i // 2] + 1)
# X가 3으로 나누어 떨어지면, 나누는 경우와 비교
if i % 3 == 0:
dp[i] = min(dp[i], dp[i // 3] + 1)
print(dp[X]) # X를 1로 만들기 위한 최소 연산 횟수 출력dp를 X를 1로만들기 위한 최소 연산 횟수로 정의.
1로 빼는 것, 2로 나누는 것 , 3으로 나누는 것의 크기를 비교하며 dp에 저장
dp[X]를 출력하면 끝
난이도 : 실버 3
문제접근
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하는 문제.
(단, 숫자의 순서가 다르면 다른 경우로 셈.)
dp[n] 을 n을 1,2,3의 합으로 나타내는 방법의 수 로 선언하면 dp[n+1], dp[n+2] 이런것들도 dp[n]을 활용하면 수월하게 나타낼 수 있으니 dp로 풀 수 있는 문제이다. 라고 이해했다.
어떤 수 n을 만드는 방법은
n-1에 1을 더한 경우
n-2에 2를 더한 경우
n-3에 3을 더한 경우
세 가지 경우의 수의 합이다.
여기서 점화식을 구할 수 있다
dp[n] = dp[n-1] + dp[n-2] + dp[n-3]
이를 통해 n에 관련된 dp들을 다 저장해놓고 dp[n]을 출력해주면 된다.
해답 및 풀이
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
n = int(input())
dp = [0] * (max(4,(n+1))) #dp[4]부터 아래 점화식이 성립되므로 처리해줌
dp[1] = 1
dp[2] = 2
dp[3] = 4
for i in range(4, n+1):
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
print(dp[n])
난이도 : 실버 3
문제 접근
2n 직사각형을 1x2, 2x1 타일로 채우는 방법의 수 10,007로 나눈 나머지를 구하는 문제.
2n 직사각형을 1x2, 2x1 타일로 채우는 방법의 수 를 dp로 저장하여 풀면 될 것 같다.
2*n 직사각형을 타일로 채우려면 두가지 경우가 있다.
n-1 까지 채우고 + 1 하는 경우
n-2 까지 채우고 눞혀서 채우는 경우 +1
결국 dp[n] = dp[n-1] + dp[n-2] 가 된다.
해답 및 풀이
import sys
input = sys.stdin.readline
n = int(input())
dp = [0] * (max(3,(n+1)))
dp[1] = 1
dp[2] = 2
for i in range(3,n+1):
dp[i] = dp[i-1] + dp[i-2]
print(dp[n] % 10007)
난이도 : 실버 1
문제 접근
조건에 의해서 인접한 집은 양옆 집과 다른색으로 칠해야 함을 알 수 있다.
서로 겹치지 않게 색칠하려면, 현재 위치(i)에서 초록색을 선택했을 경우 이전 위치(i-1)에는 빨간색이나 파란색을 선택해야 한다.
i번째 집을 초록색으로 칠한다면 i까지의 최소 비용은 i-1번째 집이 빨간색과 파란색일 경우 중 더 작은 비용을 가진 색의 비용과 i번째 집의 초록색 비용을 더한 값이 된다.
모든 위치에서 앞집과 다른 색으로 최소비용을 계산해줌으로써 색이 겹치지 않게 집을 칠하는 비용의 최솟값을 도출할 수 있다.
이를 점화식으로 표현하면 다음과 같다.
dp[i]는 i번째까지의 색칠 비용이다.
dp[i]["빨강"] = min(dp[i-1]["초록"], dp[i-1]["파랑"]) + costs[i]["빨강"]
dp[i]["초록"] = min(dp[i-1]["빨강"], dp[i-1]["파랑"]) + costs[i]["초록"]
dp[i]["파랑"] = min(dp[i-1]["빨강"], dp[i-1]["초록"]) + costs[i]["파랑"]
costs 테이블과 dp 테이블을 선언해주고 점화식을 돌려 dp 테이블을 채워준다.
해답 및 풀이
import sys
input = sys.stdin.readline
N = int(input())
costs = []
for i in range(N):
r,g,b = list(map(int,input().split()))
costs.append([r,g,b])
dp = []
for _ in range(N):
row = [0, 0, 0]
dp.append(row)
dp[0][0] = costs[0][0]
dp[0][1] = costs[0][1]
dp[0][2] = costs[0][2]
for i in range(1,N):
dp[i][0] = min(dp[i-1][1],dp[i-1][2]) + costs[i][0]
dp[i][1] = min(dp[i-1][0],dp[i-1][2]) + costs[i][1]
dp[i][2] = min(dp[i-1][0],dp[i-1][1]) + costs[i][2]
print(min(dp[N-1])) # 인덱스 0번이 1번 집이므로 N은 N-1 인덱스이다.여기부터 다소 어렵게 느껴진다,,!
난이도 : 실버 1
문제 접근
정수로 이루어진 삼각형이 주어짐.
위에서부터 아래로 내려오며, 인접한 수만 선택 가능.
최대 합을 구하는 문제
DP[i][j]: i행 j열까지 내려왔을 때의 최대 합으로 설정하고
위에서 아래로 누적합을 계산하며 내려감.
각 위치에서 좌측 위 / 우측 위 중 큰 값을 선택해서 더함.
DP[i][j] = DP[i-1][j-1] 과 DP[i-1][j] 둘 중 더 큰 값에 DP[i][j] 값을 더한 값이다.
삼각형의 맨. 왼쪽, 오른쪽 부분은 길이 한곳이기 때문에 따로 처리해준다.
해답 및 풀이
import sys
input = sys.stdin.readline
n = int(input())
# 삼각형 입력 받고 만들기
triangle = []
for _ in range(n):
row = list(map(int,input().split()))
triangle.append(row)
dp = []
for i in range(n):
row = [0] * (i+1)
dp.append(row)
dp[0][0] = triangle[0][0] # 꼭대기는 그대로
for i in range(1,n):
for j in range(i + 1):
if j == 0:
dp[i][j] = dp[i-1][j] + triangle[i][j] # 왼쪽 끝은 왼쪽 위에서만 올 수 있음
elif j == i:
dp[i][j] = dp[i-1][j-1] + triangle[i][j] # 오른쪽 끝은 오른쪽 끝에서만 올 수 있음.
else:
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]
print(max(dp[n-1]))