알고리즘 - 동적 프로그래밍 알고리즘(Dynamic programming algorithm)

 

 

다이나믹 프로그래밍

- 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다.

- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

- 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운 보텀업)으로 구성된다. / 하향식, 상향식(보텀업)

알고리즘에서 사용되는 다이나믹 프로그래밍에서 다이나믹은 별다른 의미 없이 사용된 단어이다.

 

 

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

1. 최적 부분 구조(Optimal Substructure)

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

 

2 중복되는 부분 문제(Overlapping Subproblem)

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

 

 

<다이나믹 프로그램으로 구현할 수 있는 문제 - 피보나치 수열>

- 앞에 있는 두 수의 합으로 구성되는 것이 피보나치 수열의 특징이다.

- 추가적으로 시작부분의 항을 알고 있다면 모든 항에 대해서 각각의 답을 알수 있다.

- 배열, 리스트로 구현이 가능하다.

- 수열(=Sequence)

 

<피보나치 함수(Fibonacci Function)을 재귀함수로 구현>

#피보나치 함수(Fibonacci Function)을 재귀함수로 구현

def fibo(x):
    #재귀함수가 무한루프를 돌지 않고 언제 멈출지에 대해서 명시해주는 것. 
    if x == 1 or x == 2:
        return 1
    return fibo(x-1) + fibo(x-2)
print(fibo(4))

 

<피보나치 수열의 시간 복잡도 분석>

- f(2)를 5번이나 재호출하는 경우가 생기게 된다.

- 해결된 부분문제를 따로 담아 저장하지 않으면 수행시간이 비효율적으로 쓰이게 된다.

 

 

<피보나치 수열의 효과적인 해법: 다이나믹 프로그래밍>

- 작은 문제를 모아서 큰 문제를 해결할 수 있다 -> 최적 부분 구조

- 동일한 문제를 반복적으로 해결한다 -> 중복되는 부분 문제

 

 

<다이나믹 프로그래밍 구현방법1 - 메모이제이션(Memoization)/top-down>

- dp / d / cach / memo라고 함수 이름을 짓는 것이 일반적이다.

- 탑다운 방식은 재귀를 자주 이용

- 보텀업 방식은 반복문을 이용

 

<피보나치 수열: 탑다운 다이나믹 프로그래밍 소스코드(Python)>

#한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
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))

- 피보나치 수열을 살펴보면 여러번 문제가 재등장해서 다시 풀어야하는 경우가 생긴다 이러한 경우 메모리 낭비가 있기 때문에 아예 저장을 해둔 뒤 쓰는 방식인 탑다운 다이나믹 프로그래밍을 이용해서 메모리 낭비를 줄일 수 있다. 

 

 

<피보나치 수열: 보텀업 다이나믹 프로그래밍 소스코드(Python)>

#앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화(DP = Dynamic programming)
d = [0] * 100

#첫 번째 두 번째 피보나치 수는 1
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])

- 보텀업 다이나믹 프로그래밍의 경우엔 반복문을 사용해서 구현한다.

 

 

<피보나치 수열: 메모이제이션 동작분석>

 

 

<다이나믹 프로그래밍 VS 분할 정복>

 

 

<다이나믹 프로그램밍 문제에 접근하는 방법>