동적 계획법(1)

August 16, 2024 6 분 소요

종만북, kks227님의 블로그와 바킹독님 유튜브를 공부하며 정리해보았다.

#1 도입

알고리즘 디자인 패러다임

문제를 해결하기 위해 알고리즘이 채택한 전략이나 관점을 말한다. 많은 알고리즘들은 문제를 해결하는
과정에서 문제를 해결하는데 가장 중요한 깨달음 을 공유하는데, 여기서 일정한 패턴을 확인할 수 있다.

즉 어떤 알고리즘이 문제를 해결하는데 사용한 전략이 알고리즘 설계 패러다임이다.
다이나믹 프로그래밍(Dynamic Programming : 앞으로는 DP라고 적겠다.)
1. 동적 계획법 또한 주어진 문제를 작은 문제로 만든 뒤 답을 구하고, 작은 답을 이용해 원래 답을 구한다.
2. 어떤 부분 문제가 두 개 이상의 서브 문제를 푸는데 사용된다면 이 문제의 답을 여러 번 다시 계산하는 대신 계산 결과를 메모해놓음으로써(Memoization) 속도향상을 꾀할 수 있다.
3. 메모이제이션은 함수의 리턴값이 입력 값만으로 결정될 때, 참조적 투명성이 성립할 때에만 사용가능
4. 캐시를 채울 때, 가장 큰 문제를 호출하고 나머지를 재귀적으로 호출하는 탑다운(Top-down) 방식이 있고, 반복문을 사용해 아래부터 채워가는 바텀업(bottom-up) 방식이 존재한다.
동적 계획법 레시피
1. 주어진 문제를 완전 탐색으로 해결하는 방법을 떠올려 본다.
2. 중복된 부분 문제를 한 번만 계산하도록 메모이제이션을 적용한다.

[백준1562 계단수]https://www.acmicpc.net/problem/1562

이전 자리에 오는 숫자가 다음 숫자를 결정한다.
i번째숫자가 5이면 i+1을 채울때는 0~i-1에 무슨 숫자가 존재하든 상관없이 4or 6이다.
12345…. 34545… 54345… 등에서 “i가 5일때 그 뒤는 어떻게 채워?” 라는 질문을 계속 하므로
이 값을 한번만 구해서 적어놓아야 겠다고(Memoization) 생각 할 수 있다.

[백준1509 팰린드롬 분할]https://www.acmicpc.net/problem/1509

어떤 문자열을 가장 작은 수의 팰린드롬으로 분할하는 문제이다.
k번째 칸을 채울 때, k와 팰린드롬을 이루는 i를 찾고 [i+1~n]을 재귀적으로 호출하는데 이때 부분 문제를 중복해서 호출하게 되므로 dp[st] : st부터 구한 팰린드롬 분할 개수 를 메모해 둘 수 있다.
(부분 문자열 팰린드롬을 O(n) 에 판단하는 알고리즘은 24년8월 리뷰노트에 적어두었다.)

int func(int k) {
    if(k==s.size()) return 0;
    int& ret = dp[k];
    if(ret != -1) return ret;

    ret = 1e8;
    for(int i=k;i<s.size();i++) {
        if(pal[k][i]) ret=min(ret,1+func(i+1));
    }
    return ret;
}

[백준14517 팰린드롬 개수 구하기(Large)]https://www.acmicpc.net/problem/14517

문자열에 부분수열 중 팰린드롬 개수를 구하는 것, 여기서 부분수열은 연속하지 않아도 된다.
i~j 에 존재하는 팰린드롬 개수를 dp[i][j] 라고 하면
$s[i] \neq s[j]$ 일 때 $dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]$

$s[i] == s[j]$ 일 때 $dp[i][j] = dp[i+1][j] + dp[i][j-1] + 1$

[백준1006 습격자 초라기]https://www.acmicpc.net/problem/1006

