[Algorithm] Dynamic Programming - 동적 계획법

Dynamic Programming - 동적 계획법

---

DP, 동적계획법이란?

---

큰 문제를 작은 문제로 나누어 접근하는 방식의 문제를 일컫는 용어입니다.

 

어떠한 문제를 나누어 접근한다는 시각에서는 분할정복(Divide and Conquer) 와 컨셉이 비슷합니다.

 

하지만 나누어 접근하는 작은 문제가 중복해서 일어나는가에 대한 여부에 차이가 존재합니다.

 

분할정복은 작은 문제에서 반복이 일어나지 않습니다. 반면 DP는 작은 부분의 문제들이 반복되는 컨셉을 이용해 문제를 풀어나가는 방법입니다.

 

Memoization

---

• 반복적으로 계산되는 것들의 계산 횟수를 줄이기 위해 이전에 계산했던 값을 저장해두었다가 다시 사용하는 방법으로 동적계획법에 핵심이 되는 기술입니다.

Memoization은 동적 프로그래밍 방식이 작은 문제들이 반복되고 이 작은 문제들의 결과값은 항상 같다 라는 컨셉을 이용하여 한번 계산한 작은 문제의 결과를 저장해놓고 이를 다시 사용하는것을 의미합니다.

 

간단한 예시로는 피보나치 수열이 있습니다.

 

피보나치 수열은 1, 1, 2, 3, 5, 8, 13 ... 의 수열을 이룹니다.

 

다음 수열 = 이전 수열 + 이전의 이전 수열 이라는 점화식으로 이루어진 수열을 의미합니다.

 

이를 recursion 방식으로 풀게되면 훨씬 간단히 풀 수 있으나 fibo(n) 함수에서 전달된 n의 값이 증가함에 따라 호출되는 함수의 수가 기하급수적으로 증가하기 때문에 일정 수 이상의 순열을 구하기 힘듭니다.

 

이러한 경우, 동적계획법의 두 가지 조건을 상기해보면 이를 쉽게 풀어낼 수 있습니다.

 

1. 작은 문제들이 반복된다.

• fibo(5)를 구하기 위해서는 fibo(4)와 fibo(3)이 필요하며, 다시 fibo(4)를 구하기 위해서는 fibo(3)과 fibo(2)가 필요합니다.

위 예시만 살펴봐도 fibo(3) 작업이 중복되는 것을 알 수 있습니다. 즉, 작은 문제들이 반복되는 구조입니다.

 

2. 동일한 작은 문제들의 결과값은 같다.

• 피보나치 수열의 경우, 첫번째 수열값과 두번째 수열값은 1로 고정되어 있습니다. 이 말은 즉 3번째 수열 또한 항상 결과값이 2로 고정된다는 의미입니다.

따라서, 모든 수열의 결과값은 항상 정답이 동일하다는 사실을 알 수 있습니다.

재귀를 이용한 피보나치 코드를 살펴봅니다.

def fibo(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)

 

DP 문제들은 재귀를 이용해서도 풀어낼 수 있으나, 대부분의 문제들을 시간초과 에러가 뜹니다.

 

이러한 경우, 메모이제이션을 이용하여 DP방법으로 풀어내야 합니다.

 

요약

---

1. 동적계획법이란, 큰 문제를 작은 문제들로 분할하여 해결해 나아가는 방식을 의미하며 작은 문제들의 답은 항상 동일합니다.

2. 메모이제이션 개념을 이용하여 이미 계산한 결과값을 저장하여 나중에 필요할 경우 저장된 값을 단순히 가져오기만 하면 된다는 부분에서 분할 정복과 차이가 존재합니다.

3. DP = recursion + Memoization

내용 추가

---

다이나믹 프로그래밍

• 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간을 비약적으로 증가시키는 방법
• 이미 게산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 게산하지 않도록 합니다. -> 이게 핵심!
• 다이나믹 프로그래밍 구현은 일반적으로 탑다운 & 바텀업 방식으로 구성됩니다.

다이나믹 프로그래밍의 조건

• 최적 부분 구조

  • 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있습니다.

• 중복되는 부분 문제

  • 동일한 작은 문제를 반복적으로 해결해야 합니다.

메모이제이션

• 메모이제이션은 DP를 구현하는 방법 중 하나입니다.
• 한 번 게산한 결과를 메모리 공간에 메모해놓는 기법.
  • 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옵니다.
  • 값을 기록해 놓고 필요할 때 가져다 쓴다는 점에서 캐싱 이라고도 합니다.
  • 이를 통해 한 번 계산한걸 다시 계산해야 할 때는 계산없이 해당 결과값만 바로 가져와서 사용하여 빠른 속도로 문제를 풀어낼 수 있음.
  • 즉, 연산을 위해 소비되는 시간 비용을 메모리 비용으로 충당하는 것입니다.

