DP
- 코딩 테스트 연습 중 DP가 매우 많이나오는 문제라고 해서 정리해두려고 한다.
- 마침 오늘 풀었던 알고리즘 문제도 DP문제이고
DP
- 하나의 큰 문제를 작은 문제로 나누고, 그 작은 문제를 해결하여 큰 문제의 답을 도출해내는 기법
- 작은 문제를 해결하는 과정에서 중복되는 연산을 수행하지 않는 기법
- 피보나치 문제를 이용하여 DP 문제의 접근 방식에 대해 설명해보려고 한다.
DP 문제 접근 방식
a) 첫 번째 규칙 - 큰 문제를 작은 문제로 표현할 수 있다.
- 피보나치는 다음과 같이 표현된다.
f(3) = f(2) + f(1)
f(5) = f(4) + f(3)
f(7) = f(6) + f(5)-
위의 예시를 보면, f(3)이라는 큰 문제를 f(2)와 f(1)이라는 작은 문제로 나누었다.
-
f(5)라는 큰 문제를 f(4)와 f(5)라는 작은 문제로 나누었다.
-
f(7)이라는 큰 문제를 f(6)과 f(5)라는 작은 문제로 나누었다.
-
이와 같이 하나의 큰 문제를 작은 문제로 표현할 수 있어야 DP를 적용할 수 있다.
-
즉, 하나의 큰 문제를 해결하기 위해서는 이를 구성하는 작은 문제의 계산 값을 알아야 한다.
b) 두 번째 규칙 - 점화식
- 위에서 DP 문제는 큰 문제를 작은 문제로 표현할 수 있다고 설명하였다.
- 이 말은 어떤 문제를 표현할 때 점화식(= 공식)으로 표현할 수 있다는 의미다.
- 다음 피보나치 점화식처럼 말이다.
f(n) = f(n-1) + f(n-2)- 피보나치 점화식을 분석해보면, f(n)의 값을 알기 위해서는 f(n - 1)과 f(n - 2)의 값을 알아야 한다.
- 즉, f(n)이라는 큰 문제를 f(n - 1)과 f(n - 2)라는 작은 문제로 나눌 수 있다는 것이다.
- 이처럼 n이 어떤 값이던 항상 동일하게 점화식으로 표현할 수 있는 것이 DP 문제의 특징이다.
- 더불어, 이 점화식을 직접 구하는 것이 DP 문제 풀이의 핵심이다.
c) 세 번째 규칙 - Memoization (Optional)
-
Memoization이란 컴퓨터 프로그램에서 동일한 계산을 반복(= 중복)해서 수행하는 경우 반복되는 동일한 연산의 값을
메모리에 저장하여 중복 계산을 제거함으로써 프로그램의 속도를 빠르게 하는 기술 또는 방법론을 의미한다. -
즉, 캐싱(Caching)이다.
-
DP에서도 이 방법론이 사용된다. 그러나 이는 선택적으로 사용한다.
-
그 이유는 조금 있다가 알아보고, 아래의 예시를 보자.
f(5) = f(4) + f(3)
f(4) = f(3) + f(2)
f(3) = f(2) + f(1)- 위의 예시에서 f(5)의 값을 구하려고 한다.
- f(5)는 f(4)과 f(3)으로 나눌 수 있고, f(4)와 f(3) 또한 더 작은 문제로 나눌 수 있다.
- 이 과정을 반복하다 보면 다음과 같이 중복되는 연산을 수행한다.
f(5) = f(4) + f(3)
f(4) = f(3) + f(2)
f(3) = f(2) + f(1)
f(5) = f(3) + f(2) + f(2) + f(1)
= f(2) + f(1)+ f(2) + f(2) + f(1)- 이처럼 중복 연산을 수행하는 것은 시간 복잡도나 메모리적 측면에서 비효율적이다.
- 그러므로 중복되는 연산의 값을 저장해놓는 방식을 사용하는데, 이를 memoization이라고 부른다.
d) 네 번째 규칙 - 테이블의 사용
-
앞서 DP는 memoization을 사용한다고 설명하였다.
-
그렇다면 어디에 중복되는 연산의 값을 저장할까?
-
이 저장 공간을 테이블이라고 표현한다.
-
테이블은 특별한 것이 아니다.
-
어떤 형태로든 중복되는 연산의 값을 저장하고 필요할 때 찾아서 사용할 수 있으면 된다.
-
대표적으로 단일 또는 이중 배열, 리스트, 필요에 따라서는 HashMap으로 구현된다.
DP의 풀이 방식
a) DP의 풀이 방식
- 모든 DP 문제는 Bottom-up과 Top-down이라는 2가지 방식으로 풀이될 수 있다.
- 이 방식에 대해서 알아보도록 하자.
b) Bottom-up 방식
-
어떤 글을 읽고 내용을 설명해야 한다고 해보자.
-
위에서 아래로 순차적으로 글을 읽고 내용을 이해한다.
-
이처럼 Bottom-up 방식은 데이터가 들어오는 순서대로 처리하는 과정을 사용한다.
-
대표적인 예시로, 위에서 구현한 피보나치 코드가 Bottom-up 방식이다.
-
즉, 1번째 숫자부터 N번째 숫자까지 차근차근 구하는 방식이다.
-
그러므로 반복문을 사용한 순차적인 DP 풀이를 Bottom-up 방식이라고 한다.
c) Top-down 방식
-
어떤 글을 읽고 내용을 설명해야 한다고 해보자.
-
주어진 글이 너무 길어서 각 문단의 앞부분만 읽고 전체적인 맥락을 이해한다.
-
이처럼 Top-down 방식은 어떤 패턴을 이용하는 과정을 사용한다.
-
즉, 재귀 함수를 이용하여 답을 찾는 방식이다.
-
그러므로 Recursion & Memoization을 사용한 DP 풀이를 Top-down 방식이라고 한다.
출처: https://devraphy.tistory.com/627 [개발자를 향하여:티스토리]
알고리즘