완전 탐색을 할때 반복되는 부분 문제를 생각해보면,
“주어진 칸 중 몇개의 칸이 칠해졌을 때 나머지를 채울때 필요한 값”
을 dp 배열에 적어놓고 싶어진다.
DP 문제의 난이도를 높이는 방법 중 하나가 이 메모이제이션을 어렵게 하는 것이라고 생각한다. 이 문제에서는 1부터 채워야 될까? 1,9 까지 채우고 다음칸으로 가야되나? 원형인데 어떻게 펼치지? 등의 고민을 요구한다.
원형 처리는 1와 n-1에서 해결한다고 치면 ,
i번째 벽을 채울때 만나는 경우의 수는 xx ox xo 3가지이고 두문자는 안쪽바깥쪽의 처리여부이다. 따라서 $dp[10005][3]$ 배열을 선언하고, $dp[i][j]$ 는 i칸의 모양이 j일때 i~n을 채우는 최소값이다
원형 처리는 1과n-1 사이에서 [ 안쪽만 연결, 바깥쪽만 연결, 둘다연결 , 연결X ] 4가지 경우로 시작을 하면서 처리해 주었다.

두겹의 벽을 직접 처리하기 보다는 나타날 수 있는 케이스가
한정적이라는 사실을 이용하는 것이 가장 중요했다!!

[백준1028 다이아몬드 광산] https://www.acmicpc.net/problem/1028

다이아몬드는 네변의 길이가 같고, 각 변의 기울기는 2가지 이다.
맨 위점을 기준으로 생각해보면 $ld$ 와 $rd$ 의 길이가 같고 $ld$도착점에서의 $rd$ 와 $rd$도착점에서의 $ld$ 가 같다면
4변의 길이가 같으므로 다이아몬드에 해당한다.
$O(n^2)$ 에 $ld$ , $rd$ 테이블을 채울 수 있고, $O(n^2)$ 에 최대 다이아몬드를 구할 수 있다.

배운점

처음에는 다이아몬드의 중앙을 기준으로 각 방향의 대각선을 구해서 4방향의 대각선이 같으면 다이아몬드이다. 라는 아이디어로 접근했는데, 문제점을 생각해보면 일단 직관적이지가 않았다. 대각선의 길이에 따라 중앙에서 떨어진 길이도 바뀔 뿐더러 4가지 방향을 고려해야 하는 등 문제가 많았다.
문제가 제시하는 상황의 특이점, 특수한 spot에 대해 빠르게 고민하자. 문제는 특수한 상황을 다루고, 그 상황을 이용해 문제가 제작되기에 당연히 특이점에 대해 먼저 살펴야 한다. 즉, 중앙에서 구한 대각선 이론이 실패했기에, 빠르게 마름모의 꼭짓점, 중점, 4변의 길이가 같음, $45^\circ$ 를 돌리면 정사각형 등의 성질로부터 관찰을 시작했어야 한다.

최적화 문제

동적 계획법의 일반적인 사용처는 최적화 문제, 가장 좋은 답을 선택하는 문제의 해결이다.

[알고스팟 TRIANGLEPATH]https://www.algospot.com/judge/problem/read/TRIANGLEPATH

맨위의 숫자에서 한칸씩 아래 or 오른쪽 아래로 내려갈때 경로의 최대 합을 찾는 문제이다.
잘못된 메모이제이션을 살펴보자

int n, triangle[100][100];
int dp[100][100][max_num*100+1];

int path1(int y,int x,int sum) {
    if(y==n-1) return sum+triangle[y][x];
    int& ret = dp[y][x][sum];
    if(ret!=-1) return ret;
    
    sum+= triangle[y][x];
    return ret=max(path1(y+1,x+1,sum),path1(y+1,x,sum));
}

여기서 $dp[y][x][sum]$은 y x 이전까지 sum일때, 맨 아래줄 까지 갈때 얻는 최대 값을 저장한다.

메모리 초과의 우려가 있고
특정 입력에 대해서는 완전 탐색과 같이 작동한다.

