dp (dynamic programming)

Konseo·2023년 9월 4일

알고리즘 알고리즘 개념

알고리즘

목록 보기

14/21

다이나믹 프로그래밍

개요

동적 계획법 으로도 불린다

🙋🏻‍♀️ 일반적인 프로그래밍 분야에서의 동적(Dynamic)이란 어떤 의미일까?

자료구조에서 동적 할당(Dynamic allocation)은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법 을 의미한다.

그러나 다이나믹 프로그래밍에서의 다이나믹은 별 의미 없이 사용된 단어 라고 한다😅
메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다
이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.
- 메모이제이션 (Memoization)
  - 한 번 계산한 결과를 메모리 공간에 메모(저장)하는 기법
  - 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다
  - 값을 기록해둔다는 점에서 캐싱(caching)이라고도 한다
두 가지 방식이 존재
- 바텀 업(bottom up) 방식
- 탑 다운(top down) 방식

조건

다이나믹 프로그래밍은 아래의 2가지 조건을 만족할 때 사용할 수 있다.

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

따라서 보통 규칙을 잘 파악하여 dp 테이블의 점화식을 도출해내는 것이 dp의 핵심이다.

바텀업 vs 탑다운

피보나치수열을 바텀업 방식과 탑다운 방식으로 각각 구현해보자
참고로 결과 저장용 리스트는 DP 테이블 이라고 불린다.

바텀업 방식
- 상향식으로도 불린다.
- 다이나믹 프로그래밍의 전형적인 형태이다.
- 피보나치 수열 코드 (bottom up)
```
dp=[0]*100

dp[1]=1
dp[2]=1
n=99

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

print(d[n]))
```

탑다운 방식

상향식으로도 불린다.
피보나치 수열 코드 (top down)

dp=[0]*100

dp[1]=1
dp[2]=1
n=99

def fibo(n):
	if n==1 or n==2:
  	dp[n]=1
  if dp[n]!=0:
  	return dp[n]
  dp[n]=fibo[n-1]+fibo[n-2]
  return dp[n]

print(fibo(n)))

다이나믹 프로그래밍 vs 분할 정복

공통점

최적 부분 구조를 가질 때 사용할 수 있다
- 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황

차이점

부분 문제의 중복
- 다이나믹 프로그래밍 문제에서는 각 부분의 문제들이 서로 영향을 미치며 부분 문제가 중복된다.
- 분할 정복 문제에서는 동일 부분 문제가 반복적으로 계산되지 않는다.
  - 예시 : 퀵정렬
    - 한 번 기준 원소(pivot)가 자리를 변경해서 자리를 잡으면 그 기준 원소의 위치는 바뀌지 않음
    - 분할 이후에 해당 피벗을 다시 처리하는 부분 문제는 호출하지 않음

다이나믹 프로그래밍 문제에 접근하는 방법

주어진 문제가 다이나믹 프로그래밍 문제인 지 파악을 하는 것이 중요하다
먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는 지 검토한다
- 다른 알고리즘으로 풀이 방법이 떠오르지 않는다면 다이나민 프로그래밍 고려해본다
보통은 바텀업 방식으로 점화식을 활용해 dp 풀이를 진행한다
탑다운 방식의 경우 일단 재귀로 (비효율적인) 완전 탐색 코드를 작성한 뒤에 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있다면 dp 테이블 등을 활용해 코드를 개선하는 방법을 사용할 수 있다