[알고리즘] 동적 계획법 (Dynamic Programming) 코딩테스트 대비 정리

알고리즘 문제를 풀던 중 동적계획법 풀이 방법 정리가 필요함을 느껴

동빈나님의 이코테 강의를 보고 제 생각을 더해 정리해 보았습니다.

 

풀이 언어는 파이썬을 사용했습니다.

목차

• 동적 계획법 개념
• 대표 풀이 예시 : 피보나치 수열
• 문제 리뷰

동적 계획법(DP) 개념

동적 계획법

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

 

이미 계산한 것을 메모리에 저장하여 중복 계산을 막는다.

최소/최대 문제 등에서 자주 사용된다.

점화식을 구해야 하며 이 과정이 어렵지만 코드는 대체적으로 간단한 편이다.

 

동적 계획법의 조건

1. 최적 부분 구조 : 큰 문제를 작은 문제를 나눌 수 있어야 함

2. 중복되는 부분 문제 : 중복되는 문제를 테이블에 저장하여 다시 계산하지 않음

 

동적 계획법의 두 가지 방법

1. 상향식 (bottom-up) 방법 : 주로 반복문을 사용하여 구현

2. 하향식 (top-down)  : 주로 재귀함 수를 사용하여 구현

 

두 가지 방법 모두 사용 가능한 문제도 있고 둘 중 하나로만 풀이가 가능한 문제도 있습니다.

 

대표 풀이 예시 : 피보나치 수열

피보나치 수열의 점화식은 d[i] = d[i-1] + d[i-2] 다.

이 점화식을 이용하여 파이썬 코드로 피보나치 수열을 풀 수 있습니다.

 

1. 하향식 동적 계획법 풀이

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(99))

 

2. 상향식 동적 계획법 풀이

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]

print(d[n])

문제 리뷰

강의에서 나온 다섯 문제를 리뷰해 보겠습니다. 4가지 유형이 있는 것 같습니다.

문제 내용과 풀이는 적지 않았습니다. 문제는 강의를 참고 해야 합니다.

 

개미 문제, 최소합 문제

가장 일반적인 DP 문제 였습니다.

 

효율적인 화폐 구성 문제

DP 테이블을 모두 INF로 초기화 하고 풀이를 진행해야 합니다.

(INF는 infinite로 파이썬에선 그냥 매우 큰 정수 값으로 지정하면 됨)

 

금광 문제

2차원의 맵에서 경로를 찾는 문제 입니다.

리스트 범위를 체크하는 것을 유의해야 합니다.

dp 테이블을 따로 생성하지 않고, 초기 맵을 DP 테이블로 사용해도 됩니다.

 

가장 긴 증가하는 부분 순열(LIS) 문제

array : 주어진 숫자들

D : DP 테이블

D는 모두 1로 초기화 합니다. D가 가장 작은 경우는 자기 자신만 선택 됐을 경우이기 때문에 최솟값이 1입니다.

상향식 동적 계획법으로 D[i]를 채워나갑니다.

D[i]는 array[i] 보다 작은 모든 array[j] 중 D 값이 가장 큰 것을 선택합니다.

 

시간복잡도

이 문제를 부루트포스 알고리즘으로 풀면 O(2^N)의 시간이 걸립니다.

DP로 풀면 각 i마다 i-1번의 계산을 하기 때문에 O(N^2)이 됩니다.

---

이 이후 부턴 제가 알고리즘 공부를 하면서 기억해둘 만한 유형을 기록해 둔 것입니다.

 

쉬운 계단 수

[백준] 10844: 쉬운 계단 수 리뷰

dp테이블로 2차원 배열을 사용하는 문제입니다. 풀이법을 모르면 접근하기 상당히 어려울 것 같습니다.

 

타일링 문제

[백준] 11727 (2×n 타일링 2) 리뷰

대표적인 점화식 문제인데, 점화식을 접근하는 방법에 대해 다시 생각해 볼 수 있었습니다.