사실 (y,x) 에서 맨 아래로 가는 최대 값은 sum과 상관이 없다. 따라서 sum을 입력받지 않고
$dp[y][x]$를 $(y,x)$ 에서 시작해서 맨 아래줄까지 가는 경로의 최대 합 이라고 정의하면
메모리와 시간을 줄일 수 있다.

어떤 경로로 이 부분 문제에 도착했건 관계 없이 남은 부분 문제를 항상 최적으로 풀어도 상관없다 는 성질을 최적 부분 구조 라고 한다.

부분 문제의 최적해를 이용해 전체 문제의 최적해를 구할 수 있다면 최적 부분 구조가 성립한다.
→ 따라서 캐시 메모리에 부분 문제의 최적해를 담는 해결법을 생각해 볼 수 있다.

[백준11053 가장 긴 증가하는 부분수열]https://www.acmicpc.net/problem/11053

i번째가 첫번째인 LIS는 i이전에 어떤 값이 있든 상관이 없다. 따라서
$dp[i] : i부터 시작하는 lis$
라고 하면 i+1 부터 n까지 탐색해서 dp[i]를 구할 수 있다. $O(n^2)$

[백준12015 가장 긴 증가하는 부분수열2]https://www.acmicpc.net/problem/12015

사실 LIS는 그리디를 활용하면 $O(nlogn)$ 에 구할 수 있다.

i번째 값을 살펴볼 때, 이전에 만들어든 길이 n인 IS가 여러개 있다면,
마지막 값이 가장 작은 것만 봐도 된다는 것.

#2 실제 답 계산하기

최적화 문제를 풀 때 최적해의 값만을 계산하는 것이 아닌,
어떤 경로를 통해 최적해에 도착하는지 직접 계산해보자

[백준 2213 트리의 독립집합]https://www.acmicpc.net/problem/2213

1이 루트인 트리가 주어졌다고 하면, 그 아래의 어떤 노드를 루트로하는 서브트리의 최대 합은
위에서 어떤 노드들을 선택했는지 상관 없다는 것! → 최적부분구조

인접노드를 둘다 선택할 수 없다는 조건만 고려해주면
$dp[10001][2]$ : i가 루트인 서브트리의 최대값 j==0 이면 i번째 안칠함 , j==1 이면 칠함

어떤 노드를 사용했는지 구하는 tracking함수는 메모이제이션과 비슷한 구조로 정점을 탐색하며,
간단하게 루트를 사용한 경우에 노드를 배열에 추가해주는 식으로 구현했다.

[백준3687 성냥개비]https://www.acmicpc.net/problem/3687

가장 큰 수는 1과 7만을 이용해서 만들 수 있지만 작은 수는 DP를 사용해야 한다.

다행히 성냥이 100개이므로 재귀 함수에서 10개의 숫자를 전부 시도해보아도 O(10*n) 으로 충분히 가능하다. $dp[i] = min(dp[i],dp[i-j]) (0<=j<=9)$
성냥이 남는경우, 0이 맨앞에 오는 경우는 예외처리를 해야한다.

[백준2494 숫자 맞추기]https://www.acmicpc.net/problem/2494

최적화 문제를 해결 할 때, 이전에 선택한 것에대한 정보를 최소화 시켜서 메모이제이션을 효과적으로 했던 경험이 있을 것이다. 이 문제도 $i$번째 나사를 돌릴때 그 위에서 어떤 걸 몇개를 돌렸는지는 상관이 없고, 총 몇번 왼쪽으로 돌렸는지만 아래에 영향을 미친다.

따라서 $dp[i][k]$ : 지금까지 왼쪽으로 k번 돌렸을때, i번부터 아래 나사들을 채우는 최적 값
10번 돌리면 1바퀴니까 k<10 이다.

각 (i,k) 에서 최적값을 만드는 nxt position 값을 저장해놓고 tracking 함수로 추적하며 각각의 회전 값을 출력해 주었다.

[백준1023 괄호문자열]https://www.acmicpc.net/problem/1023

