[알고리즘] 다이나믹 프로그래밍(DP)

중복되는 연산을 줄이자

 

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

컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 잇는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다.

➡️ 연산 속도가 메모리 공간을 최대한으로 활용할 수 있는 효율적 알고리즘 작성의 필요성 ⬆️

 

어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다.

이는 다이나믹 프로그래밍 기법으로 동적 계획법이라고 표현하기도 한다.

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 피보나치 수열은 다음과 같은 형태로 끝없이 이어진다.

출처 : 이것이 코딩테스트이다. -나동빈 저

 

수학자들은 점화식을 사용해 수열의 항이 이어지는 형태를 간결하게 표현한다.
점화식이란 인접한 항들 사이의 관계식을 의미하는데, 피보나치 수열의 점화식은 다음과 같이 표현가능하다.

이러한 점화식은 인접 3항간 점화식이라고 부르는데, 인접한 총 3개의 항에 대해서 식의 정의되기 때문이다.

 

프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현할 수 있다. 수열 자체가 여러개의 수가 규칙에 따라서 배열된 형태를 의미하는 것이기 때문이다.

파이썬에서는 리스트 자료형이 이를 처리하고, C/C++와 자바에서는 배열을 이용해 이를 처리한다. 리스트나 배열 모두 '연속된 많은 데이터'를 처리한다는 점은 동일하다. (파이썬의 경우 기본 자료형인 리스트 자료형이 연결 리스트의 기능을 포함하고 있는 점이 다른 프로그래밍 언어에서의 배열과 차이점이다.)

 

수학적 점화식을 프로그래밍으로 표현하기 위해 재귀 함수를 사용한 코드는 다음과 같다.

# 피보나치 수열
def fibo(x):
    if x==1 or x==2:
        return 1
    return fibo(x-1) + fibo(x-2)

print(fibo(4))

그런데 피보나치 수열의 소스코드를 이렇게 작성하면 심각한 문제가 생길 수 있다. 바로 f(n) 함수에서 n이 커질 수록 수행 시가이 기하급수적으로 늘어나기 때문이다.
이 소스코드는 O(2^N)의 지수 시간이 소요된다고 표현할 수 있다. 

출처 : 이것이 코딩테스트이다. -나동빈 저

그림을 보면 f(6)을 호출했을때 동일한 함수가 반복적으로 호출되는것을 할 수 있다. 이미 한 번 계산했지만, 계속 호출할 때마다 계산하는 것이다. 그림에서 f(3)은 3번 호출되었다. 즉, f(n)에서 n이 커지면 커질수록 반복해서 호출하는 수가 많아진다.

이처럼 피보나치 수열의 점화식을 재귀함수를 이용해 만들 수는 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결 할 수 없다.

이 문제는 DP를 사용하면 효율적으로 해결이 가능하다.
다만 항상 다이나믹 프로그래밍을 사용할 수는 없으며, 다음조건을 만족할 때 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

피보나치 수열은 이런 조건을 만족하는 대표 문제이다. 이 문제를 메모이제이션 기법을 사용해서 해결할 수 있다.
메모이제이션은 DP를 구현하는 방법 중 한 종류로, 한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 메모이제이션은 값을 저장하는 방법이므로 캐싱이라고도 한다.

한번 구한 정보를 리스트에 저장하는 메모이제이션 기법을 이용한 피보나치 수열 소스코드는 다음과 같다.

# 피보나치 수열 (재귀적)

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

# 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
    # 종료 조건(1 혹은 2일때 1을 반환
    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))

 

 

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

 

퀵 정렬 또한 정렬할 리스트를 분할하며 전체적으로 정렬이 될 수 있도록 하는 분할 정복 알고리즘을 사용한다. 다이나믹 프로그래밍과 분할 정복의 차이점은 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다.
퀵 정렬은 이미 해결한 문제에 대해서 다시 처리하는 부분은 존재하지 않는다. 반면에 다이나믹 프로그래밍은 한번 해결했던 문제를 다시금 해결한다는 점이 특징이다. f(6) 해법을 다시 메모이제이션 기법을 이용하여 그려보면 6번째 피보나치 수를 호출할 때는 다음 그림처럼 색칠된 노드만 방문하게 된다. 

출처 : 이것이 코딩테스트이다. -나동빈 저

물론 재귀함수를 사용하면 컴퓨터 시스템에서는 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생할 수 있다. 따라서 재귀 함수 대신에 반복문을 사용하여 오버헤드를 줄일 수 있다. 일반적으로 반복문을 이용한 다이나믹 프로그래밍이 더 성능이 좋기 때문이다.

# 피보나치 수열(반복적)

#앞서 계싼된 결과를 저장하기 위한 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])

 

이처럼 재귀함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운(Top-Down)방식이라고 말한다.
반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 바텀업(Bottom-Up)방식이라고 말한다.

탑다운(메모이제이션) 방식은 '하향식'이라고도 하며, 바텀업 방식은 '상향식'이라고 한다. 
다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식이다. 바텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블'이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.

다이나믹 프로그래밍과 메모이제이션의 개념을 혼용해서 사용하는 경우도 있는데, 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하므로, 다이나믹 프로그래밍과는 별도의 개념이다. 

 

앞서, 수열은 배열이나 리스트로 표현할 수 있다고 했는데, 메모이제이션은 때에 따라서 다른 자료형, 예를 들어 사전(dict) 자료형을 이용할 수도 있다. 사전자료형은 수열처럼 연속적이지 않은 경우에 유용한데, 예를 들어 An을 계산하고자 할때 A0~An-1 모두가 아닌 일부의 작은 문제에 대한 해답만 필요할 경우가 존재할 수 있다. 이럴 때에는 사전 자료형을 이용하는것이 더욱 효과적이다.

