파이썬 - 다이나믹 프로그래밍(dynamic-programming) 문제 풀이 전략

목차

시작

쉽게 dp문제 알아보는 법

전략

문제

시작

이전 글에서는 피보나치를 통해 다이나믹 프로그래밍의 기본적인 아이디어를 살펴보았습니다.

이를 기반으로 이번 글에서는 다이나믹 프로그래밍 문제에 대한 일반화와 기본적인 문제 접근 방식에 대해 알아봅시다.

 

다이나믹 프로그래밍은 기본적으로 모든 경우를 탐색합니다.

하지만 완전탐색에 추가된 점이 있는데 이는 이전에 계산한 결과를 다시 사용한다는 점입니다.

이전에 본 피보나치의 경우에도 기본적으로는 완전 탐색을 진행하고 계산 결과를 memo에 기록해 두었다가.

다시 사용함으로써 다이나믹 프로그래밍을 구현했습니다.

 

다이나믹 프로그래밍은 완전탐색에 memo를 추가한 방법입니다.

그래서 완전탐색으로 해결 가능한 문제 중 일부가 다이나믹 프로그래밍으로 해결 가능합니다.

다이나믹 프로그래밍으로 해결가능한 문제는 2가지 특징이 있는데 아래와 같습니다.

• overlapping subproblems
• optimal substructure

이전에 학습한 피보나치를 통해 위의 두 전문용어에 대해 감을 익혀봅시다.

피보나치의 i번째 값인 fib(i)를 구하는데 fib(i-1)과 fib(i-2)를 사용했습니다.

이렇게 이전에 구한 값이 이후 계산에 사용되는 구조를 다이나믹 프로그래밍에서는 overlapping subproblems을 가진다고 말합니다.

정확한 i번째 피보나치 수를 구할 땐 점화식 fib(i) = fib(i-1) + fib(i-2)을 사용했습니다.

이렇게 명확한 점화식이 있으면 optimal substructure를 가진다고 말합니다.

쉽게 dp문제 알아보는 법

다이나믹 프로그래밍 문제는 기본적으로 완전탐색으로 해결 가능합니다.

그래서 완전탐색으로 구현했다가 낭패를 보는 경우가 있습니다.

위에서 학습한 다이나믹 프로그래밍 문제의 특징인 overlapping subproblems, optimal substructure를 발견하는 일은 초보자에게 여간 쉬운 일이 아닙니다.

 

하지만!

 

dp문제를 쉽게 알아볼 수 있는 두 가지 특징이 있습니다.

모든 문제에 적용되는 것은 아니지만 대부분의 문제에 적용 가능합니다.

• 문제에 최댓값 최솟값 혹은 모든 경우의 수를 원한다.
• 이전의 선택이 미래에 영향을 준다

대부분의 dp문제는 완전탐색 문제에 optimal substructure조건을 추가하기 위해서 최댓값, 최솟값, 혹은 모든 경우의 수를 찾으라고 요구합니다.

또한 문제에서 주어진 예제를 분석할 때 이전의 선택이 나중에 값에 영향을 주는 특징을 발견할 수 있습니다.

이는 예제에서 overlapping subproblems구조의 특징을 발견한 것입니다.

전략

일단 dp문제를 해결하기 위해서는 문제가 dp인 것을 알아야 합니다.

위에서 설명한 방법대로 문제 본문에서 최댓값, 최솟값, 경우의 수를 요구하는지,

문제에 주어진 예제에서 이전의 선택이 미래에 영향을 주고 있는지를 확인하고 dp인 것을 확인해야 합니다.

 

dp문제인 것을 확인하면 계산한 결과를 저장할 데이터 구조에 대해서 생각해 봐야 합니다.

데이터 구조는 통상적으로 리스트를 활용하며 dp [i][j][k] = value의 형식을 사용합니다.

이전 챕터에서 학습한 피보나치의 경우 dp[i] = value인 경우입니다.

 

dp[i][j][k] = value와 같은 데이터 구조를 정의하기 위해서는 변수에 대해 생각을 해야 합니다.

예제 분석 혹은 문제에서 얻은 정보를 바탕으로 몇 가지의 변수가 필요한지,

각 변수 마나 어떤 의미를 가지는지 정의해야 합니다.

피보나치의 경우 변수 1개만 필요하며 변수는 i번째를 의미합니다.

dp [i][j][k] = value에서 value는 부분 문제에 대한 최댓값, 최솟값, 경우의 수를 나타내야 합니다.

 

dp[i][j][k] = value를 명확하게 정의했다면 점화식을 찾아야 합니다.

점화식은 이전의 계산한 dp [n][m][l] = value들을 이용하여 dp [i][j][k]의 value를 찾을 수 있어야 합니다.

점화식의 형태는 일반적으로

dp [i][j][k] = function(dp [n][m][l])

where 0 <= n , m , l < i , j , k

의 형태입니다.

 

마지막으로 점화식을 찾았다면 base case를 dp [i][j][k]에 추가하고 가능한 모든 상황을 탐색하면 됩니다.

대부분 기초 dp문제 에서는 for loop로 탐색이 가능하고 재귀적인 용법도 유용합니다.

몇몇 응용 문제에서는 bfs를 이용해야 하는 경우도 있습니다.

문제

원형 도둑질

https://programmers.co.kr/learn/courses/30/lessons/42897

코딩테스트 연습 - 도둑질

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

문제는 대략 이렇습니다.

원형으로 집이 배열되어 있습니다.

이 집들을 도둑질하여 최대로 얻을수 있는 돈을 구하는 문제입니다.

하지만 문제의 조건으로 한 집을 털면 양쪽 집을 털수 없는 조건을 가지고 있습니다.

 

