[Algorithm] 동적계획법(DP: Dynamic Programming)

bee·2023년 4월 25일
DPalgorithmdynamic programmingpython다이나믹프로그래밍동적계획법이코테
0

Algorithm

목록 보기
5/8
post-thumbnail

들어가기에 앞서,

🤔 컴퓨터를 활용해도 해결하기 어려운 문제?

컴퓨터를 활용해도 해결하기 어려운 문제에는 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 있다.

다만, 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다.
우리는 이 방법을 '다이나믹 프로그래밍' 또는 '동적계획법'이라고 표현한다.


🤔 동적계획법의 '다이나믹' vs 동적할당의 '다이나믹'

프로그래밍에서 '다이나믹'은 프로그램이 실행되는 도중에라는 의미이다.
따라서 자료구조에서 동적할당(Dynamic Allocation)은,
프로그램이 실행되는 도중에 프로그램 실행에 필요한 메모리를 할당하는 기법을 뜻한다.


🤔 피보나치 수열

: 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열

피보나치 수열은 간단한 점화식을 사용하여 표현할 수 있다.
(** 점화식 : 인접한 항들 사이의 관계식)

an=an−1+an−2(n≥3),a1=a2=1a_n = a_{n-1}+a_{n-2} (n \geq 3), a_1 = a_2 = 1

일반적으로 피보나치 수열은 이런식으로 재귀함수를 사용해서 구현한다고 생각할 수 있다.

## 피보나치 수열 구현 - 재귀함수
def fibo(n):
	if n == 1 or n == 2:
    	return 1
        
    return fibo(n-1) + fibo(n-2)

하지만 재귀함수를 사용하는 방식은 시간복잡도 O(2N)O(2^N)이 소요되어 수행 시간이 기하급수적으로 증가하게 된다. f(n)f(n)을 'n번째 피보나치 수'라 할 때, f(6)f(6)을 계산하기 위해서 f(3)f(3)이 3번이나 호출된다.

즉, 이미 한 번 계산했지만, 호출할 때마다 계산해야 하기 때문에, f(n)f(n)에서 nn이 커질수록 반복해서 호출하는 수가 많아진다.

이 때, 동적계획법을 사용해서 효율적으로 계산할 수 있다.







동적계획법 (Dynamic Programming)

개념

: 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법

  • 이미 한 번 풀었던 부분 문제를 저장해두어 공간복잡도를 늘리는 대신, 시간복잡도는 줄일 수 있음

사용 조건

1. 최적 부분 구조 (Optimal Substructure)
→ 큰 문제를 작은 문제로 나눌 수 있다.

2. 중복 부분 문제 (Overlapping Subproblems)
→ 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.


동적 계획 vs 분할 정복

분류동적 계획(Dynamic Programming)분할 정복(Divide and Conquer)
차이점- 문제들이 서로 영향을 미친다- 문제들이 중복되지 않고 각각 독립적이다
동작 원리한 번 해결했던 문제에 대한 답을 리스트에 저장해두고,
이 문제는 이미 해결된 것이니까
다시 해결할 필요가 없다는 뜻으로 저장한 값을 반환한다.		한 번 피벗이 자리를 바꿔 위치하게 되면,
피벗의 위치는 더 이상 바뀌지 않으며
피벗값을 다시 처리하는 부분 문제는 존재하지 않는다





동적 계획법 구현 방법

1. Memoization (Top-Down 방식)

개념

: dp[0]의 기저 상태(작은 부분)에서 출발하는게 아니라, 최종 결괏값dp[n]를 구하기 위해 위에서부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음, 해당 결과를 재귀함수를 통해 전이시켜 다시 사용하는 기법


  • 다른 말로 '캐싱(Caching)'
    (※ 캐시(Cache) : 재사용 할 값들을 저장해놓는 메모리 공간)

  • 장점 : 위에서부터 계산하기 때문에 필요없는 계산은 안해도 됨

  • 단점 : 재귀함수를 사용하기 때문에, 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드(Overhead)가 발생할 수 있음
    (※ 오버헤드(Overhead) : 어떤 처리를 하기위해 소요되는 간접적인 처리 시간, 메모리 등)


소스코드

## 피보나치 수열 예제 활용

