접근 방법
1. 문제의 재귀적인 구조 파악
어떤 자연수 i를 1,3,4의 합을 통해 만들어야하는 상황
1,3,4의 합을 통해 i가 만들어지기 직전의 상황을 생각해보면
1을 더해서 i가 되는 숫자 (i-1)
3을 더해서 i가 되는 숫자 (i-3)
4를 더해서 i가 되는 숫자 (i-4) 등의 후보가 존재한다.
i를 만들 때 i-1, i-3, i-4의 경우에 대해서만 살펴보면 된다.
2. 수식으로 표현
f(i)를 다음과 같이 정의한다.
f(i): 1,3,4의 합으로 i를 만들 때 드는 동전의 최소 개수
위 과정에서 얻은 재귀적인 구조를 수식으로 나타내면
f(i) = min(f(i-1), f(i-3), f(i-4)) + 1
3. 초기값 처리
f(i) = min(f(i-1), f(i-3), f(i-4)) + 1
위 식에서 i-1, i-3, i-4가 음수가 될 수 있으니
1 <= i <= 4인 경우를 예외처리를 해줘야 한다.
- 실제 문제에서 DP 알고리즘은 문제를 보고 DP 알고리즘을 쓸 수 있는지 판단하는 게 관건이다.
- DP 알고리즘을 쓸 수 있는지 판단할 때 중요한 것은
문제의 재귀적인 구조(관계식)을 파악하는 것이다. 문제의 재귀적인 구조를 파악하지 못하면 DP 알고리즘을 사용할 수 없다.
-> 재귀적인 구조를 파악했으면 수식으로 표현, 초기값 처리를 진행하면 된다.
초기값 처리 안하면 값이 아예 달라지므로 주의하자
DP 알고리즘의 시간 복잡도 계산
-> DP 테이블의 크기 * 한 번 갱신하는 데 걸리는 시간
DP 알고리즘 구현 방법
1) Bottom-Up 방식
: 작은 부분부터 완성하는 방식으로, 보통 반복문을 활용한다.
-> DP 테이블 전체를 완성해야 하는 경우에는 바텀-업 풀이가 효율적이다.
-> DP 테이블의 값을 갱신하는 과정에서 접근하는 순서에 유의할 필요가 있다.
-> 즉, 아직 갱신되지 않은 부분의 값을 사용하면 안된다.
2) Top-Down 방식
: 큰 부분(구하고자 하는 값)을 기준으로 DP 테이블의 필요한 부분만 구하는 방식으로 일반적으로 재귀함수를 사용한다.
-> DP 테이블의 일부만 완성해도 되는 경우에는 탑-다운 방식의 풀이가 효율적이다.
-> DP는 최적해를 구하는 알고맂ㅁ이르모
~한 경우의 수를 구하시오
~의 최소값을 구하시오
~의 최대값을 구하시오 같은 문제 많음
문제풀이
BOJ 11048
1. 브루트포스 방식으로 풀이할 수 있는가?
-> 갈 수 있는 방식은 3가지, N,M <= 1000 3**1000은 1억번의 연산을 뛰어넘는다.
2. 그리디 방식으로 풀이할 수 있는가?
-> 그냥 그 때마다 가장 많은 사탕이 있는 곳으로 가는 것 = 최적해?인가 아님.
3. DP
-> 재귀적인 구조를 파악할 수 있는가.
1) 바텀-업 방식
import sys
input = sys.stdin.readline
# 3, 4
N,M = map(int,input().split())
dp = []
for _ in range(N):
dp.append(list(map(int,input().split())))
# 초기값 세팅
for i in range(1, N):
dp[i][0] = dp[i-1][0] + dp[i][0]
for j in range(1, M):
dp[0][j] = dp[0][j-1] + dp[0][j]
for i in range(1, N):
for j in range(1, M):
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + dp[i][j]
print(dp[N-1][M-1])2) 탑-다운 방식
import sys
sys.setrecursionlimit(1000000)
def func(i, j):
global arr, dp
# base case
if dp[i][j] != -1:
return dp[i][j]
# recursive case
dp[i][j] = max(func(i - 1, j), func(i, j - 1), func(i - 1, j - 1)) + arr[i][j]
return dp[i][j]
N, M = map(int, input().split())
arr = [[0] + list(map(int, input().split())) for _ in range(N)]
arr = [[0] * (M + 1)] + arr
dp = [[-1 for _ in range(M + 1)] for _ in range(N + 1)]
for j in range(0, M + 1):
dp[0][j] = 0
for i in range(0, N + 1):
dp[i][0] = 0
print(func(N,M))