[알고리즘] DP

용어는 Dynamic Program이지만 사실 핵심은 메모제이션에 있다.

DP관련 문제 풀이들은 이전에 계산한 내용을 '기억'해두고 다음 계산에 지속적으로 이용한다.

일반적으로 풀이방식에 따라 bottem-up, top-down을 구분하는데 큰 의미는 없다고 생각한다.

트리처럼 recursion을 이용한 풀이는 보통 top-down으로, 배열에 대해 index 0부터 차근차근 풀어나가는 방식을 bottom-up으로 생각하는 경우가 많다

 

무튼 dp의 가장 간단한 예시는 피보나치 수열이다

피보나치 수열의 경우 모든 항목을 일일이 계산하지 않는다.

f(1)을 한번 계산해두면, f(2)를 구할때 계산했던 f(1)을 메모제이션 했다가 사용한다.

결국은 일종의 점화식이다.

 

 

예시1- 416. Partition Equal Subset Sum

 

실제 문제를 풀며 이해해보겠다

위의 문제는 nums라는 배열에 대해 두개의 subset을 만들어 각 subset 원소의 합이 같은 subset을 만들 수 있는지 여부를 리턴하라는 문제다

 

DP는 dp배열을 만들어 문제를 구해낸다.

따라서 dp[ i ]에 대한 정의가 우선 뚜렷해야한다.

DP문제는 결국 조건에 맞는 dp[ i ] 를 리턴하는 것이고 dp [ i ]를 dp [ i-n]의 연산을 통해 연쇄적으로 구해가는것이 핵심이기 때문이다

 

위 문제를 이해해보면 subset은 항상 같은 값 두개로 나뉜다.

예를들어 위처럼 [1, 5, 11, 5] 라면, 각 배열 원소의 합이 22/2=11이 나와야 한다.

합이 11이되기 전까지의 과정에서는 합이 1~10이 되는 과정이 포함되어 있을 것이다.

그래서 우리가 구할 dp[ i ]는, 'i라는 합을 만드는게 가능한지 여부'가 되는 것이다

또한 dp배열의 길이는 11일 것이다

 

일단 경곗값을 제거해준다.

총합이 홀수거나 배열이 없는 경우는 당연히 false다.

토탈은 reduce를 이용해 구해봤다.

 

다음은 dp의 핵심인 배열생성과 초깃값이다

i=11까지 만들것이므로 해당하는 길이의 배열을 생성하고, 0일떄는 [ ] , [ ] 으로 나뉘어져 true이므로 초깃값을 준다

 

dp는 2중루프를 돌게 되는데, 일반적으로 input 배열의 각 원소에 대해 Loop를 돌게 된다.

 

dp 배열은 다음과 같은 형태로 구성하기 때문이다.

 

해당문제는 input nums의 각 원소에 대해 dp[target]을 구할 것이다.

그런데 생각해보면 특정 nums의 원소에 대해 dp[target-원소]가 true인지만 확인하면 된다.

num=1을 예시로 들어보자

num=1인 루프에서 dp[11]을 구하기 위해서는 dp[11-1]이 true인지만 보면 된다.

dp[1]은 이미 true이기 때문이다

 

 

문제의 핵심을 요약하자면 다음과 같다

 

1) dp의 정의를 제대로 내리고 초깃값을 잘 설정해주자

2) input 원소 하나당 Loop를 돌려주자

3) Loop 내부 조건은 문제마다 다르므로 잘 이해하자

 

 

 

예시2 - 198. House Robber

 

도둑이 집(배열의 각 인덱스)마다 돈(배열의 각 value)을 훔칠건데 연속으로 붙어있는 곳은 건들면 안된다고 한다

이 문제는 비교적 간단한 dp 형태로 풀어낼 수 있다.

dp[ i ]를 nums[ i ]까지의 배열에 대해 훔치기 가능한 최대 돈이라고 해보자

dp[ i ] 를 훔치게되면, dp[i-1]은 훔치지 못하고  dp[i -2]+ nums[ i ]가 최대가 된다.