dp = [0] * 100 # 한 번 계산된 결과를 저장하기 위한 리스트(0으로 초기화)

def fibo(n):
	# 종료조건
    if n == 1 or n == 2:
    	return 1
        
    # 이미 계산한 적 있는 문제라면 결과값 그대로 반환
    if dp[n] != 0:
    	return dp[n] # 위에서부터 호출
    
    # 아직 계산하지 않은 문제라면 결과값을 재귀적으로 전이시켜 재활용
    dp[n] = fibo(n-1) + fibo(n-2)
    return dp[n]

→ 218922995834555169026





2. Tabulation (Bottom-Up 방식)

개념

: 최종 결괏값 dp[n]을 구하기 위해 DP table(dp)에 n보다 작은 모든 값에 대하여 반복문으로 계산값을 저장한 후, dp[n]을 구하기 위해 필요한 값을 DP table에서 가져와 사용하는 기법
(※ DP table : 중간 계산값 저장용 리스트)

  • 장점 : 재귀함수 대신에 반복문을 사용하기 때문에 오버헤드를 줄일 수 있음
  • 단점 : 밑에서부터 모든 값을 계산해야 하기 때문에 필요 없는 값까지 계산해야 함
  • 시스템상 재귀함수의 스택 크기가 한정되어 있을 수 있기 때문에 Bottom-Up 방식으로 구현하는 것을 권장함

소스코드

## 피보나치 수열 예제 활용

dp = [0] * 100 # 앞서 게산된 결과를 저장하기 위한 DP table(0으로 초기화)

d[1], d[2] = 1, 1
n = 99

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

→ 218922995834555169026







실습

실전문제 1. 1로 만들기

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다.

(a) X가 5로 나누어떨어지면, 5로 나눈다.
(b) X가 3로 나누어떨어지면, 3로 나눈다.
(c) X가 2로 나누어떨어지면, 2로 나눈다.
(d) X에서 1을 뺀다.

정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 최소 횟수를 출력하는 프로그램을 작성하시오.
(단, 1≤X≤300001 \leq X \leq 30000)

## 내 풀이
x = int(input())

cnt = 0

while x != 1:
    
    # 연산 (a)
    if x % 5 == 0:
        x //= 5
        cnt += 1
        
    # 연산 (b)
    elif x % 3 == 0:
        x //= 3
        cnt += 1

    # 연산 (c)
    elif x % 2 == 0:
        x //= 2
        cnt += 1
    
    # 연산 (d)
    else:
        x -= 1
        cnt += 1
        
print(cnt)

26

5



내 풀이는 동적계획법이 아니라 그리디 알고리즘을 이용한 풀이라고 할 수 있다.
그리디 알고리즘은 내가 생각한 처음 최적의 방법이 끝까지 반례없이 적용되는 것이고, 동적계획법은 가능성을 모두 열어두고 그 안에서 최적의 결괏값을 찾는 것이므로 엄연히 다르다.

내 풀이에서는 while문을 활용하여 결괏값이 1이 될 때 까지, 가장 큰 수인 5부터 3, 2까지 차례대로 나누는 방식으로 코드를 작성했다.
입력값 x가 26이라면, 연산 (c)→(d)→(b)→(c)→(c)로 정답은 5가 나온다.

하지만, 처음부터 1을 빼고 5 또는 3 또는 2로 나눈 결괏값 중 최솟값을 DP table에 저장하는 방식으로 반복하면 전혀 다르 답이 나온다.
같은 입력값을 넣었을 때 동적계획법을 사용하면, 연산 (d)→(a)→(a)로 정답은 3이 나온다.

모범답안을 살펴보자.

## 모범답안
x = int(input())

d = [0] * 30001 # DP 테이블(앞에 계산된 결과를 저장) 0으로 초기화

