[Algorithm] 다이나믹 프로그래밍

m1njae·2022년 1월 30일
0

Algorithm

목록 보기
4/4
post-thumbnail

다이나믹 프로그래밍

다이나믹 프로그래밍의 가장 큰 특징은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 이러한 특징 덕에 완전 탐색시 매우 비효율적인 시간복잡도를 가진 문제여도 획기적으로 시간복잡도를 줄일 수 있는 경우가 많다.

다이나믹 프로그래밍은 '동적 계획법'이라고도 한다. 이때, 동적은 별다른 의미없이 사용되는 단어이다.

다이나믹 프로그래밍의 구현

  • 탑 다운
    위에서부터 아래로 내려간다고 해서 하향식이라고도 한다.
  • 보텀 업
    아래에서부터 위로 올라간다고 해서 상향식이라고도 한다.

다이나믹 프로그래밍의 조건

  • 최적 부분 조건(Optimal Substructure)
    큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 문제를 해결할 수 있다.
  • 중복되는 부분 문제(Overlapping Subproblem)
    동일한 작은 문제를 반복적으로 해결해야 한다.

피보나치 수열

피보나치 수열은 다이나믹 프로그래밍을 이용해서 해결할 수 있는 대표적인 문제이다.

# 피보나치 함수(Fibonacci Function)을 재귀함수로 구현

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

print(fibo(4))

//실행 결과
3

피보나치 수열의 시간 복잡도


피보나치 수열의 효율적인 해법

메모이제이션(Memoization)

메모이제이션은 다이나믹 프로그래밍 구현 중 하나이며 하향식 즉, 탑 다운에서 사용되는 방법이다.
한 번 계산한 결과를 메모리 공간에 메모하는 기법이다. 같은 문제를 다시 호출하면 메모했던 결과를 가져오도록 한다.값을 기록해놓는다는 점에서 캐싱(cashing)이라고도 한다.

다이나믹 프로그래밍의 전형적인 형태는 보텀 업이다. 이때, 보텀 업 방식에서 사용되는 결과 저장용 리스트는 DP 테이블이라고 한다.

엄밀히 말하자면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해놓는 넓은 개념을 의미한다. 따라서 메모이제이션은 다이나믹 프로그래밍에 국한된 개념이 아니며, 한 번 계산된 결과를 담아놓아도 캐싱을 활용했다라고 볼 수 있다.

# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑 다운 다이나믹 프로그래밍)
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 테이블 초기화
d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀 업 다이나믹 프로그래밍)
for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])

접근 방법

주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요하다. 가장 먼저 그리디,구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토할 수 있다. 다른 알고리즘으로 풀이 방법이 떠오르지 않을 경우, 다이나믹 프로그래밍을 염두할 수 있다.

참고

(이코테 2021 강의 몰아보기)6. 다이나믹 프로그래밍

profile
할 수 있는 것부터 차근차근, 항해자의 공부 기록공간

0개의 댓글