정글 TIL 11 (01.22) "SSS급 재귀자의 다이나믹한 계획법"

김동준·2024년 1월 22일
TIL알고리즘

알고리즘

목록 보기
9/11

제목은 그저 회귀 문제를 다이나믹 프로그래밍(동적 계획법) 으로 풀다 생각났습니다. (제 요즘 낙입니다)

다이나믹 프로그래밍(DP, 동적 계획법)

소개

"복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말합니다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용합니다." - Wikipedia

정리하자면 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용하는 "기억하며 풀기"라고 볼 수 있습니다.

  • 동적 계획법을 이용하면 계산 횟수를 줄일 수 있습니다. 그래서 하위 문제의 수가 기하급수적으로 증가할 때 유용합니다. (예를 들어 피보나치 문제)

  • 문제를 해결하기 위한 모든 방법을 검토하고, 그 중에 최적의 풀이법을 찾아내기 때문에 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용됩니다.

동적 계획법의 효용을 알기 위해 유명한 재귀 문제인 피보나치 수 문제에 적용해보고, 비교해보겠습니다.

2747 피보나치 수(1)

첫째 줄에 45보다 작거나 같은 자연수인 n이 주어집니다. 이에 n번째 피보나치 수를 출력하는 문제입니다.
더 많은 풀이 방법이 있겠지만, 세 가지 사례를 비교해보겠습니다.
1. 반복문을 활용한 사례
2. 재귀 함수만을 이용한 사례
3. DP를 활용한 사례

  • for문으로 구현
import sys
import time

input = sys.stdin.readline
n = int(input())
start = time.time()

a, b = 0, 1
for i in range(n):
    a, b = b, a + b

print(f"Fibonacci Result: {a}, Time: {time.time() - start:.16f} sec")
  • 재귀문으로 구현
import sys
import time

input = sys.stdin.readline
n = int(input())
start = time.time()

def recursion_fibo(n):
    return 1 if n<=2 else recursion_fibo(n-2) + recursion_fibo(n-1)

print(f"n이 {n}일 때 :")
print(f"Fibo_Recur : {recursion_fibo(n)}, Time : {time.time() - start:.16f}sec")
  • DP를 활용해 구현
import time
import sys

n = int(sys.stdin.readline())
start = time.time()

def dp_fibo(n):
    dp = [0] * (n+1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n+1):
        dp[i] = dp[i-2] + dp[i-1]
    return dp[n]

print(f"n이 {n}일 때 :")
print(f"Fibo_DP Result: {dp_fibo(n)}, Time: {time.time() - start:.16f} sec")
  • for문으로 구현한 경우
    n이 30일 때:
    Fibo_Loop Result: 832040,
    Time: 0.0004923343658447 sec
    n이 10000일 때:
    Fibo_Loop Result: 33644764...,
    Time: 0.0040242671966553 sec
  • 단순 재귀문으로 구현한 경우
  • n이 30일 때 :
    Fibo_Recur : 832040,
    Time : 1.9558362960815430 sec
  • n이 10000일 때 :
    측정 불가
  • DP를 활용하여 구현한 경우
  • n이 30일 때 :
    Fibo_Loop Result: 832040,
    Time: 0.0010173320770264 sec
  • n이 10000일 때 :
    Fibo_DP Result: 336447648764 ...,
    Time: 0.0070168972015381 sec

느낌이 오시나요? 계산 시간이 DP가 for문으로 반복한 경우에 거의 근접합니다.
반면, 단순 재귀함수로 재현한 경우 n이 30일 때 2초에 근접하며, n이 10000일 때는 계산조차 불가능합니다.
이는 n이 클수록 단순 재귀함수로는 구현할 수 없음을 뜻합니다.
조금 더 심화된 문제로 비교해볼까요?

9095 1,2,3 더하기

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있습니다. 합을 나타낼 때는 수를 1개 이상 사용해야 합니다.
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1
이처럼 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제입니다.

이 문제 또한 재귀 문제로서 피보나치 수열과 같은 방식으로 3가지 방식으로 구현하고 비교해보겠습니다.

  • for 문으로 구현
import sys
import time

n = int(sys.stdin.readline())
start = time.time()
a, b, c = 1, 2, 4

for _ in range(1, n):
    a, b, c = b, c, a + b + c

print(f"n이 {n}일 때 :")
print(f"Plus with loop: {a}, Time: {time.time() - start:.16f} sec")
  • 재귀문으로 구현
import sys
import time

n = int(sys.stdin.readline())
start = time.time()