# 2부터 시작하는 이유는 결괏값이 1이 될 때까지(d[1]일 때까지) 반복해야 하기 때문
for i in range(2, x+1) :
    
    # 연산 (d)
    # 조건문이 아닌 처음부터 1을 빼고 시작하는 이유:
    # 아래 연산 (a),(b),(c)의 결괏값에 따라 d[i]가 교체되기 때문
    # 구하고자 하는 d[i]는 계산한 값이 아니라 계산 횟수를 저장하는 것이기 때문에 1을 더함
    d[i] = d[i-1] + 1
    
    # 연산(c)
    if i % 2 == 0:
    	# min함수 첫번째 항목은 연산 (d)에서 이미 1을 더해준 값이기 때문에 두번째 항목에만 1을 더함
        d[i] = min(d[i], d[i//2] + 1)
        
    # 연산(b)
    if i % 3 == 0:
        d[i] = min(d[i], d[i//3] + 1)
        
    # 연산(a)
    if i % 5 == 0:
        d[i] = min(d[i], d[i//5] + 1)

print(d[x])

26

3




📌 위 문제의 점화식을 세워보면 아래와 같다.

ai=min(ai−1,ai/2,ai/3,ai/5)+1a_i = min(a_{i-1}, a_{i/2}, a_{i/3}, a_{i/5})+1

📌 DP table d 생성 및 초기화 시, 30000이 아닌, 30001을 곱해준 이유?

첫번째 수는 d[1]이 아니고 d[2]이기 때문에 d[1]을 첫번째 수인 것 처럼 만들어준다.


📌 if ~ elif ~ else문이 아닌 if ~ if ~ if를 사용한 이유?

그리디 알고리즘과 달리, 정해진 최선의 연산 방법이 없기 때문에 연산 (a), (b), (c), (d)를 전부 다 시도해봐야 한다.







실전문제 2. 개미전사

메뚜기 마을에는 여러 개의 일직선으로 이어진 식량창고가 있으며, 각 식량창고에는 정해진 수의 식량을 저장하고 있다. 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오.

## 내 풀이
n = int(input())
k_list = list(map(int, input().split())

d = [0] * 101

d[0] = k_list[0]
d[1] = max(array[0], array[1])

for i in range(2, n):
	d[i] = max(d[i-1], d[i-2] + k_list[i]) # k_list[i]: i번째 식량창고에 있는 식량의 양
    
print(d[n-1])

4
1 3 1 5

8







실전문제 3. 바닥 공사

가로 길이 N, 세로 길이 2인 직사각형 형태의 얇은 바닥이 있다. 바닥을 1x2, 2x1, 2x2인 덮개를 이용해 채우고자 한다. 바닥의 가로 길이 N이 주어질 때, 덮개로 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오.
(출력조건 : 2xN 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.)

## 내 풀이
n = int(input())

d = [0] * 1001

d[1] = 1
d[2] = 3

for i in range(3, n+1):
	d[i] = (d[i-1] + d[i-2] * 2) % 796796

print(d[i])

3

5







실전문제 4. 효율적인 화폐 구성

N가지 종류의 화폐가 있을 떄, 이 화폐들의 개수를 최소한으로 이용해서 합이 M원이 되도록 하려고 한다. 각 화폐를 사용할 수 있는 개수는 제한이 없으며, 사용한 화폐의 구성은 같지만 순서만 다르것은 같은 경우로 구분한다. 예를 들어 2원 3원 단위의 화폐가 있을 때, 15원을 만들기 위해 3원 5개를 사용하는 것이 가장 최소한의 화폐 개수이다. N가지 종류의 화폐가 있을 때, M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하시오. (단, M원을 만들 수 없는 경우 -1을 출력한다.)

## 내 풀이
n, m = map(int, input().split())
money = [int(input()) for _ in range(n)]

d = [10001] * (m+1)
d[0] = 0

for i in range(n):
	for j in range(money[i], m+1):
    	if d[j - money[i]] != 10001: # (i-k)원을 만드는 방법이 존재하는 경우
        	d[j] = min(d[j], d[j-money[i]] + 1)
            
# 결과 출력
if d[m] == 10001: # M원을 만드는 방법이 없는 경우
	print(-1)
else:
	print(d[m])






🔗 References

profile
bee
벌집처럼 밀도있게 차곡차곡 쌓아나가는중
이전 포스트

[인프런] 파이썬 알고리즘 문제풀이 입문 - 이분탐색 & 그리디 (수정중)

다음 포스트

[Algorithm] 깊이 우선 탐색(DFS)/너비 우선 탐색(BFS)

0개의 댓글