동적계획법
이번 포스팅은 자료구조의 동적계획법을 정리해보겠습니다.
동적계획법
동적계획법이란?
다이나믹 프로그래밍(Dynamic Programming, DP)라고도 불리며, 문제의 최적해를 구하거나 답의 개수를 세는 과정에 사용할 수 있는 알고리즘 설계 기법입니다. 동적계획법을 사용하면 불필요한 계산을 줄이고, 효율적으로 최적해를 찾을 수 있습니다.
전체 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용해 전체 문제를 해결하는 방식이라고 볼 수 있습니다. 쉽게 얘기하면 동적계획법은 규칙을 찾는 문제라 할 수 있습니다.
점화식
수열에서 n번째 항을 이전에 나온 항들로 나타낸 공식
점화식 예시
문제에 따라서 규칙은 n이라는 하나의 변수에 관한 규칙일 수도, n, m 두개의 변수에 관한 규칙 혹은 그 이상일 수도 있습니다.
동적계획법 접근방법
- 작은 문제에서 큰 문제로 반복문 호출 => Bottom Up 방법
- 큰 문제에서 작은 문제로 재귀 호출 => Top Down 방법
피보나치 수열 - Bottom Up
피보나치 수열을 Bottom Up 방식의 코드로 구현해 보겠습니다.
위와 같이 리스트에 처음에 n=0번째와 n=1번째값을 1로 넣습니다. n=2번째 부터는 반복문을 통해 이전 2개의 값을 더하여 넣는것을 반복하고 구하고자 하는 n에 도착하였을때 배열의 가장 마지막 값을 반환 합니다.
def fib(n):
fibList = [1, 1]
for i in range(2, n+1):
fibList.append(fibList[i-2]+fibList[i-1])
return fibList[-1] # 동작이 끝난 후에 배열의 가장 마지막 값을 반환
print(fib(4))
5
피보나치 수열 - Top Down
피보나치 수열을 Top Down 방식의 코드로 구현해 보겠습니다.
구하고자 하는 피보나이츼 수열 n번째 값을 구하기 위해선 이전 2개의 값이 필요하고 이 2개의 값을 구하기 위해선 또 이전의 2개의 값 총 4개의 값이 필요합니다. 이렇게 반복하면 가장 끝의 2개의 값은 n=0 일떄와 n=1일때인 1의 값의 결합으로 구할 수 있게 되는 것 입니다.
def fib(n):
if n==0 or n==1:
return 1
else:
return fib(n-1) + fib(n-2)
print(fib(4))
5
하지만 Top Down 방식을 수행 할때 문제가 하나 있습니다. 피보나치 수열의 값 하나를 구하기 위하여 많은 계산일 필요하고 계산이 중복 되는 일이 발생합니다.
이를 해결하기 위해 메모이제이션(Memoization)이 필요 합니다.
메모이제이션(Memoization)
메모이제이션이란? 앞에서 했던 계산을 어딘가에 저장하고 필요한 경우 불러와서 활용 할 수 있게 하여 중복된 계산을 방지하는 방법입니다. 코드로 구현하면 아래와 같습니다.
memo = {0:1, 1:1} # 메모이제이션 을 활용할 딕셔너리
def fib(n):
if n in memo: # 메모이제이션에 값이 저장되어 있다면
return memo[n] # 저장되어 있는 값을 불러오고
else: # 저장되어 있지 않다면
result = fib(n-1) + fib(n-2) # 재귀함수를 활용하여 값을 찾음
memo[n] = result # 찾은 값은 딕셔너리에 저장하고
return result # 그 값을 반환
print(fib(4))
5
위와 같이 메모이제이션은 배열 혹은 해시를 활용하는 것이 핵심 입니다.
동적계획법 예시
data = [3, 4, 5, 6, 1, 2, 5]
이웃하지 않는 숫자들의 합의 최댓값은?
이를 찾기 위해선 가능한 모든 경우의 수를 탐색하는 완전탐색을 해야 하지만 이 문제에 대한 규칙을 찾아 봅시다.
만일 data = [3, 4, 5, 6, 1, 2, 5] 가 아닌 data = [3]만 가지고 있다고 한다면?
최댓값은 3 임으로 n=0 일때 3이라 할 수 있습니다.
여기서 4가 추가 되어 data = [3, 4]라고 한다면?
합의 최댓값은 바로 이전의 값 3과 현재의 값 4중 최대 값의 합이 합의 최댓값 임으로 n=1 일때 4라 할 수 있습니다.
여기서 5가 추가 되어 data = [3, 4, 5]라고 한다면?
바로 이전의 값 4와 현재의 값 5와 5와 이웃하지 않은 3과의 합 3+5 = 8 중 큰 값이 최대 값 임으로 n=2 일때 8이라 할 수 있습니다.
여기서 6이 추가 되어 data = [3, 4, 5, 6]라고 한다면?
바로 이전의 값 8과 현재의 값 6과 6과 이웃하지 않은 전전 합의 최댓값 4의 합 4+6 = 10 중 큰 값이 최대 값 임으로 n=3 일때 10이라 할 수 있습니다.
여기서 1이 추가 되어 data = [3, 4, 5, 6, 1]라고 한다면?
바로 이전의 값 10과 현재의 값 1과 1과 이웃하지 않은 전전 합의 최댓값 8의 합 1+8 = 9 중 큰 값이 최대 값 임으로 n=4 일때 10이라 할 수 있습니다.
여기서 2가 추가 되어 data = [3, 4, 5, 6, 1, 2]라고 한다면?
바로 이전의 값 10과 현재의 값 2과 2과 이웃하지 않은 전전 합의 최댓값 10의 합 2+10 = 12 중 큰 값이 최대 값 임으로 n=5 일때 12라 할 수 있습니다.
마지막으로 5가 추가 되어 data = [3, 4, 5, 6, 1, 2, 5]라고 한다면?
바로 이전의 값 12와 현재의 값 5와 5와 이웃하지 않은 전전 합의 최댓값 10의 합 5+10 = 15 중 큰 값이 최대 값 임으로 n=6 일때 15라 할 수 있습니다.
위의 data를 아래와 같이 표기 할때
각 자리수에 대한 결과를 S로 표기 한다면 (예: n=4 의 결과 S₄) 결과는 다음과 같은 식으로 표현 가능 합니다.
위를 코드로 구현하면 아래와 같습니다.
def solution(data):
if len(data) == 1: # 입력된 배열의 크기가 1이라면 첫번째 원소가 최대 값
return data[0]
# 크기가 2일 경우
result = [data[0], max(data[0], data[1])] # 리스트의 첫번째 결과는 첫번째 원소가 최대 값, 두번째 결과는 첫번쨰 원소와 두번째 원소중 큰 값
# 크기가 3이상 일 경우
for i in range(2, len(data)):
result.append(max(result[i-1], result[i-2] + data[i])) # 이전의 최대 값과 전전의 최대 값 + 현재값 중 큰 값
return result[-1] # 마지막 벼열에 저장 된 값이 배열의 최대 값
print(solution([3, 4, 5, 6, 1, 2, 5]))
15