한 번으로 코딩 역량을 향상하는 동적프로그래밍 기법을 알아보자! 🔥

동적프로그래밍은 처음 들어보는 사람들에게는 어려울 수 있지만, 실제로 코드를 작성해보면 그리 어렵지 않습니다.

 

 

 

아래 예제는 대표적인 동적프로그래밍 문제 중 하나인 피보나치 수열을 살펴보지만, 피보나치하면 재귀를 생각하시는데

 

결론은 dp를 사용할때 재귀를 사용하지않고도 반복문과 배열만을 이용해서도 가능하다 입니다.

 

동적프로그래밍의 기본 개념과 적용 방법을 알아보겠습니다.

 

 

---

 

아래에는 1)일반적인 피보나치와, 2)TOP-DOWN 방식과 3)BOTTOM-UP 방식으로 구현한 피보나치 수열 코드가 있습니다. 코드를 따라해보면서, 동적프로그래밍의 장점과 효율성을 알아보겠습니다 💻

 

 

🔍 피보나치 수열과의 비교

동적프로그래밍의 개념을 이해하기 위해 가장 대표적인 예시인 피보나치 수열을 살펴보겠습니다. 피보나치 수열은 첫번째와 두번째 항이 1이며, 이후의 항은 이전 두 항의 합으로 이루어진 수열입니다.

1) 피보나치 수열

def fib(n):
    if n == 0 :
        return 0

    elif n == 1 :
        return 1
    else :
        return fib(n-1) + fib(n-2)

피보나치 수열을 재귀적으로 구현할 경우, 중복 계산이 많이 발생하게 되어 시간 복잡도가 지수적으로 증가합니다.

 

이때 동적프로그래밍을 적용하면 중복 계산을 줄이고 시간 복잡도를 선형적으로 개선할 수 있습니다.

 

 

 

1.53초 가 나온것을 확일 할 수 있다.

피보나치의 시간복잡도는 O(2**n)

 

---

🔍 동적프로그래밍 TOP-DOWN vs. BOTTOM-UP

동적 프로그래밍에서 가장 많이 사용되는 두 가지 방법은 TOP-DOWN과 BOTTOM-UP입니다. TOP-DOWN 방식은 재귀 호출과 Memoization(메모이제이션)을 이용하여 문제를 해결합니다.

 

 

"메모이제이션"?? -->기록한다고 생각하면 됩니다.

 

 

아래코드를 보면

1) Top-down 방식

array=[0,1]
def fib_top_dp(n):
    if n < len(array):
        return array[n]
    else:
        fib = fib_top_dp(n-1) + fib_top_dp(n-2)
        array.append(array)
        return array

array배열이 메모이제이션 역할을 합니다. 기록을 해두었다가 따로 계산을 하지 않고, 배열에서 직접 꺼내옵니다.

198ns초

시간복잡도는 O(n)

하지만, 이러한 재귀방식은 함수 호출에 따른 콜스택 오버플로우 등의 문제가 발생할 가능성이 있습니다.

fib(5000) 큰 수를 입력하니 커널이 자꾸 죽는다.

이에 비해, BOTTOM-UP 방식은 반복문과 배열을 이용하여 문제를 해결하며,

이전에 구한 값을 저장하기 위한 오버헤드가 발생하지 않습니다. 그래서 TOP-DOWN대신 BOTTOM-UP 방식을 사용하는 경우가 많습니다.

 

---

2) Bottom-up 방식

def fibo_dp (n):
    if n == 0 :
        return 0
    elif n == 1 :
        return 1
    array = [0,1]

    for i in range(2,n+1) :
        num = array[i-1] + array[i-2]
        array.append(num)
    return array[n]

재귀를 사용하지 않고 반복문과 배열만을 이용 한 모습

큰 수를 입력하여도 오버헤드가 발생하지 않는다.

 

이후에는 일반적인 피보나치 코드 하나, dp를 이용한 코드 두 개 모두 안 보고 코드를 작성해보시길 권합니다.

 

 

감사합니다

🙇