다이나믹 프로그래밍

다이나믹 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 해결하기 위해 문제를 더 작은 하위 문제들로 나누고, 그 하위 문제들의 결과를 저장하여 반복되는 계산을 줄이는 알고리즘 기법입니다. 이 방법은 특히 최적화 문제에서 많이 사용되며, 재귀적 알고리즘의 중복 계산 문제를 해결하는 데 매우 유용합니다.

  • 다이나믹 프로그래밍의 핵심 개념
    • 중복된 하위 문제(Subproblem Overlapping):
      • 다이나믹 프로그래밍은 문제를 하위 문제로 나누었을 때, 이 하위 문제들이 여러 번 반복해서 나타나는 경우에 효과적입니다. 예를 들어, 피보나치 수열을 재귀적으로 계산할 때, 같은 값을 여러 번 계산하는 비효율이 발생합니다.
    • 최적 부분 구조(Optimal Substructure):
      • 문제의 최적 해결 방법이 그 하위 문제들의 최적 해결 방법으로 구성될 수 있을 때, 다이나믹 프로그래밍을 적용할 수 있습니다. 즉, 문제를 작은 문제들로 나누고, 이 작은 문제들의 최적 결과를 조합하여 전체 문제의 최적 결과를 구할 수 있습니다.
    • 메모이제이션(Memoization) 또는 테이블 저장(Tabulation):
      • 메모이제이션: 재귀적으로 문제를 풀 때, 각 하위 문제의 결과를 계산하고, 그 결과를 저장해 두었다가 같은 하위 문제가 다시 등장할 때 재계산하지 않고 저장된 값을 사용하는 방법입니다.
      • 테이블 저장: 문제를 상향식으로 풀어가면서, 작은 하위 문제부터 차례대로 계산한 후 그 결과를 표 형태로 저장해두는 방법입니다. 이후 계산할 때 이 표를 참조합니다.

피보나치 수열 - 탑다운

array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

target = 7

def binary_search(array, target, start, end):
    if start > end:
        return None

    mid = (start + end) // 2

    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    else:
        return binary_search(array, target, mid + 1, end)

print(binary_search(array, target, 0, len(array) - 1))

피보나치 수열 - 바텀업

n = 10

dp = [0] * n

dp[1], dp[2] = 1, 1

for i in range(3, n):
    dp[i] = dp[i - 1] + dp[i - 2]

print(dp)

다이나믹 프로그래밍 예시

개미 전사

개미 전사는 메 뚜기 마을의 식량창고를 몰래 공격하려고 합니다.
메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있습니다.
이 때 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있습니다.
들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야합니다.

해결 아이디어

특정한 i 번째 식량창고를 털지 안 털지의 여부는 i-1, i-2 2가지 중 더 많은 식량을 털 수 있는 경우를 선택 

n = 4
store_list = [1 ,3 ,1 ,5]


dp = [0] * len(store_list)

dp[0] = store_list[0]
dp[1] = max(store_list[0],store_list[1])

for i in range(2,len(store_list)):
    dp[i] = max(dp[i-1],dp[i-2] + store_list[i])


print(dp)


1로 만들기

정수 x가 주어졌을 때 x가 5로 나누어 떨어지면 5로 나눕니다 x가 3로 나누어 떨어지면 3으로 나눕니다 x가 2로 나누어 떨어지면 2로 나눕니다 x에서 1을 뺍니다. 정수 x가 주어졌을 때, 연산 4개를 적절히 사용해서 1로 만들고자 합니다. 연산을 사용하는 횟수의 최솟값을 출력하세요

n = 26

dp = [0] * 30001

for i in range(2, n + 1):
    dp[i] = dp[i - 1] + 1
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i // 2] + 1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i // 3] + 1)
    if i % 5 == 0:
        dp[i] = min(dp[i], dp[i // 5] + 1)

print(dp[n])