코테 알고리즘 다이나믹 프로그래밍 간단 이해

다이나믹 프로그래밍(dp)는 뭘까?

다이나믹 프로그래밍은 이름은 뭔가 거창하지만 개념은 간단한데

바로 최종 결과를 얻기 위해 필요한 하위 데이터를 계속 저장해서 상위 문제를 해결하는 방법이다

핵심은 하위 데이터를 계속 저장한다는 점이다

 

물론 이 말만 듣는다고 바로 이해하기는 어렵다

이해를 위해 예를 하나 들어보겠다

다이나믹 프로그래밍하면 무조건 따라오는 문제인 피보나치 수열을 보자

피보나치 수열은 n번째 수가 n-1과 n-2의 합인 수열이다

즉 n번째 수를 구하기 위해서는 n-1과 n-2의 정보가 필요하다

 

피보나치 수열을 다이나믹 프로그래밍으로 구하는 방법은 몹시 간단한데

코드는 다음과 같다

dp = [0]*n
dp[0] = 1
dp[1] = 1

for i in range(2,n) :
	dp[i] = dp[i-1] + dp[i-2]

 

n번째 수를 구하기 위해서는 n-1과 n-2의 값이 필요하다

즉 dp[0]과 dp[1]의 값은 직접 대입해줘야 한다는 말이다

이후 값은 반복문을 통해 순서대로 값을 dp에 저장하고 dp[n-1]에는 n 번째 수의 값이 들어가게 된다

 

다이나믹 프로그래밍을 왜 쓸까?

 

코테 문제를 풀기 위해 알고리즘을 적용하기 위해 꼭 생각해 봐야하는 점은

이 알고리즘을 왜 사용하는지에 대한 점이다

그렇다면 다이나믹 프로그래밍을 쓰는 이유는 뭘까?

이유는 간단하다

상위 값을 구할 때 하위 값의 결과가 필요하기 때문이다

다르게 말하면 하위 값을 모르면 최종 결과를 구할 수 없기 때문에 하위 값을 하나씩 구한다는 말이다

 

다이나믹 프로그래밍을 적용하는 문제

다이나믹 프로그래밍을 적용하는 문제들에 대해서 설명을 해보겠다

먼저 특정 규칙대로 결과를 구할 때 n번째에 위치하는 값을 구하는 문제다

 

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

다음과 같은 문제를 예로 들 수 있겠다

사실 이런 문제에서 중요한건 dp 개념을 이해하는 것이 아니라

규칙을 찾는게 가장 중요하다  규칙을 찾는 방법은 숫자 범위를 정해서 직접 하나씩 계산을 해보고

해당 범위 내의 값에서 규칙성을 찾으면 된다

 

 

다른 문제는 n번째 선택을 할 때 나올 수 있는 최선의 값을 구하는 문제다

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

이런 문제를 예로 들 수 있겠다

이러한 문제를 풀 때는 보통 n 번째 위치의 최선의 값을 구하기 위해 max() 혹은 min()을 사용하여 최선의 값을 구한다

문제 풀이 접근 방법은 간단한데 해당 위치에서의 최선의 선택을 하기 위해 어떤 선택지를 고려해야 하는지 고민하면 된다

그리고 dp[n] = max(선택지1, 선택지2) 와 같은 형태로 선택지 중에 최선을 저장하게 하면 문제가 해결 된다

가끔씩 n 번째 위치의 최선이 아니라, 전체 계산중에서 최선의 숫자를 구하는 문제가 있는데

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

이러한 문제는 dp로 n번째 위치의 최선의 수를 다 구하고 마지막에

print(max(dp)) 같은 형태로

전체 dp중의 최선의 값을 출력해주면 된다