본문 바로가기

알고리즘/알고리즘&자료구조

[알고리즘] 다이나믹 프로그래밍(Dynamic Programming)

728x90

< Dynamic Programming(동적 계획법) >

- 큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말이다. 

- 부분 문제 반복(Overlapping subproblems)과 최적 부분 구조(Optimal substructure)를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

 


 

➰ 분할정복(Divide and Conquer)과 비슷하지 않나?

- 비슷하지만 결정적인 차이점이 있다.

- 작은 문제가 중복이 일어나는지 안일어나는지가 분할정복과 동적 계획법의 차이다.

- 분할정복은 큰 문제를 해결하기 어려워서 단지 작은 문제로 나누어 푸는 방법 -> 작은 문제에서 반복이 일어나지 않는다

- 동적계획법은 작은 부분 문제들이 반복된다!!!!

 

➰ Dynamic Programming 조건

- 작은 문제가 반복해서 일어나는 경우

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

 

 

 Dynamic Programming 방법

- 모든 작은 문제들은 한번만 풀어야 하기 때문에 정답을 구한 작은 문제들은 어딘가에 메모해야 한다

- 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 메모한 작은 문제의 결과값을 이용한다

 

 

 


 

🌼 좋은 예시 - 피보나치 수열

이런 피보나치 수열을 트리 형태로 나타내면, 소문제가 상위 문제를 해결하기 위해 사용되는 것을 알 수 있다. 

 

 

이때 문제점이 있는데, 소문제의 결과가 상위문제의 결과를 찾는 데 사용됨으로 각각의 소문제는 중복될 수가 있다. 이렇게 되면 같은 소문제를 여러번 반복해서 계산하다 보니 자원낭비가 심해진다.

 

이럴때 동적 계획법은 소문제의 답을 따로 메모해두고 이를 더 큰 문제를 푸는데 이용한다. 

그래서 자원 절약과 시간 절약을 한다!!

 

 

Memoization (Top-Down, 하향식)

-  하위 문제에 대하여 정답을 계산했는지 확인해가며 문제를 자연스럽게 풀어나가는 방법

 

dp = [0]*100 # 소문제 결과를 저장할 리스트
dp[0] = 1 
dp[1] = 1

def fib(n):
    
    # 만약 계산한 적이 없다면 재귀로 계산 
    if dp[n] == 0:
        dp[n] = fib(n-1) + fib(n-2)
    
    # 있다면 그대로 반환 
    return dp[n]

fib(10)

 

상향식, Bottom-Up

- 더 작은 하위 문제부터 살펴본 다음 작은 문제의 정답을 이용해서 큰 문제의 정답을 풀어나가는 방법

def fib(n):

    dp = [0]*(n+1)
    dp[0] = 1
    dp[1] = 1
    
    # 작은 값(소문제)부터 직접 계산하며 진행 
    for i in range(2,n+1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

 


https://doing7.tistory.com/75

 

[알고리즘] 다이나믹 프로그래밍 with Python

💡 다이나믹 프로그래밍 필요한 계산 값을 저장해두었다가 재사용하는 알고리즘 설계 기법이다. 큰 문제를 한번에 해결하기 어려울 때, 여러개의 작은 문제로 나누어 푸는 '분할 정복' 알고리

doing7.tistory.com

 

https://velog.io/@bonjaski0989/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-%EC%A0%95%EB%A6%AC%EA%B8%80Python

 

동적계획법(Dynamic Programming) 정리글_Python

동적계획법에 대한 정리글입니다. (피보나치 수열 파이썬 구현)

velog.io

 

https://lsh424.tistory.com/76

 

[알고리즘] Dynamic programming (동적 계획법) 완전정복 with Python

동적 계획법 - 주어진 문제를 여러 개의 소문제로 분할하여 각 소문제의 해결안을 바탕으로 주어진 문제를 해결, 이때 각 소문제는 다시 또 여러 개의 소문제로 분할 가능하다. 각 소문제는 원래

lsh424.tistory.com