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

chaaansooo·2022년 3월 31일
1

알고리즘 문제풀이

목록 보기
11/13

다이나믹 프로그래밍(Dynamic Programming)

DP

DP의 정의

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

DP가 필요할 때

피보나치 수열을 계산할 때 f(n)을 구하기 위해서 f(n-1)과 f(n-2)를 알아야 한다.
f(n-1)을 알기 위해서는 f(n-2), f(n-3)을 알아야 한다.
여기까지만 보더라도 많은 중복되는 계산이 굉장히 많다는 것을 알 수 있다.
DP는 이렇게 한번 계산한 값들을 다시 계산하지 않고, 저장해두고 reuse하는 방법이다.

Divide & conquor와의 유사성

위의 예시처럼 큰 문제를 작은 문제로 쪼개서 푼다는 의미에서 DP문제의 대부분은 D&Q의 개념을 공유한다.
하지만 피보나치를 보면 계산을 해야하는 양이 지수함수로 늘어난다.
우리는 이렇게 엄청나게 늘어나는 계산량을 DP를 통해 줄여줄 수 있다.

DP Basic Operation

DP의 연산량은 값들을 저장하기 위한 표를 채우는 것과 같다.

활용

DP Design

  1. 큰 문제를 작은 문제로 나눠서 볼 수 있는 반복을 찾아낸다.
    (단, 작은 문제에서 구한 정답은 큰 문제에서도 동일해야한다)
  2. 처음 진행되는 계산은 Look-up table을 사용해서 저장하고 재사용한다.

DP Analysis

DP의 Time Complexity는 Look-up table의 cell의 연산량 = # subproblems * # time/sub

두가지 방식

  1. 탑다운(Top-Down): 재귀를 이용해서 가장 큰 덩어리부터 접근해서 작은 덩어리로 내려간다. 메모이제이션을 사용한다.
  2. 바텀업(Bottom-Up): 반복문을 이용해서 가장 작은 덩어리부터 큰 덩어리로 접근한다.DP 테이블을 사용한다.
    일반적으로는 바텀업 방식을 더 많이 사용한다.(반복문이 재귀보다 리소스 덜 사용)

모두 계산을 할 필요가 없을 때

우리가 찾고자하는 값까지 도달하기 위해 그 전의 모든 값이 필요하지 않을 때는 dictionary같은 자료형이 더 유리할 수 있다.

profile
악으로 깡으로 버티기

0개의 댓글