[코딩테스트] 다이나믹 프로그래밍

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

메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법.

이미 계산된 결과는 별도의 메모리 영역에 저장해두었다가, 나중에 해당 결과가 필요할 때 메모리 영역에 기록되어 있는 정보를 그대로 사용하고, 다시 계산하지 않도록 한다.

한 번 해결한 문제는 다시 계산하지 않으므로, 완전탐색을 이용했을 때 비효율적인 시간복잡도를 가진다 하더라도 다이나믹 프로그래밍으로 시간 복잡도를 줄일 수 있다.

일반적으로 Top-down(하향식) or Bottom-up(상향식) 두 가지 방식으로 구성하여 구현한다.

 

다이나믹 프로그래밍은 동적 계획법이라고 부른다.

자료구조에서 동적 할당(Dynamic Allocation) : 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법.

다이나믹 프로그래밍 : 별다른 의미 없음.

 

다음 조건을 만족하는 문제에서 사용할 수 있다.

1. 최적 부분 구조(Optimal substructure) : 큰 문제를 작은 문제로 나눈 후, 작은 문제의 답을 모으면 큰 문제 해결 가능.

2. 중복되는 부분 문제(Overlapping subproblem) : 동일한 작은 문제를 반복적으로 해결해야 문제가 해결될 때

 

대표적인 예시 : 피보나치 수열 문제.

1,1,2,3,5,8,13....

앞의 두 수를 더했을 때 해당 피보나치 수가 된다는 특징을 가지고 있다.

 

점화식 = 인접한 항들 사이의 관계식.

피보나치 수열의 점화식은 다음과 같다.

시작 부분 항의 값들을 알고 있다면, n이 얼마나 큰 수이든 결과적으로 모든 피보나치 수의 값을 구할 수 있다.

실제 프로그래밍에서 재귀함수를 이용해서 점화식을 소스코드로 그대로 구현할 수 있고, 이러한 수열(sequence)을 배열이나 리스트를 이용해서 표현할 수 있다.

파이썬 코드로 구현

#재귀함수로 구현한 Fibonacci function
def fibo(x):
	if x==1 or x==2:
    	return 1
    return fibo(x-1)+fibo(x-2)
    
print(fibo(4))

이렇게 단순 재귀 함수는 x==1이나 2가 아닐 때, fibo함수를 계속 재수행하기 때문에 이미 계산한 부분이 중복으로 호출되어 '지수'시간 복잡도O(2ⁿ)를 가진다.

f(30)을 계산하려면 2의 10제곱인 1024를 3번 곱해 약 10억번의 연산을 해야 한다. 숫자가 더 커지면 너무나 오랜 시간이 걸린다.

큰 문제를 작은 문제로 나누고, 동일한 작은 문제를 반복적으로 해결하는지 (=다이나믹 프로그래밍의 사용 조건을 충족하는지) 확인해보니 이를 충족한다.

 

메모이제이션 Memoization

다이나믹 프로그래밍을 구현하는 대표적인 방법. 한 번 계산한 결과를 메모리 공간에 메모했다가, 같은 문제를 다시 호출하면 메모를 그대로 가져온다. 값을 기록해놓는 거라 캐싱 Caching이라고도 한다.

Cach, D, DP 등의 변수명을 사용한다.

메모이제이션은 한 번 구해진 결과를 담아놓는 걸 의미하므로, 다이나믹 프로그래밍에 국한된 개념은 아니다.

 

탑다운 vs 보텀업

탑다운(메모이제이션)방식 = 하향식

보텀업 = 상향식. 전형적인 다이나믹프로그래밍의 형태.

결과 저장용 리스트는 DP 테이블이라고 부른다.

 

#탑다운 메모이제이션 다이나믹 프로그래밍 : 재귀함수
d=[0]*100

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(6))
# 실행 결과 : f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)


#보텀업 다이나믹 프로그래밍 : 재귀함수가 아니라 반복문을 사용한다.
d=[0]*100

#종료조건 대신에 시작항의 값을 각각 수행한다.
d[1]=1
d[2]=1
n=99

#반복문을 이용해서 점화식을 구현하여, 작은 문제를 먼저 풀고, 그걸 조합해서 풀어나간다.
for i in range(3, n+1):
	d[i] = d[i-1] + d[i-2]

이렇게 구현한 피보나치수열의 시간 복잡도는 O(N), 선형 시간 복잡도를 가진다.

 

다이나믹 프로그래밍 vs 분할 정복

둘 다 최적 부분 구조(큰 문제를 작은 문제로 나누고, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황)를 가질 때 사용할 수 있다.

 

