자료구조/알고리즘 Dynamic Programming

DP

DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다.

피보나치 수열로 예를 들어 본다면,

def fibo(n):
    if n in [1, 2]:
        return 1
    return fibo(n-1) + fibo(n-2)


assert fibo(10) == 55
assert fibo(100) == 354224848179261915075 # 안끝난다.

이런식으로 재귀 함수로 푼다면 100번째 값을 찾을 때는 fibo(1)번째, fibo(2)번째를 찾았던 n번째수를 계속해서 찾아나갈 것이다.

그렇지만 찾아 나간 결과를 저장해두고 그 값을 이용한다면 시간복잡도는 확실히 줄것이다.

memo = {1: 1, 2: 1}


def fibo(n):
    if n in memo:
        return memo[n]
    memo[n] = fibo(n - 1) + fibo(n - 2)
    return memo[n]


assert fibo(10) == 55
assert fibo(100) == 354224848179261915075

이런식으로 값을 저장해두고 그 값을 다시 사용해서 반복횟수를 줄이는 것이 동적 계획법이라고 한다.

회고

알고리즘 주차가 마무리 되었다.

내일부터는 주특기주차가 시작된다. 주특기를 한다고 해도 알고리즘은 쉬운 문제로 하루에 2~3문제씩 풀 생각이다.

그리고 CS 발표 준비를 했다. 작문과 비슷한 프로그래밍이라는 주제로 발표하게 되었다.

https://geonoo.tistory.com/144

작문과 비슷한 프로그래밍

 

마지막으로 오늘은 김영한님의 인프런 입문강의를 다 듣고 잘거다!

^0^!