스프링 DB 1편 - 데이터 접근 핵심 원리 섹션5 이어서 수강

---

토픽 1개 - 동적 계획법 dp

+) 22. 08. 30. 정리한 거 추가!

Dynamic Programming은 Optimization Problem을 해결하는 전략 중 하나이다.
여기서 Optimization Problem이란, 문제를 해결하는 최적의 답(Optimal Solution)을 찾아야 하는 문제를 뜻한다.

Optimal Solution은 하나 이상일 수 있으며, 최대 혹은 최소값을 가지는 Solution을 찾는 문제들이 주를 이룬다. (예: 가장 빨리 도착하는 경로(Solution)의 소요 시간(Value)은? 등…)

DP는 해결하려는 문제를 좀 더 작은 크기의 SubProblem으로 나누고, 그 SubProblem의 Optimal Solution을 활용하여 원래 Problem의 Optimal Solution을 찾는 방식이다.

여기서 문제를 계속 잘게 쪼개다 보면, 어느 순간 겹치는(Overlapping) SubProblem이 생긴다. 그럴 때 이 서브 문제들을 계속 계산하는 것이 아니라 맨 처음 한 번만 계산을 하고, 그 결과를 저장한 뒤에 필요하다면 또 재사용한다.

DP의 두 가지 접근 방식

	Top-Down Approach	Bottom-Up Approach
구조	Recursive(재귀)	Iterative(for-loop)
SubProblem 결과 저장	Memoization	Tabulation
선호되는 상황	SubProblems의 일부만 계산해도 최종 Optimal Solution을 구할 수 있을 때	모든 SubProblems를 계산해야 최종 Optimal Solution을 구할 수 있을 때

Top-Down Approach는 문제들을 작은 크기의 문제로 나누어서 해결하는 것이고, Bottom-Up Approach는 일단 작은 크기의 문제부터 차근차근 해결해 나가는 것이다.

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

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

예제

Climbing Stairs
정상까지 오르는 데 n번의 스텝이 필요한 계단이 있다. 한 번에 한 스텝, 혹은 두 스텝을 오를 수 있을 때, 계단의 정상까지 오르기 위해서는 몇 개의 유니크한 방법이 있는지 구하시오.

예1: n = 2 → 답 = 2 (1step + 1step, 2steps)
예2: n = 3 → 답 = 3 (1step + 1step + 1step, 1step + 2steps, 2steps + 1step)

위 문제는 Optimization Problem이다.

총 몇 개의 유니크한 방법이 있는지 구한다는 것은 최대 몇 개의 유니크한 방법이 있는지를 물어보는 것과 동일하기 때문이다.

f(n) = n스텝의 계단을 오르는 유니크한 방법 수일 때,
➡️ f(n) = f(n-1) + f(n-2)

def climb(n:int) -> int:
	if n <= 2: #재귀 함수에서의 탈출 조건
		return n
	return climb(n-1) + climb(n-2)

Recursion 방식으로 푼 코드

위 코드는 DP를 적용한 것이 아니라 Recursion 방식을 적용한 코드다. Recursion 방식을 적용하면 아래 이미지와 같이 중복 호출이 발생한다.

climb(6)을 호출했을 경우

이렇게 겹치는 SubProblem들이 많을 때, 동일한 Input에 대한 Function Call은 처음 한 번만 계산하고 그 결과를 메모해 뒀다가, 이후에 재사용하는 방식으로 해결하면 된다.

memo = {} #Function Call에 대한 결과를 저장할 공간

def climb(n:int) -> int:
	if n in memo:
		return memo[n]
	if n <= 2: #재귀 함수에서의 탈출 조건
		return n
	memo[n] = climb(n-1) + climb(n-2)
	return climb(n-1) + climb(n-2)

Top-Down 방식 사용(Memoization)

Bottom-Up 방식 사용

def climb(n:int) -> int:
	tabular = {1:1, 2:2}
	for i in range(3, n+1):
		tabular[i] = tabular[i-1] + tabular[i-2]
	return tabular[n]

Iterative(반복문) 사용, Tabulation 방식

Tabulation: 작은 SubProblem부터 시작해서 최종 Problem 결과를 도출할 때까지 결과를 차례대로 기록하는 것.

시간 복잡도 비교

	Recursion	DP: Top-Down	DP: Bottom-Up
시간 복잡도	O(2^n)	O(n)	O(n)

➡️ DP를 사용하면 성능 면에서 개선이 된다는 것을 알 수 있다.

언제 DP를 사용하면 될까?

DP를 사용하기 위해선 다음과 같은 조건이 필요하다.

1. Optimization Problem이 Optimal Substructure여야 한다.
   → Optimization Problem의 Optimal Solution이 Subproblem의 Optimal Solution을 포함하는 구조여야 한다.

   즉, 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다. (부분 문제에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을 때 DP를 사용할 수 있다.)

   예: f(n) = f(n-1) + f(n-2)

   여기서 주의할 점은, Subproblems는 독립적이어야 한다. 즉, Subproblem의 Solution은 다른 Subproblem의 Solution에 영향을 주면 안 된다는 뜻이다.

2. Optimization Problem이 Overlapping Subproblems를 가져야 한다.
   → 재귀적 형태의 알고리즘이 동작할 때, 동일한 Subproblems를 여러 번 해결해야 한다면 해당 문제는 Overlapping Subproblems를 가진다고 표현한다.

   즉, 동일한 작은 문제들이 반복하여 나타나는 경우에 사용 가능하다.

분할 정복과 동적 프로그래밍의 차이점

분할 정복과 DP는, 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결한다는 점은 같다.
하지만 분할 정복은 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우에 쓰며, DP는 동일한 중복이 일어날 경우 쓴다.

정리

일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다.
그러나 한 번 구한 작은 문제의 결과 값을 저장해두고 재사용한다면, 앞에서 계산된 값을 다시 반복할 필요가 없어 매우 효율적으로 문제를 해결할 수 있게 된다.

DP는 특정한 경우에 사용하는 알고리즘이 아니라 하나의 방법론이므로 다양한 문제 해결에 쓰일 수 있다.

Bottom-Up 방식은 아래에서부터 계산을 수행하고, 누적시켜서 전체의 문제를 해결하는 방식이다.
dp[0]가 기저 상태(가장 작은 문제의 상태)이고, dp[n]을 목표 상태라 할 때, Bottom-Up 방식은 dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식이다.

Top-Down 방식은 dp[n]의 값을 찾기 위해 위에서부터 호출을 시작하여 dp[0]의 상태까지 내려간 다음, 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식이다.

---

참고 자료

1. 겐지충 프로그래머, “알고리즘 - Dynamic Programming(동적 계획법)”, https://hongjw1938.tistory.com/47

2. 쉬운코드, “코딩테스트에서 많이 사용되는 dynamic programming(다이나믹 프로그래밍, 동적 계획법)의 개념과 언제 어떻게 사용할 수 있는지 두 가지 예제를 통해 살펴봅니다~”, https://youtu.be/GtqHli8HIqk

---

프로젝트 주제 생각하기