알고리즘 - 동적 프로그래밍 : Dynamic Programming

Dynamic Programming

큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말

분할정복과 유사함

분할 정복과 동적 프로그래밍의 차이는 작은 문제가 중복이 일어나는지의 차이이다.

분할 정복은 큰 문제를 작게 나누어 푸는 방법이며, 동적 프로그래밍은 작은 문제들이 반복되는 것이다.

동적 프로그래밍의 답은 일정하면 바뀌지 않는다.

동적 프로그래밍 방법과 조건

모든 작은 문제들을 한번만 풀어야 한다.

정답을 구한 작은 문제들을 어딘가에 메모하고 큰 문제를 풀 때 작은 문제가 나타나면

앞에서 메모한 결과를 이용해서 큰 문제를 푼다.

동적 프로그래밍의 사용 조건은 아래와 같다.

작은 문제가 반복이 일어나는 경우
문제가 구할 때마다 정답이 같은 경우

Memoization

메모제이션은 동적 프로그래밍에서 작은 문제들이 반복되고, 이 작은 문제들의 결과값이 항상 같은것을 이용한다.

한번 계산한 작은 문제를 저장해놓고 다시 사용하는 것을 뜻한다.

피보나치를 예로 들면 피보나치는 1, 1, 2, 3, 5,8.. 등의 수를 이루게 되는데,

다음 수열 = 이전 수열 + 두단계 전 수열의 합 이라는 점화식을 갖는 수열이 된다.

재귀 함수로 문제를 풀계되면 간단하게 풀수 있지만, n의 값이 클 경우 일정 수 이상의 순열을 구하기가 어렵다.

동적 계획법의 조건 두가지를 생각하면, 이를 동적 계획법으로 풀 수 있다.

1. 작은 문제들의 반복

F(5)를 구하기 위해서 F(4), F(3)이 필요, 다시 F(4)를 구하기 위해서 F(3), F(2) 필요

이러한 방식이 반복

2. 같은 문제는 구할때 마다 정답이 같음

첫번째, 두번째 수열은 항상 값이 1이며 3번째 수열은 언제나 값이 2

언제나 정답이 같다는 사실이 적용

동적 계획법 구현 방법

1. Bottom - Up 방식 : 작은 문제부터 큰 문제로 확장

import sys 
# Bottom - up : 작은 문제부터 구하는 방법
def fibonacci_bottom_up(n):
    if n <= 1:
        return n
    
    fir = 0
    sec = 1 
    for i in range(0,n-1):
        next = fir+sec
        fir = sec
        sec = next
    return next

n = int(sys.stdin.readline())
print(fibonacci_bottom_up(n))

2. Top - Down 방식 : 큰 문제부터 작은 문제로 축소

# Top - down : 큰 문제부터 구하는 방법
# 재귀함수로 구현하는 경우
memo = []
def fibonacci_top_down(n):
    if memo[n] > 0:
        return memo[n]
    
    if n <=1 :
        memo[n] = n
        return memo[n]
    else :
        memo[n] = fibonacci_top_down(n-1) + fibonacci_top_down(n-2)
        return memo[n]

memo = [0 for i in range(100)]
n = int(sys.stdin.readline())
print(fibonacci_top_down(n))

더 좋은 알고리즘?

Top - Down의 경우 소스 가독성이 증가하지만 작성이 다소 어려움,

Bottom - Up의 경우는 풀기 쉽지만 소스의 가독성이 저하된다.

규칙을 찾아서 더 좋은 방식을 적용하는 것이 좋음

저작자표시