Dynamic Programming (DP)

이번 알고리즘 스터디에서 DP를 했는데..

알고리즘 숙제를 하면서 느낀 점..

나 혹시 탑다운 DP를 모르나..?

귀여운 고양

 

그래서 DP에 대해 다시 정리해보았다. (이전글 +a 해서 재업로드)

---

 

Dynamic Programming 이란?

 

DP의 핵심 컨셉은 한 번 같은 인자를 넣었을 때 동일한 결과가 나오는 경우 이 결과가 필요할 때마다 다시 연산하지 않고 저장해뒀다가 다시 사용한다. 즉, 한 번 푼 것은 다시 풀지 않는다.

 

재귀를 이용하여도 문제의 결과를 도출할 수 있다. 하지만 재귀는 다음과 같은 문제점이 있다.

1. 반복적으로 동일한 데이터를 계산한다.
2. 스택에 호출 경로 데이터를 계속 쌓아두어서 stack overflow가 발생할 수 있다.

 

DP에서는 Memoization이라는 기법으로 연산한 결과를 저장하고 연산 결과가 있는 경우 이를 꺼내서 사용한다.

주로 dp 배열을 만들고 이 배열에 연산 결과를 기록한다.

 

 

 

Top-down vs. Bottom-up

 

DP를 푸는 방법에는 Top-Down, Bottom-Up 두 가지가 있다.

 

 

1. Top-Down

 

Top-Down 방식은 가장 큰 문제를 풀고, 이를 풀기 위해 작은 문제를 푸는 방법이다.

예를 들어, 1일차, 2일차, .. , N일차를 누적해서 문제를 해결해야한다면,

N일차부터 호출하고 이것에 대한 답을 찾기 위해 N-1일차, N-2일차, ... 를 호출한다.

 

재귀에 dp 배열을 이용한 Memoization 이용하여 이 방법으로 해결할 수 있다.

 

 

2. Bottom-Up

 

Top-Down과 반대로 가장 작은 문제에서 시작하여 큰 문제의 답을 찾는 방법이다.

즉, 1일차부터 답을 찾고 이를 활용해서 2일차, 3일차, ... 의 답을 찾는다.

 

반복문을 이용해 구현하며, Top-Down에 비해 메모리와 시간 복잡도 측면에서 유리하다.

 

 

관련 문제

 

• BOJ 2579 계단 오르기

 

 

---

참고 자료

• DP 기본 개념 : https://www.youtube.com/watch?v=FmXZG7D8nS4
• Top-down vs. Bottom-up : https://semaph.tistory.com/16