def recur(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    else:
        return recur(n - 1) + recur(n - 2) + recur(n - 3)
    
print(f"n이 {n}일 때 :")
print(f" Plus with Recursion : {recur(n)}, Time : {time.time() - start:.16f}sec")
  • DP를 활용한 구현
import time
import sys

n = int(sys.stdin.readline())
start = time.time()

dp = [0] * (n + 1)

for i in range(1, n + 1):
    if i == 1:
        dp[i] = 1
    elif i == 2:
        dp[i] = 2
    elif i == 3:
        dp[i] = 4
    else:
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

print(f"n이 {n}일 때 :")
print(f"Plus with Dynamic Programming : {dp[n]}, Time : {time.time() - start:.16f}sec")
  • for문으로 구현한 경우
    n이 30일 때 :
    Plus with loop: 53798080,
    Time: 0.0004506111145020 sec
    n이 10000일 때 :
    Plus with loop: 193071563 ...,
    Time: 0.0063436031341553 sec
  • 재귀 함수로 구현한 경우
    n이 30일 때 :
    Plus with Recursion : 53798080,
    Time : 46.2734870910644531sec
    n이 10000일 때 :
    구현 불가
  • DP를 활용한 경우
    n이 30일 때 :
    Plus with Dynamic Programming : 53798080,
    Time : 0.0011804103851318sec
    n이 10000일 때 :
    Plus with Dynamic Programming : 19307156388 ...,
    Time : 0.0127346515655518sec

DP의 장점

1,2,3 더하기 문제에서도 DP는 30 이상의 큰 숫자들을 계산하지 못 하는 반면에, for문과 DP에서는 훨씬 큰 n이 10000일 때도 구현해냅니다.
이러한 결과로 보아 일반적인 재귀를 단순히 사용할 시에 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 되고 있음을 알 수 있습니다.
아래의 그림을 보면 더 와닿으실겁니다.

n = 5일 때 f(1)이 5번 계산된 것이 보이시나요? n = 30일 때는 10,301,680번의 연산이 필요합니다.
그러나 한번 구한 작은 문제의 결과 값을 저장해두고 재사용한다면, 시간 복잡도는 O(n^2)에서 O(f(n))으로 향상됩니다.

그러나 DP를 적용하기 위해서는 2가지 조건을 만족해야 합니다.

  • 겹치는 부분 문제(Overlapping Subproblems)
    동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능합니다. 반대로 말하자면, 부분 문제가 반복적으로 나타나지 않는다면 부분 문제의 결과를 저장하여 재사용이 불가능합니다. 그래서 부분 문제가 중복되지 않는 경우에는 사용할 수 없습니다.
  1. 최적 부분 구조(Optimal Substructure)
    부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우에 적용 가능합니다. 결과적으로 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일합니다.

위의 그림에서 A - X 사이의 최단 거리는 AX2이고 X - B는 BX2입니다. 전체 최단 경로는 AX2 - BX2이므로 다른 경로를 택한다고 해서 전체 최단 경로가 변할 수는 없습니다.

DP의 조건

동적 계획법은 특정한 경우에 사용되는 방법론이기 때문에 일반적으로 DP를 사용하기 전에 아래의 과정을 거쳐야 합니다.

  1. 문제의 변수 파악
  2. 변수 간 관계식 만들기(점화식 만들기)
  3. 메모하기(memoization)
  4. 제한 조건 확인하기
  5. 구현하기

  • 문제의 변수 파악
    DP는 현재 변수에 따라 그 결과 값을 찾고 그것을 전달하여 재사용합니다.
    예를 들어, 피보나치 수열에서 목표는 n번째 숫자를 구하는 것이므로 n이 변수가 됩니다.
    1,2,3 더하기 문제에서도 n번째 1, 2, 3의 합으로 나타내는 방법의 수를 출력하므로 n이 변수입니다.

  • 변수 간 관계식 만들기
    변수들에 의해 결과값이 달라지지만 동일한 변수값인 경우 결과는 동일합니다. 이러한 하위 문제의 결과값을 재사용하여 관계식을 만들어야 합니다.
    이를 점화식이라 부르며, 반복/재귀를 통해 문제가 해결되도록 식을 작성해야 합니다.
    예를 들어, 피보나치 수열에서는 f(n) = f(n-1) + f(n-2) 였습니다. 1,2,3 더하기 문제에서는 f(n) = f(n-1) + f(n-2) + f(n-3)이었습니다.

  • 메모하기
    점화식을 세웠다면 변수의 값에 따른 결과를 저장해야합니다. 이를 메모한다고 하여 memoization이라고 합니다.

위 예제에서는 결과를 저장할 배열인 DP[]를 만들어 하위 문제의 결과값들을 배열 내에 저장하고, 재사용했습니다.

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다. - wikipedia

  • 제한 사항 확인하기
    피보나치 문제와 1, 2, 3 더하기 문제에서처럼, n이 1일 때 1, 2일 때 1 등.. n이 작을 때 점화식을 적용할 수 없는 경우를 코드에 포함해야 합니다.

DP의 구현 방식은 크게 2가지로 나뉩니다.

  • Bottom-Up 방식
    이름에서 보이듯이, 아래에서 부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식입니다.
    1,2,3 문제에서, Bottom-up은 제한 조건인 dp[n]의 n이 3보다 작을 때부터 시작하여 반복문을 통해 점화식으로 dp[n]까지 그 값을 재활용하는 방식이었습니다.

사실 위에서 메모하기 부분에서 Memoization이라고 했는데 Bottom-up일 때는 Tabulation이라고 부른다.
왜냐면 반복을 통해 dp[0]부터 하나 하나씩 채우는 과정을 "table-filling" 하며, 이 Table에 저장된 값에 직접 접근하여 재활용하므로 Tabulation이라는 명칭이 붙었다고 한다. 사실상 근본적인 개념은 결과값을 기억하고 재활용한다는 측면에서 메모하기(Memoization)와 크게 다르지 않다. - 블로그에서(출처)

  • Top-Down 방식
    dp[n]의 값을 찾기 위해 위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 재활용하는 방식입니다.
    피보나치의 예시처럼, f(n) = f(n-2) + f(n-1)의 함수 호출의 과정에서 보이듯이 n=5일 때, f(3), f(2)의 동일한 계산이 반복적으로 나오게 됩니다.
    이 때, 이미 이전에 계산을 완료한 경우에는 단순히 메모리(배열)에 저장되어 있던 내역을 꺼내서 활용하면 된다. 그래서 가장 최근의 상태 값을 메모해 두었다고 하여 Memoization이라고 부릅니다.

출처
https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95
https://hongjw1938.tistory.com/47

profile
김동준
고민하고 고뇌하는 개발자 (점심, 저녁 메뉴를)
이전 포스트

정글 TIL 12(01.23)

다음 포스트

정글 TIL 6(01.17) "RE-zero부터 시작하는 알고리즘"

0개의 댓글