Dynamic Programming( 동적계획법 )

 

---

 

■ 동적계획법, (aka. DP)

 

- 입력 크기가 작은 부분 문제들을 해결한 후, 해당 문제의 해를 활용해서 큰 부분 문제를 해결

   ( bottom to up-towards solution )

- 이 과정에서 Memoization을 이용, 계산 결과가 저장되는 형식을 채택해 전체 실행 속도를 높임

- 최종 해를 구하는 과정에서 greedy 방식이 사용되는 경우도 많음

 

 

■ 예시

1) Fibonacci 예시 1

def fibo_dp(num):
    cache =  [ 0 for index in range(num + 1) ]
    cache[0] = 0
    cache[1] = 1
    
    for index in range(2, num + 1):
        cache[index] = cache[index - 1] + cache[index - 2]
    return cache[num]

 

2) Fibonacci 예시 2

def fibo(num):
 
    # cash defined
    # 0번 index 무시위해 + 1 크기 설정
    data = [0]*(num + 1) 
    
    for i in range(1, num + 1):
        if i == 1:
            data[i] = 1
        elif i == 2:
            data[i] = 1
        else:
            data[i] = data[i-1] + data[i-2]
            
    return data[-1]
    
print(fibo(10))
>>> 55

 

3) stack & 동적 계획법

문제 예시 : jinho-study.tistory.com/801

> 첫 번째 줄에 빌딩의 개수 N이 입력된다(1 ≤ N ≤ 80,000) 라는 조건

   → 1중 for문의 경우 : 8만번 연산

   → 2중 for문의 경우 : 8만번 연산 * ( 4만번 연산 ) = 32억번 === 이중 for문 안됨

import sys

N = int(sys.stdin.readline())
li = [int(sys.stdin.readline()) for _ in range(N)]
stack, res = [], 0
for i in range(N):
    print(f'li[i] : {li[i]}')
    while stack != [] and stack[-1] <= li[i]:
        stack.pop()
    stack.append(li[i])
    print(f'stack : {stack}')
    res += len(stack)-1 # 시작점 제외(== 끝포인트 부터 앞에까지 count)
    print(f'res : {res}')
    print(f'')
    
print(res)



>>> # Stdin Inputs
6 # 다음 줄의 개수
10 # 빌딩 높이 시작
3
7
4
12
2

>>> # 결과
li[i] : 10
stack : [10]
res : 0

li[i] : 3
stack : [10, 3]
res : 1

li[i] : 7
stack : [10, 7]
res : 2

li[i] : 4
# 10과 4, 7과 4 == (1 + 1) == len(stack)(=3) - 1(=기준점 4)
stack : [10, 7, 4] 
res : 4

li[i] : 12
stack : [12]
res : 4

li[i] : 2
stack : [12, 2]
res : 5

5

> 새로 들어온 포인트를 [stack 동적 계획법]으로 '계산에 필요하기 때문에 살아남은' legacy 포인트와 비교해서 계산 후,

   다음 포인트 계산시 이 결과를 재활용

> O(N) 1중 for 문 유지하면서 문제 해결

 

---

■ 동적 계획법의 장점

기존 계산 결과 재활용 가능할 것 같으면 동적계획법 쓰는게 좋음

Fibonacci 경우 동적계획법 // 동적 계획법 + 재귀 : 의 두 방식이 있음

 

 

> 결과 비교

import time

_dict = {}

def fibo(num, dp = True):
    
    if num == 1:
        return 1
    elif num == 2:
        return 2
    
    else:
        if dp:
            if num in _dict:
                return _dict[num]
            else:
                _dict[num] = fibo(num-1) + fibo(num-2)
                return _dict[num]
        else:
            return fibo(num-1) + fibo(num-2)

# 재귀만 적용
st_1 = time.time()
print(fibo(100, dp=False))
print(f'elapsed : {(time.time()-st_1)*1000} ms')
>>>
573147844013817084101
elapsed : 0.20074844360351562 ms


# 동적 계획법 + 재귀 적용
st_1 = time.time()
print(fibo(100))
print(f'elapsed : {(time.time()-st_1)*1000} ms')
>>>
573147844013817084101
elapsed : 0.07152557373046875 ms

---

■ 프로그래머스 동적계획법 문제 예시

 

programmers.co.kr/learn/courses/30/lessons/43105?language=python3

코딩테스트 연습 - 정수 삼각형

 

programmers.co.kr/learn/courses/30/lessons/42898?language=python3

코딩테스트 연습 - 등굣길

programmers.co.kr/learn/courses/30/lessons/12914

코딩테스트 연습 - 멀리 뛰기

참조 :

https://www.fun-coding.org/Chapter14-dp_divide.html

파이썬과 컴퓨터 사이언스(기본 알고리즘): 동적 계획법과 분할 정복 - 잔재미코딩

blog.shovelman.dev/431

#004_자료구조와 알고리즘_Stack과 동적 프로그래밍

---