그러나 dp [i -1]이 이보다 클 수도 있다.

 

따라서 각 nums별로 loop를 돌릴 필요 없이 직관대로 풀면 된다.

이렇게 간단한 문제는 dp설명에 부적합해 보인다.

 

 

예시3- 279. Perfect Squares

 

 

다음 문제를 보자

n이 주어졌을때 n을 최소한의 제곱수로 나눈다면 몇개로 나눠지냐는 문제이다

 

이 문제가 왜 DP문제인가?

dp[ i ]를 n이 i일때 최소 squres의 갯수라 해보자.

dp[ i ] 가 a^2+b^2로 나눠진다면, dp[ i ]는 dp[a] + dp[b]가 될 것이다

이것을 순서대로 각각 Loop로 구해본다고 했을때, a에 대해서만 생각해보면 1(a라는 제곱수인것이 확실하므로 1가지)+dp[i-a]가 될 것이다.

이렇게 일일이 구한 dp중 가장 작은 것이 답이 된다.

 

풀이는 그림과 같다.

각 n에 대해 Loop를 돌리면서 그것보다 작은 제곱수의 모든 경우에 대해 최솟값을 구해주는 것이다.

이때 최솟값을 구해야 하므로 Infinity를 기본 원소로 두었다.

 

 

예시4- 322. Coin Change

 

유사한 문제이다.

배열과 amount가 주어질 때, 배열의 원소를 사용하여 amount를 만드는 최소한의 가짓수를 구하는 것.

이번엔 전형적인 dp 풀이 방식에 맞추어 풀어보겠다.

 

1) dp[ i ] = amount가 i 일때 경우의 수

2) Loop의 조건: nums의 각 원소에 대해 반드시 각 원소가 쓰이는 경우대로 Loop

3) dp[ i ]의 결정: nums의 원소가 a라면, dp [ i ]는 dp[i -a]+1(a를 사용했으니 1회)과 dp[ i ] 중 더 작은 수

4) 초깃값의 결정: dp [ 0 ]은 0

 

위 조건대로 코드를 짜면 다음과 같다.

역시 dp의 정의가 중요함을 알 수 있다.

 

 

예시5- 494. Target Sum

마지막으로 한 문제만 더 풀어보고 포스팅을 마치겠다.

해당 문제는 양의 정수로 구성된 배열과 정수 S가 들어올 때, 배열의 원소중 일부를 마이너스로 바꾸어 합하여 정수 S를 만드는 방법의 가짓수를 구하는 문제이다

 

dp [ i ] 는 i를 만들기 위한 경우의 수 라고 해보자

하지만 이는 상당히 애매한 정의다

애초에 dp [ i ]를 dp[i- a] 로 어떻게 유추할 수 있을까?

합이 2가 되는 경우의수와 3이 되는 경우의 수의 관계가 뭘까?

잘 모르겠다

따라서 조금 더 직관적인 dp를 만들어보고자 한다.

 

특정 S를 만들기 위해서는 nums의 배열에서 양수로 유지할 집합(A)에서 음수가 될 집합(B)를 빼야 한다.

예컨데 nums가 [ 1, 1, 1, 1, 1]이고 s가 3이라면 A는 [ 1,1 ,1 1]되고 B는 [1]이 되어야 한다

합으로 생각해보면 A+B= 5, A-B=3이 되어야 한다는 뜻이다.

이를 일반화 시켜보면 A+B= total이라는 합으로, A-B=s로 나타낼 수 있다.

 

다시말해 이렇게 나타낼 수 있다는 뜻인데, 이는 직관적인 dp배열을 만들도록 해준다

왜냐하면 우리가 특정 s를 만족시킨다는 뜻은 결국 A라는 숫자를 만들 수 있는 경우가 된다.

그런데 nums의 한 원소를 a라 하면 , dp[A]는 dp[A-a]를 만드는 경우의 수와 같아진다. 

 

따라서 다음과 같이 작성해주면 된다.

상기에 나왔던 문제들과 원리는 모두 동일하다.