제한사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다

문제를 읽고 드는 생각.

일단 완전탐색으로 해결할 수 있다는 생각을 자동으로 들어야합니다.

또한 문제를 살펴보면 돈의 최댓값을 구해야합니다.

여기서 dp를 의심하기 시작해야 합니다.

그리고 제한사항을 보면 인풋에 대해서 for loop한번으로 처리를 해야합니다.

완전탐색으로 진행할 경우 for loop한번으로 처리할 수 없을 것 같습니다.

또한 문제를 보아하니 어디를 도둑질 하냐에 따라 미래에 선택할 수 있는 상황에 영향을 줍니다.

위의 상황을 종합해 볼떄 다이나믹 프로그래밍 문제라 확신할 수 있습니다.

 

다이나믹 프로그래밍 문제 유형이라 확신이 들었다면,

dp[i][j][k] = value와 같은 데이터 구조를 생각해야 합니다.

먼저 변수에 대해 정의해 봅시다.

우리가 원하는 결과는 i번째가 마지막 집이라고 가정했을 때 얻을수 있는 최댓값 입니다.

그래서 dp[i] = max_money로 생각할 수 있습니다.

 

데이터 구조 까지 정의했 다면,

점화식을 찾아봅시다.

dp[i]는 i번째 까지 탐색 했을때 얻을수 있는 최대 돈입니다.

dp[i]는 i번째 집을 터는 경우와 아닌 경우 두가지가 존재합니다.

i번째 집을 터는 경우는 dp[i] = dp[i-2] + money[i]이고,

털지 않는 경우를 포함하는 경우는 dp[i] = dp[i-1]입니다.

 

note dp[i+1] >= dp[i]입니다. 그래서 i번쨰 집을 털지 않는 경우 dp[i] = dp[i-1]로 생각할 수 있습니다.

 

결국 dp[i]는 i번째 까지 진행했을때 얻을수 있는 최대 돈이기에,

dp[i] = max( dp[i-2] + mpney[i], dp[i-1] )의 접화식을 얻을수 있습니다.

 

base case의 경우 첫번째 집을 턴 경우와 털지 않은 경우를 생각해야합니다.

첫번째 집을 턴 경우는 dp[0] = money[0], dp[1] = money[0]입니다.

털지 않은 경우는 dp[0] = 0, dp[1] = money[1]입니다.

위의 두가지 경우를 고려하여 최대로 벌수 있는 돈을 구하면 됩니다.

 

의사코드

1. dp1, dp2 테이블을 초기화 한다.
2. dp1은 0번째 집을 털지 않은 경우이고 dp2는 턴 경우이다.
3. dp1과 dp2에 base case를 넣는다.
4. for i in money
    5. dp1[i] = max(dp1[i-1], dp1[i-2] + money[i])
6. dp2에 대해서도 loop를 돈다.
7. dp1과, dp2를 고려한 최댓값을 리턴한다.

구현

def solution(money):
    dp1 = [0] * len(money)
    dp1[0] = money[0]
    dp1[1] = money[0]
    dp1[-1] = money[0]
    for i in range(2,len(money)-1):
        dp1[i] = max(dp1[i-1], dp1[i-2] + money[i])
        
    dp2 = [0] * len(money)
    dp2[0] = 0
    dp2[1] = money[1]   
    for i in range(2, len(money)):
        dp2[i] = max(dp2[i-1], dp2[i-2] + money[i])

    return max(dp1[-2], dp2[-1])

 

최소 스테미너로 이동하기

m*n의 크기를 가지는 지형이 있습니다.

각 칸마다 자연수가 존재합니다.

자연수는 칸에 도착했을 떄 소모되는 스테미너를 의미합니다.

이때 (0,0)에서 (m,n)으로 가는 최소 스테미너를 구하시오.

 

예제.

1	1	1
3	3	1
4	4	1

최소 스테미너는 5입니다.

 

문제를 읽고 드는 생각.

완전탐색으로 해결 가능한 문제입니다.

거기다 최솟값을 원하고 있습니다.

또한 예제의 (3,3)에 대해 생각을 해봅시다.

(3,3)으로 진입할 수 있는 방법은 (3,2) ,(2,3)에서 진입할 수 있습니다.

만약 (3,2) ,(2,3)까지의 최소 스테미너 비용을 안다면,

(3,3)의 최소 비용은 아래와 같이 구할 수 있습니다.

dp[3][3] +=  min ( dp[3][2] , dp[2][3] )

dp 문제이며 점화식도 쉽게 구할수 있는 문제입니다.

 

혹시 모르니 dp[2][2]에 대해서도 생각해 봅시다.

1	1	1
3	3	1
4	4	1

dp[2][2]는 위의 표에서 주황색으로 색칠된 부분 문제를 생각하고 (2,2)까지 가는 최소 스테미터를 계산하면 됩니다.

(2,2)로 진입하는 방법은 (1, 2), (2, 1)이 있습니다. 

결국  dp[2][2] +=  min ( dp[1][2] , dp[2][1] )로 계산하면 됩니다.

 

의사코드

1. 그리드의 모든 성분을 순차적으로 순회하며
   dp[x][y] += min( dp[x-1][y], dp[x][y-1])
   점화식을 적용한다.
2. dp[-1][-1]을 리턴한다.

구현

def Solution(grid: List[List[int]]) -> int:
    for x in range(1,len(grid)):
        grid[x][0] += grid[x-1][0]
    for y in range(1,len(grid[0])):
        grid[0][y] += grid[0][y-1]
        
    for x in range(1,len(grid)):
        for y in range(1,len(grid[0])):
            grid[x][y] += min(grid[x-1][y], grid[x][y-1]) 
        
    return grid[-1][-1]