하지만 다이나믹 프로그래밍은 각 부분의 문제들이 서로 영향을 미치고, 부분 문제가 중복되는 반면

분할 정복 문제에서는 한 번 계산한 문제를 반복적으로 다시 계산하지 않는다.(분할 정복의 대표적인 예시인 퀵 정렬에서 pivot 값이 한 번 자리를 잡으면, 그 피벗은 바뀌지 않는다. 즉, 해당 부분을 다시 처리하지는 않는다.)

 

 

DP 문제 접근법

1. 그리디나 구현, 완전탐색 등 다른 알고리즘으로 풀이 방법을 생각해보고, 너무 시간이 오래걸리면 다이나믹 프로그래밍으로 접근하자.

2. 우선 비효율적인 완전탐색프로그램을 재귀함수로 작성 후, 코드를 개선한다.

3. 점화식은 지나치게 어려워질 수 있기 때문에, 일반적으로는 기본 유형, 많이 출제되는 유형으로 출제된다.

 

문제1. 개미 전사

개미 전사가 일직선으로 이어진 메뚜기 식량창고를 몰래 공격하려 한다.

서로 인접한 식량창고를 공격하면 바로 들키기 때문에, 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.

N개의 식량창고, 각 식량창고에 저장된 식량의 개수 K가 주어졌을 때, 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하라.

풀이

왼쪽부터 차례대로 식량창고를 턴다고 가정하고, 특정 i번째 식량창고에 대해서 공격의 여부를 결정하면,

아래 둘 중에서 더 많은 식량을 얻을 수 있는 경우를 선택하면 된다.

 

1. i-1번째까지의 식량창고를 공격했을 때 얻을 수 있는 최대 식량

2. i-2번째까지의 식량창고를 공격했을 때 얻을 수 있는 최대 식량+i번째 식량창고의 K

 

i-3은 이미 앞쪽에서 고려되었으므로 고려할 필요가 없다.

코드

#정수 n과 모든 식량 k정보 입력받기
n=int(input())
k=list(map(int,input().split()))

d=[0]*100 #i번째 창고까지의 최대 획득 가능 식량 담을 DP 테이블 초기화

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

 

 

 

문제 2. 1로 만들기

정수 X가 주어졌을 때, 아래 4개의 연산을 최소 횟수로 사용해서 값을 1로 만들고자 한다.

1. X가 5로 나누어 떨어지면 5로 나누기

2. X가 3으로 나누어 떨어지면 3으로 나누기

3. X가 2로 나누어 떨어지면 2로 나누기

4. X에서 1을 빼기

 

풀이

단순히 1-2-3-4 순으로 하면 되는 것처럼 보이지만, 그렇게 풀면 최적의 값을 찾을 수 없다. 4가지 방법 중에서 하나를 골라야 한다. 

i를 1로 만들기 위한 최소 연산 횟수를 aᵢ라고 하면, 1을 빼는 연산을 제외하고는 해당 수로 나누어 떨어질 때에 한해 점화식을 적용할 수 있다.

코드

x=int(input())

d=[0]*30001 #최대 x값을 기록

for i in range(2,x+1):
	d[i] = d[i-1] +1 #현재의 수에서 1을 빼는 경우를 먼저 담고
    if i%2 ==0 :
    	d[i] = min(d[i],d[i//2]+1) #위에서 구한 d[i]와 비교
    if i%3 ==0 :
    	d[i] = min(d[i],d[i//3]+1) #위에서 구한 d[i]와 비교
    if i%5 ==0 :
    	d[i] = min(d[i],d[i//5]+1) #위에서 구한 d[i]와 비교
print(d[x])

 

코딩테스트 준비하기

 

2023.01.25 - [Data Science] - [코딩테스트] 이진 탐색 알고리즘

2023.01.25 - [Data Science] - [코딩테스트] 정렬 알고리즘 비교 및 기초 예제

2023.01.24 - [Data Science] - [코딩테스트] 정렬 알고리즘(2) 퀵 정렬 계수 정렬

2023.01.24 - [Data Science] - [코딩테스트] 정렬 알고리즘(1) 선택 정렬과 삽입 정렬

2023.01.24 - [Data Science] - [코딩테스트] DFS BFS 문제 풀이 실습

2023.01.23 - [Data Science] - [코딩 테스트] DFS BFS 개념 - 스택 큐 자료구조 재귀함수 기초

2022.12.24 - [Data Science] - [코딩테스트] 구현, 시뮬레이션과 완전 탐색

2022.12.23 - [Data Science] - [코딩테스트] 그리디 알고리즘(Greedy), 탐욕법

 
 
https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC *내용에 대한 모든 저작권은 해당 영상의 원저작자에게 있습니다.