[알고리즘] DP(다이나믹프로그래밍)

date

Jul 24, 2023

slug

algorithm-dp

author

status

Public

DP 다이나믹 프로그래밍

: 하나의 문제를 단 한번만 풀게 한다.

큰문제→작은 문제로 나눔.(분할정복)

구한 값을 잠시 저장해둔거 → Memo(memoization)

재귀와 비슷하지만, 일반적인 재귀를 단순히 사용시 비효율적인 계산이 될 수 있다.

but 한번 구한 작은 문제의 결과를 저장해두고 재사용한다면? 효율적인 계산이 가능해진다.

DP가 적용되기 위해서는 2가지의 조건을 만족해야 한다.

1.겹치는 부분 문제

2.최적 부분 구조

1.겹치는 부분 문제

DP는 기본적으로 큰 한 문제를 나누고, 그 문제의 결과값을 재활용해서 전체 답을 구한다.

그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용 가능하다.

ex) 피보나치 수열의 같은 문제가 반복해서 나타나는 경우

2.최적 부분 구조

부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우이다.

A-X/ X-B가 많은 경로 중 가장 짧은 경로라면, A - X - B도 가장 짧은 경로가 된다.

작은문제에서 구한 정답이 큰문제에서 동일하다.

DP사용법

DP는 특정한 경우에 사용되는 알고리즘이 아니라, 방법론이다.

1.DP로 풀 수 있는 문제인지 확인한다.

2.문제의 변수 파악

3.변수 간 관계식 만들기(점화식)

4.메모하기(memoization or tabultaion)

5.기저 상태 확인하기

6.구현하기

보통 특정 데이터 내 최대화 / 최소화 계산을 하거나 특정 조건 내 데이터를 세야 한다거나 확률 등의 계산의 경우 DP로 풀 수 있는 경우가 많다.

DP는 2가지 방식으로 구현할 수 있다.

1.BOTTOM-UP(Tabulation 방식) - 반복문 사용

2.TOP-DOWN(Memoization 방식) - 재귀 사용

BOTTOM-UP 방식 (상향식)

: 아래서부터 계산을 수행하고, 전체 큰 문제를 해결하는 방식이다.

제일 작은 인덱스의 수 부터 목표하는 값으로 향하는 것

TOP-DOWN 방식 (하향식)

: 위에서부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식이다.

맨 위의 값에서 재귀로 제일 작은 인덱스를 향하는 것

🤩

그리디 알고리즘은 내가 생각한 처음 최적의 방법이 끝까지 반례 없이 적용이 되는 경우에 이용하고,

동적 계획법은 가능성을 모두 두고 그 안에 최솟값을 찾을 수 있음

→ 구현 방법 암기해놓기


n = int(input())

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

if n <= 3 : print(n)
else : 
	dp[1] = 1
	dp[2] = 2
	for i in range(3, n+1):
		dp[i] = dp[i-1] + dp[i-2]

	print(dp[i]%10007)

문제 푸는 법

• 따라서 첫 번째 단계는 문제가 DP 문제임을 확인한 후 문제의 상태를 결정하는 것이다. 알고 있듯이 DP는 계산된 결과를 사용하여 최종 결과를 공식화하는 문제다. 따라서 다음 단계에서 현재 상태와 이전 상태 간의 관계를 찾아야 한다.

점화식 세우는게 어렵지만 중요

유동적으로 변하는 부분을 생각

많이 풀어보고 감을 잡아야 함.

무조건 방법을 찾아낸다는 생각으로 접근하기