K가 상당히 크기때문에, 맨앞에 $($ 이 오는경우, $)$이 오는 경우 두가지로 나누고 $($뒤에 오는 경우의 수 만큼 건너뛰며, 구해야겠다고 생각했다. 그렇다면 필요한 질문

’(‘ 뒤에 올 수 있는 문자열은 어떤 것인가?
그것보다 이전에 선택한 괄호는 영향을 주는가?

괄호 문자열의 속성 : 여는 괄호가 전부 닫는 괄호에 대응이 된다. → 여는 괄호가 더 많다면 괄호ㄴㄴ문자열 → 여는 괄호 값이 음수, 닫는 괄호가 먼저나온경우 이후 문자열에 상관없이 괄호ㄴㄴ문자열

앞에 여는괄호 j개일 때, 괄호 문자열 만드는 길이i인 뒤쪽 문자열 경우의수 : $dp[i][j]$
’(‘ 뒤에 올 수 있는 문자열 개수는 $cnt = 2^{i-1} - dp[i-1][j+1]$
k<= cnt 이면 여는괄호, k>cnt 이면 k-=cnt, 닫는괄호
만약 여는괄호 개수가 음수가 된 적이 있다면(=닫는괄호가 여는괄호 없이 나온적 있다면)
모든 문자열 가능하므로 $cnt = 2^{i-1}$

사고 과정 정리

k번째를 찾는 과정에서 앞에서 부터 ( or ) 중 어느 것 차례인지 결정하면서 진행해야겠다.
괄호 ㄴㄴ 문자열은 여는 괄호가 남아있거나, )가 먼저나온 경우 2가지가 있구나
앞에 있는 ( 개수에 따라, 그리고 뒤에 남은 길이에 따라 cnt값이 달라지는 구나

#3 행렬 거듭제곱을 이용한 DP

행렬제곱 을 수행할 때, 지수가 큰 경우, 분할정복을 이용해 크기를 절반으로 줄이면서 $O(n^3logB)$ 에 해결할 수 있다.
피보나치수 를 dp table을 이용해 $O(n)$ 에 구할 수 있음을 우리는 알고있다.

그러나 피보나치 수의 점화식이이 바로 직전의 2개 피보나치 수만 알면 구할 수 있다는 사실 때문에,

$ \left[ \begin{matrix} F_n \ F_{n-1}\ \end{matrix} \right] = \left[ \begin{matrix} 1 & 1 \ 1 & 0 \ \end{matrix} \right]\left[ \begin{matrix} F_{n-1} \ F_{n-2}\ \end{matrix} \right] $ 라는 행렬식을 만들 수 있다. 0번째 1번째 피보나치 수를 알고 있기때문에, 행렬 제곱을 통해 $O(logN)$ 에 피보나치 수를 구할 수 있음을 알 수 있다.
1. 점화식이 이전의 몇개의 값을 이용해 표현할 수 있다면
2. 행렬로 점화식을 나타낼 수 있으므로
3. 행렬 거듭제곱을 이용해 정답을 구할 수 있다.

[백준2099 The game of death]https://www.acmicpc.net/problem/2099

a번 사람부터 시작 한다면, a가 가리키는 b와 c는 첫 번째로 불릴 수 있다. 를 모든 a에 관해 한번에 나타내야 한다는 점, n<=200 이라는 점 을 통해 인접행렬과 벡터의 곱으로 상태를 나타내야 겠다고 생각해야 한다.
행렬곱에 $O(n^3)$ 이므로 $k$번 전부 곱하지 않고, 분할정복을 활용한 행렬곱을 떠올린다.

Twitter Facebook LinkedIn

정승제

동적 계획법(1)

#1 도입

최적화 문제

#2 실제 답 계산하기

#3 행렬 거듭제곱을 이용한 DP

공유하기

댓글남기기

참고

동적 계획법(2)

여름방학동안 친 코드포스 개강하고 업솔빙하기

깊이 우선탐색

세그먼트 트리(1)