[Algorithm] 알고리즘 - Dynamic Programming(동적 프로그래밍)

 

동적 프로그래밍, 즉 동적 계획법(Dynamic Programming, DP)은 복잡한 큰 문제를 작은 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법들을 결합하여 최종적인 목적에 도달하는 문제 해결 방식이다.

 

각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그 것을 간단하게 해결할 수 있다.

 

▶ 계산 횟수를 줄일 수 있다.

▶ 최장 공통 부분 수열, 최단 경로 문제, 벨만-포드 알고리즘, 플로이드-워셜 알고리즘, 배낭 문제 등에 사용 된다.

▶ 동적 계획법은 모든 방법을 일일이 검토하여 그 중에 최적화된 결과를 찾아내는 주먹구구식 방법이라고 생각할 수 있지만, 문제가 가능한 모든 방법을 충분히 빠른 속도로 처리할 수 있는 경우에는 최적의 해결 방법이다.

 

- Divide and Conquer (분할정복)

분할정복: 

동적 계획법은 분할정복과 비슷하지만, 결정적으로 다른 점은 작은 문제에서 중복이 일어나는지 안일어나는지 이다.

 

- 메모이제이션(memoization)

: 중복된 계산을 막기 위해 저장된 결과를 배열에 저장한 뒤, 다음 번에 똑같은 계산이 필요할 때에는 저장된 값을 불러와서 중복을 없애는 기법이다.

: 시간 복잡도가 줄어든다.

 

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

Fibonacci 수열의 경우 첫번째 두번째 수열은 각각 1로 고정되어 있다.(편의상 0번째 항이 0이 되는 경우도 있다.) 즉, 3번째 수열은 언제나 결과가 2 다. 또 4번째 수열은 3번째 수열과 2번째 수열을 이용해 구하므로 언제나 정답이 같다는 사실을 알 수 있다.

def memoization_fibo(n):
    memo[0] = 1
    memo[1] = 1

    if n < 2:
        return memo[n]

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

    return memo[n]

if __name__ == '__main__':
    n = int(sys.stdin.readline())
    memo = [0 for i in range(n+2)]
    print(memoization_fibo(n))

 

n번째 Fibonacci 수열을 구하는 문제를 동적프로그래밍으로 푼 코드이다. 0, 1번째 수열은 항상 1이므로 배열에 미리 저장한다. 그 후 2번째 수열을 구할때에는 배열에 저장된 이 값을 이용한다. 구한 2번째 수열의 결과 값을 배열에 다시 저장한다. 그런식으로 진행하며 입력받은 n번째 수열을 구하게 된다.

 

*항상 배열을 이용할 때에는 인덱스를 주의해야 합니다.

 

 

- Bottom-up 과 Top-down

• Bottom-up: Bottom-up의 경우 작은 문제부터 차근차근 구해나아가는 방법입니다.
• Top-down: 재귀함수로 구현하는 경우가 대부분 Top-down이라고 생각하면 됩니다. 큰 문제를 풀 때 작은문제가 아직 풀리지 않았다면 그제서야 작은 문제를 해결하게됩니다.

(출처: https://galid1.tistory.com/507)

 

 

 

- 접근 (출처: 나무위키 https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95)

동적 계획법의 개념과 구현에 대해 정확하게 짚고 넘어가기 위해 동적 계획법을 적용시킬 수 있는 예에 대해 알아보자.

• f(a,b) = f(a-1,b) + f(a,b-1) (a,b >= 1 )

• f(0,0) = 1, 임의의 자연수 n에 대해 f(n,0) = f(0,n) = 1

위와 같이 정의된 함수에서 주어진 임의의 a,b에 대해 f(a,b)의 값을 효율적으로 구하고자 할 때 동적 계획법을 적용시킬 수 있다.
예를 들어 f(2,2)을 계산한다고 해보자. 이 경우 아래 그림과 같은 참조를 거치게 된다.

순서대로 계산횟수를 구해보면 f(2,2)를 구하기 위해 총 5번의 연산을 거쳐야한다. 이 때 중복되는 부분 문제[3]에 대한 답을 미리 계산해놓고 연산한다고 가정했을 때 계산횟수를 구해보면 f(2,2)를 구하기 위해 4번의 연산을 거쳐야한다. 이 경우 간단한 예라 중복되는 부분 문제가 f(1,1) 하나 뿐이기 때문에 큰 속도의 이득을 볼 수 없지만 a,b의 값이 커질 수록 속도 면에서 엄청난 이득을 볼 수 있다. 몇 가지 a,b 값에 대해 f(a,b)를 구하기 위한 연산 횟수를 나타낸 아래 표를 참조해보자.

(a,b)	그냥 계산시 연산 횟수	동적 계획법 이용시 연산 횟수
(2,2)	5	4
(4,4)	69	16
(6,8)	3002	48
(10,10)	184755	100

이 정도면 아마 대충 동적 계획법의 효율이 느껴질 것이다. 실제로 a,b가 1증가할 때마다 연산 횟수는 기하급수적으로 증가하며, 이 때 중복되는 부분 문제를 적절히 처리해줌으로써 높은 계산효율을 얻을 수 있는 것이다.

 

 

 

출처: 

https://kimlog.me/algorithm/2016-05-15-dynamic-programing.md/

https://coding-all.tistory.com/2