[알고리즘] 동적 프로그래밍

동적 프로그래밍이란?

하나의 문제는 한번만 풀도록 만들어진 알고리즘이다.

• 풀이 방법:
  작은 문제는 한번만 풀어야하므로 정답을 구한 작은 문제를 메모하여 (메모제이션으로 구현도 가능)
  큰문제를 풀 때 똑같은 작은 문제가 나타나면 작은 문제의 결과값을 이용한다.

• 조건 :
  작은 문제가 반복적으로 일어나는 경우나
  같은 문제는 구할 때 마다 결과값이 같은 경우

예로 백준 설탕배달 문제를 이용하여 DP를 분석해보자

문제 설명

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

초기 구현한 코드 (그리디)

n = int(input())

result = []

d = n // 5
y = 0

// 5키로짜리 봉지를 사용가능한 갯수를 0까지 반복
for i in range(d,-1,-1):
  res = n - (i * 5)
  if res % 3 == 0:
    print(i+(res//3))
    y = 1
    break

if y == 0:
  print(-1)

그리디로도 구현 가능하지만 dp를 이용해 풀어보자

구현 코드 (동적 프로그래밍)

3 -> 1
4는 -1로 X
5 -> 1

이 3과 5숫자에 3,5만큼 차이나는 숫자들은 이전 값들에서 +1만 해주면 된다.
다시 말하자면, dictionary를 이용해서 표를 만들어 나가 해당 숫자까지 채워져 값을 도출해내는 방식이다.

n = int(input())

result = []

res = {3:1,5:1}

for i in range(6,n+1,1):
  tmp = 0
  if i-3 in res.keys() and i % 5 != 0:
    tmp = res[i-3]+1
  elif i-5 in res.keys():
    tmp = res[i-5]+1

  if tmp != 0:
    res[i] = tmp

if n in res.keys():
  print(res[n])
else:
  print(-1)

해당 풀이 방식은 이미 계산된 문제는 해결되었으니 추가로 더해주기만 하면 되어 계산을 여러번 반복하지 않아도 된다.

동적 프로그래밍 문제 유형들

프로그래머스 level3. 정수 삼각형

문제 설명
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

동적 프로그래밍 접근방법
거쳐간 숫자의 합이 가장 큰 경우를 찾는 문제이다.
이 문제는 2단 삼각형이거나 8단 삼각형이어도 푸는 방식은 똑같다 상위 숫자가 하나인 경우는 그 숫자를 가져오고 두개인경우는 비교해서 더 큰 숫자를 가져오는 방식이다.

따라서 상위단 숫자를 자신의 숫자를 더하는 방식으로 같은 문제를 반복하지 않는 동적 프로그래밍을 사용 할 수 있다.

def solution(triangle):
    answer = 0
    
    for i in range(1,len(triangle)):
        for index,data in enumerate(triangle[i]):
            // 인덱스가 0인 경우
            if index == 0:
                triangle[i][index] = data + triangle[i-1][index] 
            // 인덱스가 마지막 번호인 경우
            elif index == i:
                triangle[i][index] = data + triangle[i-1][index-1]
            //중간 인덱스인 경우 둘 중 큰수를 자신에게 대입한다.
            else:
                triangle[i][index] = data + max([triangle[i-1][index-1],triangle[i-1][index]]) 
        
    return max(triangle[len(triangle)-1])

프로그래머스 level3.등굣길

문제설명
계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

동적 프로그래밍 접근방법
4*3 좌표의 각각 좌표의 최단 경로를 계산하여 계산된 최단경로를 가지고 최종 목적지의 최단 경로를 구하는 방식

좌표크기와 같은 배열을 하나 생성하고 장애물좌표는 -1로 지정한다.
오른쪽과 아래로만 이동가능하므로 위와 왼쪽의 좌표의 최단경로를 가지고 계산한다.

def solution(m, n, puddles):
    answer = 0
    
    arr = list(list(0 for i in range(m)) for i in range(n))
    
    for i in puddles:
        arr[i[1]-1][i[0]-1] = -1
    
    arr[0][0] = 1
    
    for i in range(n):
        for j in range(m):
            
            if arr[i][j] != -1:
            	// 왼쪽 좌표
                if j >= 1 and arr[i][j-1] != -1:
                    arr[i][j] += arr[i][j-1]
                // 위쪽 좌표
                if i >= 1 and arr[i-1][j] != -1:
                    arr[i][j] += arr[i-1][j]
                    
    return arr[n-1][m-1] % 1000000007

동적 프로그래밍을 공부한 후 느낀 점

• 작은 문제를 여러번 반복하는 것을 잘 잡아내야 한다.

• 도형을 가지고 해결하는 문제는 DP방식을 고민해볼 필요가 있다.
  도형문제는 작은 도형과 큰 도형과 풀이 방식이 거의 동일하기 때문에
  dp 를 이용하여 접근을 해야할 것 같다.

• 그리디방식으로 해결이 안되면 작은 범위에서 도출되는 결과를 나열하여 앞선 해결방식을 이용할 수 있는지, 반복적인 공식이 있는지 분석해볼 것이다.

• 생각보다 쉬운 문제도 동적 프로그래밍 방식으로 해결될것 같은 문제가 여럿 떠올랐다. 여러 방식의 알고리즘으로 접근하는 연습을 하자