알고리즘의 꽃(이라고 생각합니다) 동적 계획법!
흔히 줄여서 DP라고 부르죠.
저는 개인적으로 이게 제일 어렵습니다 ㅠㅠ 그래서 오늘 한 번 뿌셔보려고 합니다
** 이번 파트는 코드그라운드의 Codeground Note와 여러 사이트를 참고해가면서 포스팅했습니다!
동적 계획법(Dynamic Programming)
복잡한 문제를 여러 개의 작은 부분 문제(Sub-Problem)로 나누어 해결하는 방법
쓰는 이유?
지금은 속도가 중요한 시대죠! 동적 계획법의 핵심인 Memoization을 이용하면 큰 문제로부터 빠른 속도로 최적의 해를 찾아낼 수 있기 때문입니다.
예시
DP 설명할 때 항상 등장하는 DP 예시의 조상님, 피보나치 수열 되시겠습니다!
<사진 출처 : http://egloos.zum.com/kuphy00/v/2472789>
피보나치 수열은 모두가 알다시피, 1 1 2 3 5 8.... 이런식으로 N번째의 값 = N-1번째 값 + N-2번째 값 을 계산하는 수열입니다.
아~주 간단하게 표현하면 DP[N] = DP[N-1] + DP[N-2]가 되겠죠.
위의 그림처럼,
1. 피보나치 수열로 계산된 값 중 7번째 값을 구하고 싶을 때
2. 위의 방식으로 분할하여 답을 찾는데
3. 중간에 중복 호출이 발생하기 때문에 Memoization 기법을 사용해줘야 합니다.
Memoization이 뭔데?
프로그래밍 할 때, 반복되는 결과를 메모리에 저장해서 중복호출 되었을 때, 한 번 더 계산하지 않고 메모리에 저장해둔걸 가져와서 재활용 한다고 보시면 됩니다.
쉽게 말해서, 학습이라고 생각하면 편할 것 같습니다. 우리가 구구단을 외우는 이유처럼요 ㅋㅋㅋ 9 x 2가 18인걸 우린 달달달 외워서 알고 있지, 펜 꺼내들고 계산하고 있지는 않잖아요?
9 x 2 = 18이다 라는 것을 기억하고 있으면, 다른 문제에서 해당 계산이 요구될 때 굳이 계산하지 않고 머리에서 18이라는 값을 끄집어내서 갖다 쓰면 되는 그런...거죠 ㅎㅎ
그러면 자연스럽게 왜 Memoization을 사용하는지 알게 되었고.... 이로 인해 얻는 장점은 해결 속도가 빨라진다! 라는 점을 자연스럽게 알게 되는거죠.
하지만 세상에 공짜는 없죠! 속도를 얻는 대신 메모리를 잃습니다(?) 잃는다기 보다는 '실행 시간과 메모리를 trade-off한다' 라고들 표현합니다.
구현 방식은?
두 가지가 있습니다. Top-Down과 Bottom-Up
Top-Down은 뜻 그대로 큰 문제(Main Problem)에서 작은 부분 문제(Sub Problem)를 재귀적으로 호출하여 리턴된 값으로 문제를 해결하는 방식입니다.
1 | Func(n) = Func(n-1) + Func(n-2); | cs |
위에 처럼 말이죠!
Bottom-Up은 작은 부분문제(Sub Problem)를 미리 계산해두고, 이 문제들을 모아 큰 문제를 해결하는 방식입니다.
1 2 3 4 5 | DP[1] = 1; DP[2] = 1; for(int i=3;i<N;i++) DP[i] = DP[i-2] + DP[i-1]; | cs |
요것처럼 말이죠 ㅎㅎ
저는 주로 Bottom-Up 방식을 쓰고 있습니다. Top-Down은 조건도 잘 걸어줘야 하고, Memoization을 잘 활용해야 해서 까다롭거든요... 아직 저는 실력이 부족해서 ㅠㅠ...
각각은 장단점이 있어요
Top-Down은 재귀함수를 통해서 구현되기 때문에 함수 호출에 대한 오버헤드가 발생한다는 단점이 있지만, Memoization을 잘 활용하면 Bottom-Up보다 훠어어얼씬 빠릅니다.
Bottom-Up은 큰 문제를 해결하기 위해서 어떤 Sub Problem이 요구되는지 몰라서 모든 부분 문제를 해결해야 한다는 단점이 있지만, for문으로 구현되므로 자원에 비교적 자유로워서 시간 및 메모리의 최적화가 쉬워요!
그럼, DP문제 종류엔 뭐가 있나요?
1. Coin Change Problem
2. KnapSack
3. LCS
4. LIS
5. Edit Distance
6. Matrix Chain Multiplication
이 있습니다. 저는 개인적으로 Coin DP를 진짜 맨날!!!! 볼때마다 틀려서 이번에 이거만 확실히 정리할거예요 헤헤
Coin Change Problem
흔히 coin DP라고들 하죠 코인디피...
쉽게 말하면 제가 슈퍼마켓을 가서 1300원짜리 부라보콘을 사고 2천원을 냈어요. 그러면 거스름 돈으로 500원짜리 하나, 100원짜리 두개를 주겠죠?
우리한텐 이게 당연한데 컴퓨터는 안그렇거든요... 슈퍼가서 700원 거스름돈 주는데 10원짜리 70개 뭉태기로 주면 칼부림나겠죠..?
이처럼, 거스름돈을 줄 때 동전의 갯수를 최소화하는 로직을 짜는 문제가 바로 Coin DP입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | import java.util.*; public class Main { public static void main(String args[]) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int k = scanner.nextInt(); int coin[] = new int[n]; for (int i = 0; i < n; i++) { coin[i] = scanner.nextInt(); } int d[] = new int[k + 1]; for (int i = 1; i <= k; i++) { d[i] = -1; for (int j = 0; j < n; j++) { if (coin[j] <= i) { if (d[i - coin[j]] < 0) continue; if (d[i] < 0) d[i] = d[i - coin[j]] + 1; else if (d[i - coin[j]] + 1 < d[i]) d[i] = d[i - coin[j]] + 1; } } } System.out.println(d[k]); } } | cs |
인터넷에 흔히 보이는 코드입니다.
하나씩 뜯어보죠!
D[i] 는 'i원을 만들기 위해 필요한 동전의 최소 갯수'를 의미합니다.
Coin에는 우리가 갖고 있는 동전의 가치를 의미하구요. Coin[N] = {1, 5, 11}이라면, 거스름돈으로 1원짜리, 5원짜리, 11원짜리를 각각 갖고 있는 상태입니다.
D[1]을 볼까요? 1원을 만들기 위해 필요한 최소 동전의 갯수입니다. 1원이니까 당연히 1개만 필요하겠죠!
1 2 3 4 5 6 7 8 9 10 | int d[] = new int[k + 1]; for (int i = 1; i <= k; i++) { d[i] = -1; for (int j = 0; j < n; j++) { if (coin[j] <= i) { if (d[i - coin[j]] < 0) continue; if (d[i] < 0) d[i] = d[i - coin[j]] + 1; else if (d[i - coin[j]] + 1 < d[i]) d[i] = d[i - coin[j]] + 1; } } | cs |
위의 코드에서는 Coin으로 무슨 값이 들어올지 모르기 때문에 -1로 초기화하고, 밑의 조건에서 다 처리해주고 있네요!
만약 i가 5라면, 밑의 조건에서 5보다 작거나 같은 동전이 있는지
1 | if(coin[j] <= i) // A | cs |
에서 골라내주고 있습니다. 편의상 A 조건문이라고 할게요.
1 | if (d[i - coin[j]] < 0) continue; // B | cs |
위의 조건은, 간단히 말해서, d[i]가 -1이면 진행하지 않는다는 말 입니다. 즉, 갖고 있는 동전으로는 만들 수 없는 값이라는 의미가 되죠!
우리가 갖고 있는 동전은 1원 5원 11원인데 만들 수 없는 거스름돈은 없겠지만, 만약에 2원 5원 11원 이렇게 갖고 있다면, 죽었다 깨어나도 8원은 못 만들겠죠! 그런 부분을 예외처리 해준 조건문입니다.
여기는 B 조건문이라고 하겠습니다.
1 2 | if (d[i] < 0) d[i] = d[i - coin[j]] + 1; // C else if (d[i - coin[j]] + 1 < d[i]) d[i] = d[i - coin[j]] + 1; // D |
A, B 조건문을 모두 거치면, 만들 수 있는 동전임이 증명이 된 상태입니다. 이제 최소를 찾으면 되겠네요.
예시를 들면서 하는게 더 낫겠죠? 하핫 저도 쓰면서 뭔소린지 이해가 안돼서 다 지우고 다시씁니다 ㅋㅋㅋㅋㅋ
현재 갖고 있는 동전은 1원 5원 12원입니다.
우리는 현재 i = 6이고, coin[j] = 5 이라고 해볼게요. d[6]은 아직 정해지지 않았기 때문에 당연히 -1이겠죠!
그래서 d[6] = d[6 - 5] + 1. 즉, d[1] + 1을 하겠다는 소리는, 1원을 만들기 위해 필요한 최소 동전의 갯수에다가 5원을 추가하여 6원을 만들때 필요한 최소 동전의 갯수를 d[6]에 저장하겠단 소리가 되네요!
이게 바로 C조건문입니다.
D 조건문은, i가 5일때를 생각하면 쉽겠네요!
d[4]까지 구해진 상태에서, 5원만 넣은것과(d[i]), 4원까지의 최소 값에 +1한 것(d[i - coin[j]]+1)을 비교했을 때, 더 작은 값을 넣겠단 소리가 됩니당.
후.. 어렵네요 ㅋㅋㅋㅋㅋ 알고리즘 문제 많이 풀면서 감을 익히는게 최고일 것 같습니다.