탑다운 vs 바텀업

• 탑다운(메모이제이션) 방식은 하향식이라고도 하며, 바텀업 방식은 상향식이라고도 합니다.
• DP의 전형적인 형태는 바텀업 방식입니다.
  • 결과 저장용 리스트를 DP 테이블이라고 부릅니다.
• 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미합니다.

재귀를 이용한 피보나치 수열 방식

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

탑다운 방식(메모이제이션)

# 한 번 계산한 결과를 기록, 메모이제이션 DP 테이블 초기화
dp = [0] * 100

# 피보나치를 재귀함수로 구현 (탑다운 DP)
def fibo(x):
    if x == 1 or x == 2:
        return 1
    # 이미 계산한 적 있는 작은 문제라면 그대로 반환
    if dp[x] != 0:
        return d[x]
    # 아직 계산하지 않은 작은 문제라면 계산 후 값을 메모이제이션 한 이후 반환
    dp[x] = fibo(x-1) + fibo(x-2)
    return dp[x]

바텀업 방식

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
dp = [0] * 100

# 1,2 번째 피보나치 수 초기화
dp[1] = 1
dp[2] = 1
n = 99

# 피보나치 함수 반복문으로 구현 (바텀업 DP)
for i in range(3, n+1):
    dp[i] = dp[i-1] + dp[i-2]

바텀업 방식은 재귀가 아닌 단순 반복문을 이용하여 작은 문제부터 해결해 나아가며 최종 답안을 도출해내는 방식을 의미합니다.

 

핵심 정리

• DP는 한번 계산한 결과를 특정 메모리에 기록하여 해당 결과를 이용하여 빠르게 정답을 얻어내는 방식. -> 메모이제이션!
• DP 구성방식은 탑다운 & 바텀업 크게 두 가지로 나뉜다.
  • 탑다운 : 가장 큰 문제를 방문 후 작은 문제를 호출하여 답을 찾는 방식.
  • 바텀업 : 가장 작은 문제들부터 답을 구해가며 전체 문제의 답을 찾는 방식.

탑다운 방식은 점화식을 이해하기 쉽다는 장점이 있고, 바텀업 방식은 재귀를 이용하지 않기 때문에 메모리 사용량을 줄일 수 있다는 장점이 있습니다.

 

예제풀이

---

백준 - 1463 _ 1로 만들기

 

문제

---

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

입력

---

첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다.

 

출력

---

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

제출코드

---

def calc(arr):
  l = []
  for num in arr:
    l.append(num-1)
    if num%3 == 0:
      l.append(num//3)
    if num%2 == 0:
      l.append(num//2)
  return l

n = int(input())
cnt = 0
arr = [n]
while True:
  if 1 in arr:
    print(cnt)
    break
  arr = calc(arr)
  cnt += 1

 

문제풀이

---

정수 x에 사용할 수 있는 연산은 세 가지가 있으며 해당 연산들을 적절히 사용하여 x를 1로 만들어야 합니다.

 

입력받는 수에 따라서 세 가지 연산중 연산이 가능한 경우도 있고 불가능한 경우도 있을 것입니다.

 

문제의 핵심은 연산을 진행한 결과에 다시 또 연산을 진행하고 또 연산을 진행하며 1로 만들어야 합니다.

 

즉, 연산을 진행한 결과값을 기록하고 이를 다음 연산에 활용하면 중복되는 연산을 진행할 필요가 없습니다.

 

따라서 3 가지 연산 중 가능한 연산들을 수행한 결과 배열을 반환하는 calc(arr) 라는 함수를 정의합니다.

 

이 함수의 인자값으로 이전 연산의 결과값 배열을 전달합니다.

 

예를 들어 입력값으로 10이 들어온 경우를 살펴보겠습니다.

 

첫 calc 함수 실행시 [10]을 전달하면 [9, 5] 을 반환합니다.

 

이후 [9, 5] 를 입력값으로 calc 함수를 실행하면 [8, 3, 4] 을 반환합니다.

 

[8, 3, 4]를 다시 calc 함수의 인자로 전달하면 [7, 4, 2, 1, 3, 2] 가 반환되어 여태 진행된 연산 횟수 3을 출력하고 프로그램을 종료하게 됩니다.