다이나믹 프로그래밍이란? 작은 문제로 나누고 메모이제이션하는 기법

안녕하세요, 김코딩스타입니다. 오늘은 프로그래밍 블로그 코딩의 신에서 다이나믹 프로그래밍에 대해 알아보겠습니다. 다이나믹 프로그래밍이란 무엇이고, 어떤 문제에 적용할 수 있는지, 그리고 어떤 방법으로 구현할 수 있는지에 대해 자세히 설명해드릴 예정입니다. 다이나믹 프로그래밍을 이해하고 활용하면 프로그래밍의 세계가 훨씬 넓어지고 재미있어질 것입니다. 그럼 시작해볼까요?

다이나믹 프로그래밍이란?

 

다이나믹 프로그래밍은 큰 문제를 작은 문제로 나누어 푸는 분할 정복 기법의 일종입니다. 다만, 분할 정복과 다른 점은 작은 문제들이 중복되어 발생한다는 것입니다. 즉, 같은 문제를 반복적으로 풀어야 하는 경우가 많습니다. 이런 경우에는 작은 문제의 해답을 저장해두고, 필요할 때마다 꺼내서 사용하는 방식으로 시간을 절약할 수 있습니다. 이렇게 작은 문제의 해답을 저장하는 공간을 메모리라고 하며, 메모리에 저장된 값을 메모이제이션이라고 합니다.

 

---

 

 

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

 

다이나믹 프로그래밍을 적용하기 위해서는 두 가지 조건을 만족해야 합니다. 첫 번째 조건은 최적 부분 구조입니다. 최적 부분 구조란 큰 문제의 최적해가 작은 문제의 최적해로부터 구성되는 경우를 말합니다. 예를 들어, 피보나치 수열에서 n번째 항은 n-1번째 항과 n-2번째 항의 합으로 구할 수 있습니다. 따라서 n번째 항의 최적해는 n-1번째 항과 n-2번째 항의 최적해로부터 구할 수 있습니다. 두 번째 조건은 중복 부분 문제입니다. 중복 부분 문제란 작은 문제들이 여러 번 반복해서 발생하는 경우를 말합니다. 예를 들어, 피보나치 수열에서 n번째 항을 구하기 위해서는 n-1번째 항과 n-2번째 항을 구해야 하는데, 이 때 n-1번째 항을 구하기 위해서는 n-2번째 항과 n-3번째 항을 구해야 하고, 이런 식으로 같은 문제가 반복해서 발생합니다.

 

---

 

 

다이나믹 프로그래밍의 구현 방법

 

다이나믹 프로그래밍을 구현하는 방법에는 두 가지가 있습니다. 첫 번째 방법은 탑다운 방식입니다. 탑다운 방식은 큰 문제에서 작은 문제로 내려가면서 해결하는 방식입니다. 재귀 함수를 사용하여 구현할 수 있습니다. 예를 들어, 피보나치 수열에서 n번째 항을 구하는 함수를 작성한다면 다음과 같습니다.

 

# 메모리 생성

memo = [0] * 100

 

# 피보나치 수열 함수

def fibo(n):

    # 기저 조건

    if n == 1 or n == 2:

        return 1

    # 메모이제이션

    if memo[n] != 0:

        return memo[n]

    # 재귀 호출

    memo[n] = fibo(n-1) + fibo(n-2)

    return memo[n]

 

두 번째 방법은 바텀업 방식입니다. 바텀업 방식은 작은 문제에서 큰 문제로 올라가면서 해결하는 방식입니다. 반복문을 사용하여 구현할 수 있습니다. 예를 들어, 피보나치 수열에서 n번째 항을 구하는 함수를 작성한다면 다음과 같습니다.

 

# 메모리 생성

memo = [0] * 100

 

# 피보나치 수열 함수

def fibo(n):

    # 기저 조건

    memo = 1

    memo = 1

    # 반복문

    for i in range(3, n+1):

        memo[i] = memo[i-1] + memo[i-2]

    return memo[n]

 

 

---

 

 

이상으로 다이나믹 프로그래밍에 대해 알아보았습니다. 다이나믹 프로그래밍은 많은 프로그래밍 문제에 적용할 수 있는 강력한 기법입니다. 다만, 다이나믹 프로그래밍을 적용하기 위해서는 문제의 특성을 잘 파악하고, 적절한 메모리를 사용해야 합니다. 다이나믹 프로그래밍을 통해 프로그래밍의 세계를 더욱 즐겁게 탐험해보세요!

다음 포스팅에서는 다이나믹 프로그래밍의 응용 예시로 최장 증가 부분 수열 문제를 소개하겠습니다. 많은 관심 부탁드립니다. 읽어주셔서 감사합니다.^^