[알고리즘] DP

zxcvbee·2022년 1월 16일
0

DP관련 문제를 풀 때는 기억에 남지만, 프로젝트를 진행하고 다른 알고리즘 문제를 풀다가 DP를 만나면 개념이 리셋되는 경우가 많기에 정리하여 기억해보려 한다.

DP(Dynamic Programming)는 메모리를 적절히 사용해 시간 효율을 향상시키는 방법으로, 이미 계산된 결과(작은 문제)는 별도의 메모리에 저장하여 다시 계산하지 않도록 한다.

완전 탐색을 이용해 비효율적 시간복잡도를 가지는 문제를 DP를 이용해 시간복잡도를 획기적으로 줄일 수 있는 경우가 많다.

DP 사용 가능한 조건

  1. 최적 부분 구조
    큰 문제를 작은 문제로 나눌 수 있어, 작은 문제의 답을 모아 큰 문제를 해결할 수 있는가.
  2. 중복되는 부분 문제
    동일한 작은 문제를 반복적으로 해결할 수 있는가.

DP를 대표하는 문제

  • 피보나치 수열
    앞 두 수의 합이 다음 수가 되는 수열을 말한다.

피보나치 수열을 점화식으로 표현한다면, 아래와 같다. 점화식이란 인접한 항 사이의 관계식이다.

프로그래밍에서는 이러한 수열을 배열이나 리스트를 이용해 표현한다.

n번째 피보나치 수열을 f(n)이라고 할 때, 4번째 피보나치 수 f(n)을 구하는 과정은 아래와 같다.

def fibo(x):
	if x == 1 or x ==2:
    	return 1
    return fibo(x-1) + fibo(x-2)

print(fibo(4))

이렇게 단순 재귀함수로 피보나치 수열을 구현을 한다면 O(2^N)을 갖게 된다.

DP 구현

DP 문제는 상향식(보텀업)과 하향식(탑다운) 방식으로 구현할 수 있다.

메모이제이션(Memoization)

DP 문제를 하향식으로 구현한 방식으로, 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다. 그렇기에 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다. 이 방법은 값을 기록해 놓기에 캐싱(Caching)이라고도 한다. 이러한 방식으로 구현하면, 이미 계산된 결과를 메모리에 저장하므로 아래와 같이 색칠된 노드만 처리하면 된다.

아래는 피보나치 수열을 탑다운 방식으로 해결한 코드이다. 시간 복잡도는 O(N)이다.

memo = [0] * 100

def fibo(x):
	if x == 1 or x == 2:
    	return 1
   
    # 이미 계산한 적 있다면, 그대로 반환
    if memo[x] != 0:
    	return memo[x]
    
    # 아직 계산한 적 없다면, 점화식 따라 피보나치 결과 반환
    memo[x] = fibo(x-1) + fibo(x-2)
    return memo[x]

print(fibo(99)

아래는 피보나치 수열을 바텀업 방식으로 해결한 코드이다.

memo = [0] * 100

memo[1] = 1
memo[2] = 1
n = 99

for i in rnage(3, n+1):
	memo[i] = memo[i-1] + memo[i-2]

print(memo[n])

DP VS 분할 정복

두 알고리즘 풀이 방식에서 헷갈렸던 것은 DP와 분할 정복 모두 큰 문제를 작은 문제를 나누어 작은 문제의 답을 모아 큰 문제를 해결할 수 있을 때 사용할 수 있다. 즉, 최적 부분 구조를 가질 때 사용할 수 있다. 하지만 차이점은 아래와 같다.

구분DP분할 정복
차이점각 부분 문제들이 서로 영향 미치며 부분 문제가 중복된다.동일한 부분 문제가 반복 계산되지 않는다.

0개의 댓글