[AIGORITHM THEORY] DP (Dynamic Programing) 개념정리

개념

컨셉

• 다이나믹 프로그래밍, DP, 동적 계획법 모두 같은걸 의미함
• 최적해를 구하기위한 시간, 또는 메모리공간이 많이 필요한 경우 사용하게 된다.
  • 컴퓨터는 연산속도에 한계가 있고, 메모리 공간도 한정적이기 때문
  • 연산속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘이 필요하다.
• 메모리를 적절히 사용해, 수행시간 효율성을 비약적으로 향상시킨다.
  • 한번계산한 문제는 다시 계산하지 않는다.
  • 이미 계산된 결과는 별도의 영역(dp 테이블) 에 저장, 다시 계산하지 않도록 한다. // Memoization
• 구현방식은 크게 두가지로 나뉜다.
  • top-down
  • bottom-up
• 일반적으로 프로그래밍에서 dynamic의 의미는, ‘프로그램이 실행되는 도중에’ 이다. 자료구조 에서의 동적할당 (Dynamic allocation) 은, 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법!
• 실제로 dp에서의 dynamic 은 별다른 의미가 없다.

사용법 (문제의 조건)

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

메모이제이션(Memoization)

• 한번 계산한 결과를 메모리 공간에 메모하는 기법
  • 같은 문제를 다시 호출하면, 메모했던 결과를 그대로 가져온다.
  • 값을 기록해 놓는다는 점에서 캐싱이라고도 한다.
• 메모이제이션 구현
  • 한번 구한 정보를 리스트에 저장
  • DP를 재귀적으로 구생하다가 같은 정보가 필요할 때는 이미 구한 정답을 그대로 리스트에서 가져온다.
• 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 개념
  • DP에 국한되어있는 개념이 아니다! 중요!
  • 한번 계산된 결과를 담기만하고 활용하지 않을 수도 있다.

알고리즘

1. 시작 정점 v를 결정하여 방문
2. 정점 v에 인접하고 아직 방문하지 않은 한 정점 w 선택
   • 방문하지 않은 정점 w가 없다면 (3) 로 감
   • 방문하지 않은 정점 w가 있다면
     1) 정점 v를 스택에 push, pred(w) = v라 셋팅
     2) w를 v로 하여 (1)로 감
3. 스택에서 pop
   • 공백이라면 알고리즘 종료
   • 공백이 아니라면 꺼낸 정점을 v로 하여 (2)로 감

TOP-DOWN vs BOTTOM-UP

• TOP-DOWN
  • 큰 문제를 해결하기 위해 작은 문제를 재귀적으로 호출하는 방식
  • 재귀함수를 사용하여 구현
  • 작은 문제를 재귀적으로 호출하는 과정에서 한번 계산된 결과값을 기록하기 위해 메모이제이션을 이용한다.
• BOTTOM-UP
  • 작은 문제를 하나씩 해결해가며, 먼저 계산했던 문제들의 결과값을 이용해 그다음 문제를 해결하는 방식
  • 반복문을 사용하여 구현
• DP의 전형적인 형태는 BOTTOM-UP 방식이며, 결과 저장용 리스트는 DP 테이블로 불린다.

DP vs 분할정복

• 공통점
  • 둘 다 최적 부분구조를 가질때 사용 가능하다.
  • 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
• 차이점
  • 부분 문제가 중복되는지
    • DP 문제에는 각 부분문제들이 서로 영향을 미치고, 부분문제가 중복된다
    • 분할 정복 문제에서는 동일한 부분문제가 반복적으로 계산되지 않는다.

---

필기

• DP의 큰 예로 피보나치 수열을 확인해 볼 수 있다.

  

  쉽게 생각해 본다면 분할정복과 비슷하고, 재귀함수와도 비슷하다. 재귀와 분할과의 차이점이 있다면, 함수를 불러오는것과, 함수값! 을 가져오는것의 차이가 아니까? 생각한다. 연산을 위해 반복해서 알고리즘을 호출한 후 다음 값을 집어넣어 결과값을 도출하는것과, 미리 계산된 결과값을 dp 테이블에 집어넣어 필요할때마다 해당 인덱스의 결과값을 가져오게 되는것. 두가지의 차이점은 당연히 시간, 메모리가 될것이다.

  피보나치에 대한 dp 식은 아래 코드에 첨부할 예정!
  

• 그럼 문제에는 어떻게 적용할까? DP는 생각과 아이디어가 대부분이다. 뻗어나가기도 쉽고, 문제도 다양하고, 사용할수 있는 방법또한 다양하다. 즉, 정해진 방법이 있는게 아닌, 앞서서 정리한 개념들을 토대로 문제에 적합하게 적용해 내야 한다. 그렇기에 많은 문제들을 접해보며 활용해 보는게 dp학습에 큰 도움이 될거라 생각한다.

• 큰 틀로 문제를 분석해본다면,

  • 최종 목표 작은 문제로 나눠서 풀어내는 이유는, 그 결과들을 활용해 최종 문제의 답을 얻어내기 위해서다. 최종적으로 얻어내고자 하는 값을 확실해가 의식할수록, DP식을 구현하기 편해진다.
    
  • 상태와 값 DP 값은 상태의 값을 담아낸다. 상태, 값 두가지 키워드에 집중을 하는편이 좋다. 진행하는 도중에 필요한 값, 최종결과물과 관련된 값.
    
  • 관계 DP 값들이 의미가 있으려면, 그 DP 사이의 관계식이 확실해야 한다.
    

• DP문제의 해결은 대부분 DP식, 즉 점화식을 잘 세우는 것이 중요하다. 주어진 문제가 DP유형이 맞는지 확인하고, 최종적으로 구할 큰 문제가 뭔지 확인해야 한다.

---

코드

• 백준 2748 / 피보나치 수 2

#https://www.acmicpc.net/problem/2748
#피보나치 수 2
#2748

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * 91

def fun(n):

    if n == 0:
        dp[0] = 0
    if n == 1:
        dp[1] = 1

    if n >= 2:
        dp[0] = 0
        dp[1] = 1
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]

    return dp

result = fun(n)
answer = result[n]

print(answer)

• 백준 9084 / 동전

#https://www.acmicpc.net/problem/9084
#동전
#9084

t = int(input())

def fun(n, coin, m):

    for i in range(n):
        for j in range(m+1):
            if j == coin[i]:
                dp[j] += 1
            elif j > coin[i]:
                dp[j] += dp[j-coin[i]]

    return dp

# result = fun(n, coin, m)
# answer = result[m]
# print(answer)

for _ in range(t):
    # n = 동전의 가지수 / coin = 각 동전의 개수 / m = 만들어야 하는 금액
    n = int(input())
    coin = list(map(int, input().split()))
    m = int(input())
    
    dp = [0] * (m+1)
    result = []

    result = fun(n, coin, m)
    print(result[m])

---

참고자료

• 감사하신 홍정희 교수님의 강의자료
• https://stonejjun.tistory.com/48