동적계획법 - DP (Dynamic Programming)

DP 

다이나믹 프로그래밍은 다음 조건을 만족할 때 사용할 수 있다.

1. 최적 부분 구조(Optimal Substructure): 큰 문제를 작은 문제로 나눌 수 있다.
2. 중복되는 부분 문제(Overlapping Subproblem): 동일한 작은 문제를 반복적으로 해결한다.

 

DP 예시

대표적인 문제로는 피보나치 수열이 있다.

(cf. 점화식: 인접항들의 관계식을 의미한다.)

// 피보나치 수열
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...

 

 

* 피보나치 수열의 점화식

 

 

단순 재귀를 통한 피보나치 수열 구현

* [Python] 단순 재귀를 통한 피보나치 수열

# 피보나치 함수를 재귀함수로 구현
def fibo(x):
	if x == 1 or x == 2:
    	return 1
    return fibo(x-1) + fibo(x-2)
    
print(fibo(4))  # 3

 

단순 재귀함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가지게 된다.

아래 이미지와 같이 f(2)가 중복 호출되는 문제가 발생한다.

(cf. 빅오표기법 기준으로 f(30)을 계산하기 위해 약 10억 가량 연산을 수행해야한다.)

 

 

메모이제이션(Memoization) - 하향식(Top Down) 방식

• 메모이제이션은 DP를 구현하는 방법 중 하나이다.
• 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다.
  • 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
  • 값을 기록해놓는다는 점에서 캐싱(Caching)이라고도 한다.

 [Python] Top-Down DP

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0] * 100

# 피보나치 함수를 재귀함수로 구현(탑다운 DP)
def fibo(x):
	# 종료 조건
    if x == 1 or x == 2:
    	return 1
    # 이미 계산한 적 있는 문제라면 그대로 반환
    if d[x] != 0:
    	return d[x]
    # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]
    
print(fibo(99))  # 218922995834555169026

 

[Python] Bottom-UP DP

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 첫번째 피보나치 수와 두번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수 반복문으로 구현(바텀업 다이나믹 프로그래밍)
for i in range(3, n+1):
	d[i] = d[i-1] + d[i-2]
    
print(d[n])  # 218922995834555169026

 

DP vs 분할정복

• DP와 분할정복은 모두 최적 부분 구조를 가질 때 사용할 수 있다.
  • 즉, 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황

• DP와 분할정복의 차이점은 부분 문제의 중복이다.
  • DP 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다.
  • 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.

 

DP 문제 접근방법

• 주어진 문제가 DP 유형임을  파악하는 것이 중요하다.
• 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토할 수 있다.
  • 다른 알고리즘으로 풀이방법이 떠오르지 않는다면 DP를 고려해보자.
• 일단 재귀함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 코드를 개선하는 방법을 사용할 수 있다.
• 일반적인 코테 수준에서는 기본 유형의 DP 문제가 출제되는 경우가 많다.

 

DP 구현 예시

개미전사: 문제설명 (이코테 2021 ch 6. DP 문제 예시)

개미전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져있다.

각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다.

이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다.

따라서 개미전사가 정찰병에게 들키지않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야한다. 

 

개미전사: 문제해결 아이디어

• 예시를 확인해 보자. N = 4일때, 다음과 같은 경우들이 존재할 수 있다.
  • 식량을 선택할 수 있는 경우의 수는 다음과 같이 8가지다.
  • 7번째 경우에서 8만큼의 식량을 얻을 수 있으므로 최적의 해는 8이다.

 

 

 

 

[Python] 답안예시

import sys

input = sys.stdin.readline
# 정수 N을 입력받기
n = int(input())
# 모든 식량 정보 입력받기
array = list(map(int, input().split()))

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# DP 진행(바텀업)
d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2, n):
	d[i] = max(d[i-1], d[i-2] + array[i])
    
# 계산된 결과 출력
print(d[n-1])