동적계획법

개요

모든 알고리즘 문제들은 완전탐색으로 해결할 수 있다.
그러나 비효율적인 연산과 시간을 줄이기 위해 여러 알고리즘이 있는데 동적 계획법이란 그 중 가장 많은 문제를 효율적으로 풀 수 있는 알고리즘이다.
동적 계획법이란 복잡한 문제를 여러개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법이다.

동적 계획법으로 풀 수 있는 문제 중 대표적인 것이 바로 피보나치 수열이다.
피보나치 수열은 이전의 두 항의 합을 현재의 항으로 설정하는 수열로 예를 들면
1, 1, 2, 3, 5, 8, 13, 21….와 같다.

이를 일반화 해보면 a(n+2) = a(n+1) + a(n)로 코드 상으로는 배열과 리스트를 이용해서 처리할 수 있다.

코드로 나타내보면…

def fibo(x):
  if x == 1 or x == 2:
    return 1
  return fibo(x - 1) + fibo(x - 2)

print(fibo(5))

그러나 x가 작다면 문제가 없겠지만 x가 커지면 연산횟수가 급격하게 늘어난다.
시간복잡도론 O(2^N)으로 나타낼 수 있다.

예를 들어 수가 구하려는 수가 10만 되더라도 약 1천 번의 연산을 수행해야한다.

여기서 좀 더 효율적으로 목표한 수를 구할 수 있을까?

가만히 보니 동일한 함수가 여러 번 호출되는 것이 보인다.
이 문제는 메모리 공간을 사용하는 것으로 해결할 수 있으며 이러한 접근의 문제 해결 방식을 동적 계획법, 다이내믹 프로그래밍이라고 부른다.

핵심 이론

동적 계획법의 원리와 구현 방식은 이러하다.

큰 문제를 작은 문제로 쪼갤 수 있어야한다.
작은 문제들이 반복되어 나타난다
이 작은 문제들의 결과값은 항상 같아야한다.
작은 문제들은 한 번만 계산해 DP테이블에 저장하며 추후 재사용할 때는 이 테이블의 값을 이용한다.
동적 계획법은 톱다운과 바텀업 방식으로 구현한다.

예시 문제

파보나치 수열

5번 째 피보나치 수열은 4번째 피보나치 수열과 3번째 피보나치 수열의 합이다. 즉 5번 째 피보나치 수열의 값은 4번째, 3번째 수열을 구하는 작은 문제로 쪼갤 수 있고 수열의 값은 항상 같기에 동적 계획법으로 풀 수 있다.

점화식을 세워보면 D[i] = D[i-1] + D[i-2]가 된다. 그 다음 이 값을 DP테이블에 저장해놓는다. 만약 해당 값이 필요하면 다시 연산하지 않고 저장되어있는 값을 사용한다.

d = [0] * 100

def fibo(x):
  if x== 1 or x == 2:
    return 1
  if d[x] != 0:
    return d[x]

  d[x] = fibo(x - 1) + fibo (x - 2)
  return d[x]

print(fibo(99))

이처럼 이미 수행된 적 있는 결과를 기록해서 재사용하는 방식을 캐싱이라고 부른다. 피보나치 수열에 동적계획법을 적용했을 때의 시간 복잡도는 O(n)이다.
기존 O(2^n)이던 것과 비교하면 정말 획기적으로 줄었다.

d = [0] * 100

def fibo(x):
  print('f(' + str(x) + ')', end=' ')
  if x== 1 or x == 2:
    return 1
  if d[x] != 0:
    return d[x]

  d[x] = fibo(x - 1) + fibo (x - 2)
  return d[x]

fibo(6)

현재 항을 구한 뒤 그 다음 항을 구하는데 사용되기 때문이다.
우리가 구하고자하는 6번째 항을 구하기 위해 작은 문제를 호출하는 방식으로 구했고 탑다운 방식에 해당한다.

바텀업 방식으로 코드를 작성해보면 다음과 같다.

d = [0] * 100

d[1] = 1
d[2] = 1
n = 99

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

print(d[n])

정수를 1로 만들기

1로 만들기는 대표적인 동적 계획법 문제로
정수 n개가 주어졌을 때 다음의 연산을 사용하여 주어진 숫자를 1로 만드는 최소 연산 횟수를 구하는 문제다.

3으로 나누어 떨어지면 3으로 나눈다.
2로 나누어 떨어지면 2로 나눈다.
1을 뺀다.

문제 플이 과정

D[i]는 i에서 1로 만드는데 걸리는 최소 연산 횟수
D[i] = D[i-1] + 1
if(i % 2 == 0) min(D[i], D[i]/2 + 1)
if(i % 3 == 0) min(D[i], D[i]/3 + 1)

의사코드

N은 구하고자 하는 수
for(i -> 2 ~ N) {
  D[i] = D[i-1] + 1
  if(i % 2 == 0) min(D[i], D[i]/2 + 1) // 결과가 D[i]보다 작으면 변경하기
  if(i % 3 == 0) min(D[i], D[i]/3 + 1) // 결과가 D[i]보다 작으면 변경하기 
}

가장 큰 정사각형 찾기

프로그래머스의 문제로 2차원 배열이 주어진다. 원소는 0또는 1이 담겨있으며 1이 적혀있는 칸은 1 * 1의 정사각형을 의미한다.
만약 1이 두 개 연이어서 있다면 직사각형으로 정사각형이 되려면 1개의 정사각형이 가로 2개 세로 2개 있어야한다.

예시를 보면 다음과 같다.

(0,1)부터 (3, 3)까지의 정사각형이 가장 크기 때문에 답은 9가 된다.
동적 계획법을 사용하여 작은 문제로 나누어보자.

우선 정사각형의 넓이는 가로 * 세로이고 실수할 가능성이 있으니 미리 리턴 값에 answer * 2와 같이 타이핑 해놓는 것이 좋다.

연속된 1이 있더라도 가로 세로를 더했을 때 정사각형이 나오지 않을 수 있다.

1111
1111

가로 길이 4, 세로 길이 2로 정사각형이 아니다. 생각해보면 최대 정사각형의 너비는 가로와 세로 길이중에 짧은 길이에 의해 결정된다. -> min 함수 위의 경우 2 * 2 = 4가 된다.
이미 구한 답을 다시 구하지 않도록 이전의 계산 결과를 원본 배열 board에 저장한다.

문제에서 주어진 board 배열을 순회하며 자신을 기준으로 왼쪽, 위, (정사각형이 되기 위한)대각선 위를 참고하여 자신을 정사각형의 오른쪽 아래 꼭짓점으로 잡았을 때 만들 수 있는 가장 큰 정사각형 값을 계산한다.

만약 왼쪽 대각선 위의 값이 0이라면 가로와 세로 값이 있다고 하더라도 정사각형을 만들 수 없게 된다.

인덱스 범위 초과 오류를 피하기 위해 (1,1) 지점부터 배열을 순회한다.

def solution(board):
    max_side = board[0][0]
    rows, cols = len(board), len(board[0])

    for i in range(1, rows):
        for j in range(1, cols):
            if board[i][j] == 1:
                board[i][j] = min(board[i-1][j], board[i][j-1], board[i-1][j-1]) + 1
                max_side = max(max_side, board[i][j])

    return max_side ** 2