알고리즘 | Algorithm

DP(Dynamic Programming) 동적 계획법 | 파이썬

sungkshon 2024. 5. 27. 23:05
반응형

1. DP

DP는 완전탐색, DFS, BFS와 같이 수많은 경우의 수를 전부 따져봐야 하는데 그 경우의 수가 너무 많아서 속도가 느려지는  문제를 개선하고자 그래서 수행 시간을 단축하고자 만들어진 알고리즘이다.

복잡한 문제를 여러 개의 문제로 나누어 푸는 방법이다.

 

 DP의 목적: 메모리를 사용해서 중복 연산을 줄이고 중복 연산을 줄여서 수행 속도를 개선한다.

메모리를 사용한다 → 배열 혹은 자료구조를 만든다.

중복 연산을 줄인다  → 연산한 결과를 배열에 담는다.

 

2. DP 문제를 알아보고 구분하는 방법

DP는 특정 유형에만 국한되지 않고 다양한 유형의 문제를 최적화 할 때 고려될 수 있는 알고리즘이다.

  1. DFS / BFS 로 풀 수는 있지만 경우의 수가 너무 많은 문제
  2. 경우의 수들에 중복적인 연산이 많은 경우
  3. 문제 해결 접근 방법 (많은 문제 유형을 접해보기)

DP는 다음의 가정 하에 사용할 수 있다.

  1. 큰 문제를 작은 문제로 나눌 수 있다.
  2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

3. DP의 두 가지 접근 방식

재귀적 호출은 Top-Down접근 방식을 사용한다. 즉 큰 문제를 작은 문제로 나누어 해결하는 방식이다.

DP는 주로 Bottom-Up접근 방식을 사용한다. 작은 하위 문제들부터 시작해 결과를 저장하고 점진적으로 큰 문제의 해를 구해 나간다.

4. DP를 사용한 알고리즘 설계 순서

이전값을 어떻게 사용하는지 점화식을 먼저 구하는 것이 DP의 핵심이다.

  1. 주어진 문제의 optimal solution이 구조적으로 어떤 특징을 가지는지 분석한다.
  2. 재귀적인 형태로 optimal solution의 value를 정의한다.
  3. (주로) Bottom-Up 방식으로 optimal solution의 value를 구한다.
  4. 지금까지 계산된 정보를 바탕으로 optimal solution을 구한다.

5. DP 코드 예시

피보나치 수열

피보나치 수열을 재귀함수로 구현 하고 실행 하면, 동일한 함수가 반복적으로 호출된다는 것을 알 수 있다. 반복적인 부분을 저장하는 방법으로 실행 속도를 높일 수 있다.

def fibonacci(num):
    if num == 1:
        return 1
    if num == 0:
        return 0
    return fibonacci(num-1) + fibonacci(num-2)

 

Bottom-Up 방식

def fibonacci_dp(num):
    f = [0, 1]
    for i in range(2, num+1):
        f.append(f[i-1] + f[i-2])
    return f

 

Top-Down 방식

def fibonacci_memoi(num):
    global memo
    if num >= 2 and len(memo) <= num:
        memo.append(fibonacci_memoi(num-1) + fibonacci_memoi(num-2))
    return memo[num]
memo = [0, 1]

 

 

 

 

 

참고

https://www.youtube.com/watch?v=0bqfTzpWySY

https://www.youtube.com/watch?v=GtqHli8HIqk

https://wikidocs.net/130632

 

 

반응형