알고리즘 스터디를 진행하면서 DP에 대해 공부한 내용을 공유하고자 한다.
PPT로 만들어서 발표했기 때문에 ppt 슬라이드를 보면서 정리해 보겠다.
개념 정리
우선 동적 계획법의 정의이다.
동적 계획법은 큰 문제를 작은 문제로 나누고 작은 문제들의 답을 이용해 큰 문제의 답을 구하는 방법론이다.
한 마디로 이전문제의 답을 기억하면서 풀기라고 할 수 있다.
DP의 가장 큰 특징이 바로 이렇게 기억을 할 수 있다는 건데, 이걸 memoization이라고 부른다.
그리고 아래 써놓은 거 처럼 재귀 문제 같다 싶으면 한번 생각해 봐도 좋을 거라고 생각한다.
이제 DP의 조건인데 DP로 문제를 풀려면 최적부분구조와 부분 문제 반복이 있어야 한다.
최적 부분 구조는 큰 문제의 답에 작은 문제의 답이 포함돼 있다는 거고
부분 문제 반복은 한 번 구했던 답이 나중에도 사용되며 이 답은 변하지 않아야 한다는 거다.
예를 들어서 밑에 있는 그래프는 피보나치 수열을 구하는 문제 인데,
f(6)을 구하려면 f(5)와 f(4)를 알아야 한다.
즉, f(6)이라는 큰 문제는 f(5)와 f(4)라는 작은 문제의 답을 포함하고 있기 때문에
최적 부분 구조를 가지고 있다.
그리고 f(6)을 구할 때 f(5)와 f(4)가 필요한데, f(5)를 구할 때도 f(4)와 f(3)을 필요로 한다.
이런 식으로 답을 구할 때 f(4)가 반복적으로 나타나고,
이 값은 변하지 않으므로 부분 문제 반복도 만족한다.
그래서 재사용이 가능하기 때문에 위에 그래프에서 보이듯이
점선으로 된 값들은 굳이 다시 계산하지 않아도 되어 시간을 많이 절약할 수 있다.
DP 문제를 푸는 방법은 두 가지가 있다.
첫 번 째는 bottom-up인데 말 그대로 작은 문제부터 차근차근 해결해서 큰 문제를 구하는 방법이다.
보통 for문을 사용해 문제를 해결하며 재귀 호출이 없어 시간과 메모리를 절약할 수 있다는 장점이 있다.
하지만 직관적으로 이해하기 힘들 수 있다는 단점도 있다.
오른쪽에 피보나치 수열을 구하는 코드를 보면 먼저 dp테이블을 초기화하고,
피보나치 1과 2는 구할 수가 없으니 초기화를 해준 다음에
for문을 통해 3부터(작은 문제)시작해서 점화식을 이용해 n까지 채워나가는 방법이다.
두 번 째는 top-down인데 이건큰 문제부터 작은 문제로 내려가면서 큰 문제의 답을 구하는 방법이다.
보통 재귀로 문제를 해결하며,
재귀를 돌면서 전에 계산해둔 값이 있으면 쓰고 없으면 계산하는 식으로 작동한다.
최대 재귀 깊이 초과 에러가 발생할 수 있으며,
메모리와 시간을 bottom-up에 비해 많이 잡아 먹는다는 단점이 있다.
하지만 점화식을 이해하기 쉽다는 장점도 존재한다.
오른 쪽에 코드를 보면 재귀 함수에 n(큰 문제)을 매개변수로 넘겨주고,
재귀 함수에서는 전에 계산해둔 값이 있으면 dp테이블에서 가져와서 쓰고
없으면 재귀를 돌리는 식으로 작동하는 걸 볼 수 있다.
top-down과 bottom-up 중에 어떤 게 더 좋냐고 했을 때 명확한 답은 없다고 한다.
그래도 구분해보자면 위와 같다.
그런데 나는 bottom-up 방식이 더 이해하기 쉬워서 bottom-up으로 풀다가
안되면 top-down으로 풀 수 있을 지 고민해 보는 방식으로 하려고 한다.
문제 푸는 방법
여기까지가 개념 설명이었고,
우리는 알고리즘 문제를 풀어야 하기 때문에 이제 부터는 문제를 푸는 방법을 소개하려고 한다.
우선 이 문제가 DP인 지 아닌 지 구별하는 방법이다.
그리고 참고로 DP문제를 풀면서 느낀건데 뭔가 내가 생각하기에
DFS나 완전탐색 문제의 느낌이 날 때 DP문제인 경우가 좀 있었다.
위의 방법대로 생각해 봤는데 완전 탐색인 지 그리디인 지 헷갈릴 경우에는 이걸 생각해보자.
이제 DP문제라는 감을 잡았으면 위의 방법대로 차근차근 생각해보면 문제를 좀 쉽게 풀 수 있다.
문제 풀이 예시
이제 부터는 문제 풀이 예시이다 .
백준에 1로 만들기라는 문제를 한 번 풀어보자
근데 사실 내 블로그에도 이 문제 풀이를 정리해 둔 적이 있다.
첫번 째로 처음 문제를 보면 보통 어떤 흐름으로 답이 구해지는 지 끄적여 볼 것이다.
그렇게 끄적이다 보면 뭔가 반복되는 것이 발견될 때가 있는데, 이 때 DP인지를 의심해 보면 된다.
나머지는 슬라이드에 설명이 있기 때문에 생략한다.
그리디인 지 판단하는 부분만 보충 설명을 하자면
보통 일반적으로는 3이나 2로 나눠지면 3으로 나누는 게 가장 빨리 1로 갈 것이고, 2로 나눠지면 2로 나누는 게 빨리 1로 갈 것이고 이도 저도 아닌 경우에만 -1을 하면 되겠다 라고 생각할 수있다.
9 -> 3 -> 1이 이걸 만족하는 일반적인 경우이다.
하지만 10의 경우에는 2로 나누어지기 때문에 위의 논리대로 라면
10 -> 5 -> 4 -> 2 -> 1이 되어야 한다.
하지만 10 -> 9 -> 3 -> 1이 더 빠르다.
이렇게 내가 생각한 방법이 끝까지 반례없이 적용되지 않기 때문에 그리디로 풀 수 없다고 판단할 수 있다.
이렇게 DP문제인 지 알았으면 문제 풀이 과정은 아래와 같다.
1. 반복되는 부분을 찾는다.
5,4,3,2를 1로 보내는 방법의 수를 나열하면 위에 적어놓은 것 처럼 나온다.
여기서
5->1의 최소연산은
5->4->2->1, 5->4->3->1
4->1의 최소 연산은
4->2->1과 4->3->1
3->1의 최소연산은
3->1
이라는 걸 알 수가 있다.
여기서 우리가 얻을 수 있는 사실은
5->1의 최소 연산인 5->4->3->1은 4->3->1을 포함하고
4->1의 최소 연산인 4->3->1은 3->1을 포함한다!
작은 문제의 답이 반복된다!!
2. dp[i]의 의미 정의
위의 아이디어로 부터 우리는
이전 수의 최소 연산 횟수를 저장하면 다음 수는 이 횟수의 +1만 해주면 된다고 생각할 수 있다.
그래서 dp[i] = i를 1로 만들기 위한 최소연산 횟수로 정의한다.
3. 점화식 세우기
3으로 나누거나 2로 나누거나 -1을 한 수의 최소연산횟수에 +1한 게 현재 수의 최소연산 횟수가 될 것이다.
dp[i] = min(dp[i-1], dp[i//2], dp[i//3])
4. bottom-up vs top-down
슬라이드에 적은 것과 같이 bottom-up으로 결정
이런 식으로 풀면된다!
참고로 top-down으로도 풀어봤는데 메모리 초과가 난다.
직접 문제 풀어 보기
이제 쉬운 계단수 문제로 위의 예시처럼 순서대로 풀어보면서 한 번 더 연습해보자
이 문제의 풀이는 아래 슬라이드 참고!
처음 이 문제 보고 내 접근 방법
메모리 초과 이후 수정한 접근 방법
