다이나믹 프로그래밍 : DP
아니 이게 참 아이러니한게….사실 “DP”라는 말은 실제로 DP의 설명을 하기엔
어울리지 않는 뜻을 가지고 있습니다 ^^…
왜그러냐고요? 전혀 다이나믹 하지 않은 프로그래밍 이거든요;
심지어 프로그래밍이라는 말도 연관성이 없어요 ^^….
여기서 말하는 다이나믹 프로그래밍이란.
복잡하고 큰 하나의 문제를 여러개의 간단한 문제로 나누어 풀고, 그것을 결합하여 복잡하고 큰 하나의 문제를 해결하는 방식입니다. 또한 메모이제이션을 통해 미리 계산해서 저장해 둔 결과를 활용합니다.
그래서 서울대 모 교수는 “기억하며 풀기” 라고 말을 한답니다 ^^
DP와 재귀호출
사실 재귀호출 방식과 DP방식은 매우 흡사합니당.
큰 문제를 작은 문제로 나누어서 푸는거죠? 근데 재귀호출은 심각한 단점이 있습니다.
바로 동일한 작은 문제들이 여러번 반복되어 비효율적인 계산이 될수도 있다. 입니당!
그래서 둘의 차이점을 설명할때 피보나지 수열을 구할때의 재귀호출 방식이 아아아주 많이 예로 쓰입니다.
한번 볼까요?….
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 … 이게 피보나치 수열이죠?
즉 만약에 어떤 수의 피보나치 수열을 구하고 싶다면 식은
return f(n) = f(n-1) + f(n-2); 이렇게 됩니당.
문제는 f(n-1), f(n-2)에서 각각 함수를 1번씩 호출합니다….그래서 위 사진과 같이 동일한 값을 2번 구하게 되죠.
그래서 100번째의 피보나치 수를 구할려고만 해도 시간복잡도가 쥑입니다. O(n^2) 되버려요 ^^
그런데 만약 이미 해결한 문제의 값을 저장해두고 재사용할수만 있다면?
This is DP.
맞습니다. DP가 바로 이미 해결한 문제의 저장값을 저장하고 재사용하는 방식인거죠!
DP를 사용하기 위해서는 2가지 조건을 필요로 합니다.
- 겹치는 부분 문제 (Overlapping Subproblems)
- 최적 부분 구조 (Optimal Substructure)
1. 겹치는 부분 문제
DP는 기본적으로 큰 문제를 작은 문제로 나눕니다. 그리고 작은 문제의 결과 값을 재활용하여서 전체 값을 구하죠.
그렇단…말은…..”동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다”
라고 생각하면 됩니다 ! 당연하죠? 아니 잘 생각해보면…….
DP는 작은 문제의 결과 값을 재활용해서 다시 계산을 안하게 하는것인데, 애초에 해당 문제가 반복적으로 안나타나면,,,
왜 쓸까요….? 만약에 쓴다면 저 좀 알려주세요 궁금해요 ….
2. 최적 부분 구조
말부터 어렵네요 ^….자 쉽게 이해해봅시다. 저희가 피보나치 수열을 구할때 전값들을 가지고 최종값을 구했죠?
즉, 문제의 정답은 문제의 “크기”와 상관없이 항상 동일하다 입니다. 그럴때만 DP를 사용할 수 있따.
쉽죠 헿.
부분 문제에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을 때 DP를 사용할 수 있게 된다.
그래서 언제? 어떻게? 써요?…..
일단 DP로 풀 수 있는 문제인지 먼저 알아야겠지요?…….
사실 이거부터가 난이도가 HELL 이이요 ^^
문제를 직면 했을때 이게 큰 문제를 작은 문제로 나누어서 작은 문제들의 결과 값이 큰 문제가 되냐!
그걸 알아야지 DP를 쓰든가 말든가 하죠…..
그래서 보통은 아래의 과정을 거쳐서 이 문제가 DP로 해결가능한 문제인지 알수 있답니당.
- DP로 풀 수 있는 문제여?…
- 문제의 변수가 뭘까
- 변수 간 관계식을 만들어야 해요… (점화식)
- 메모하기 ! (Memoization or Tabulation)
- 기저 상태 파악하기
- 구현하기
벌써 머리아프네
1. DP로 가능?
자 결론 부터 말해봅시다.
일단 보통 특정 데이터내 최대화 / 최소화 계산을 하거나 특정 조건 내 데이터를 세야 한다거나 확률을 구해야 하는
계산의 경우 DP로 풀 수 있는 경우가 많습니다.
2. 문제의 “변수”가 뭘까요오
DP는 현재 변수에 따라 그 결과 값을 찾고 그것을 전달하여 재사용하는 과정을 반복합니다.
즉 문제의 변수 개수를 알아내야 합니당.
피보나치 수열을 예로 들면 n번째까지 값을 구해야 하죠?
여기서 n이 문제의 “변수”입니다. Ez
3. 변수 간 관계식 만들기
변수들에 의해 결과 값이 달라지지만 동일한 변수값인 경우 결과는 동일합니다. 당빠
저희는 DP를 사용하면서 그 결과값을 고대로 재사용 할것이기 때문에, 그 관계식을 만들 수 있어야 합니다….
그걸 바로 점화식 이라고 부른답니다 ! EX: f(n) = f(n-1) + f(n-2)
4. 메모하기
DP는 결과값을 저장하고 재사용한다 했죠? 그때의 저장하는것을 메모. ⇒ Memoization이라고 부릅니당.
변수 값에 따른 결과를 저장할 배열을 생성하여 결과가 도출되면 배열 내에 저장하고 그 저장된 값을 재사용합니다.
5. 기저 상태 파악하기
여기까지 진행했으면, 가장 작은 문제의 상태를 파악해야 합니다 !
예를 들어 피보나치 수열은 f(0) = 0, f(1) = 1 이죠?? 이게 가장 작은 문제입니당
그래서 해당 문제를 파악하고 미리 배열에 넣어놓은 상태로 사용을 하면 됩니다.
6. 구현하기
허헣 이제 구현만 하면 되요! 어떻게 언제 쓸지 파악을 했으니까요!
보통은 두가지 방법이 있습니다.
- Bottom - Up 반복문
- Top - Down 재귀 호출
이게 뭐냐고요?
그냥 n번째 부터 시작해서 0으로 가느냐
0번째부터 n번째로 가느냐
영어를 번역한 그대로입니다 🙂
번외:
저도 공부를 하면서 분할 정복과 DP의 차이점이 그러면 뭘까?? 라는 생각이 들었는데
잘 생각해보니까 분할정복과 다이나믹 프로그래밍은 일단 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 그 결과를
이용하여 큰 문제를 해결한다는 점은 똑같습니다만….
분할정복 : 분할된 하위 문제가 동일하게 중복이 안일어남.
DP : 일어남…..
끝.
'Programming' 카테고리의 다른 글
| Parameter 와 Argument의 정의 및 차이 (0) | 2023.02.01 |
|---|---|
| 비동기 프로그래밍 (0) | 2023.01.17 |