코테에서 다이나믹 프로그래밍 문제는 3차원 리스트를 이용할만큼 어려운 난이도는 나오지 않는다고 한다. 대체로 간단한 형태로 출제되는편이다.
특정한 문제를 완전 탐색 알고리즘으로 접근했을때 시간이 매우 오래걸리면 다이나믹 프로그래밍을 적용할 수 있는지, 해결하고자 하는 부분 문제들의 중복여부를 확인해보자. 
가능한 재귀함수를 이용하는 탑다운 방식보다는 바텀업 방식으로 구현하는 것을 권장한다고 한다. 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문이다.

실제로 앞에서 재귀적인 피보나치 수열의 소스코드에서 5000번째 이상의 큰 피보나치 수를 구하도록 하면 'recursion depth'에 관한 오류가 발생될 수 있다. 이럴 경우 sys 라이브러리에 포함되어 있는 setrecursionlimit()함수를 호출하여 재귀 제한을 완화할 수 있다는 점을 기억하자.

 

---

실전문제

 

정답👇🏻👇🏻👇🏻(더보기를 눌러주세용)

#1로 만들기

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

#정수 n 입력받기
n = int(input())

#다이나믹 프로그래밍 진행(바텀업)
for i in range(2,n+1):
    #현재의 수에서 1을 빼는 경우
    arr[i] = arr[i-1]+1
    #현재의 수가 2로 나누어떨어지는 경우
    if i % 2 ==0:
        arr[i] = min(arr[i], arr[i//2]+1)
    #현재의 수가 3으로 나누어 떨어지는 경우
    if i % 3 ==0:
        arr[i] = min(arr[i], arr[i//3]+1)
    #현재의 수가 5로 나누어 떨어지는 경우
    if i % 5 ==0:
        arr[i] = min(arr[i], arr[i//5]+1)

print(arr[n])

 

 

 

 

정답👇🏻👇🏻👇🏻(더보기를 눌러주세용)

# 개미 전사 (전 dp가 너무 어려워요ㅠㅠㅠㅠ 이것도 점화식보고 풀었어요ㅠㅠㅠ)

n = int(input())
arr = list(map(int, input().split()))

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

# DP 진행(바텀업)
d[0] = arr[0]
d[1] = max(arr[0],arr[1])

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

print(d[n-1])

하.. 정말 나는 DP가 진짜 세상 제일 어려운것 같다. 일단 배열 길이에 대해서 감도 안잡히고, 점화식 또한 생각나지 않는다.
이걸 어떻게 코드로 구현하여 풀지...? 라는 생각이 온 머리를 둘러싸는것 같다.

솔직히 이 문제가 어려운 문제는 아니지만ㅠㅠ 문제풀이 발상부터 막히니, 코드로 짜는것이 어려운것 같다! 

위와 같은 문제풀이 솔루션을 읽고 위의 코드를 작성했다. 점화식이 나와있으니, 그래도 코드는 작성할 수 있었지만. 저 하이라이트 표시된 부분이 발상이 되야하는데, 그 과정이 제대로 이루어지고 있질 않는다.ㅠㅠ 답답하지만 연습하다보면 늘겠지!!!

 

 

 

 

정답👇🏻👇🏻👇🏻(더보기를 눌러주세용)

# 바닥 공사(이것도 점화식 보고 풀었어요..ㅠ)

n = int(input())

d =[0] * 1001

# dp진행(바텀업)
d[1] = 1
d[2] = 3
for i in range(3, n+1): #3부터 n까지
    d[i] = (d[i-1] + d[i-2]*2) % 797796

print(d[n])

 

이 풀이는 이코테 책에서 알려준 풀이이다. 이렇게 그림으로 보고 맨 마지막일때부터 상황을 보는것이 점화식을 세우는데 도움이 되는것 같다.

 

 

 

 

정답👇🏻👇🏻👇🏻(더보기를 눌러주세용)

# 효율적인 화폐 구성

n, m = map(int, input().split())

#캐시 생성
d = [10001] * m+1
d[0] = 0

arr=[]
for i in range(n):
    arr.append(int(input())) #arr에 단위 화폐 저장


#dp 진행(바텀업)
for i in range(n):
    for j in range(arr[i], m+1):
        if d[j-arr[i]] != 10001: #i-k원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j-arr[i]] + 1)

if d[m] == 10001: #m원을 만다는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

 

하ㅏ....! 어렵다! 

이건 이코테 책에 나온 문제 풀이방법인데, 일단 화폐단위 대로 반복문을 돌려야한다는 사실은 파악했었다! 그리고 캐시에서 각 인덱스를 금액으로 설정하여 진행해야겠다는 생각도 할 수 있었다. 하지만 결국 내가 또 중간에 막힌 이유는,,,

좀 더 구체적인 구현을 해내지 못했다. 예를 들어 a5의 경우, 5-3을 하면 2인데, 이렇게 5에서 3을 빼고, 5에서 2를 빼고 이런식의 구상을 하지 못했다. 너무 아쉽다.

 

나는 정말 DP가 아직 어려운것 같다. 그 구상을 하고 구현해낼 수 있는 능력이 있어야하는데, 아직까지는 구상하는 능력도 부족한것 같고 구현하는 능력도 부족한것 같다.

DP에 관련된 여러문제를 풀며, 앞으로 조금 더 고민해보고 익숙해질 수 있는 시간을 가졌으면 좋겠다.ㅠㅠ

 

% 해당 글은 "이것이 코딩테스트다. (나동빈 저)" 를 공부하며 정리해놓은 게시글입니다!