다이나믹 프로그래밍(DP, 동적 계획법)의 특징 / DP 알고리즘 문제 접근법

이번 포스팅은 오랜만에 알고리즘 관련임 음하하
교재의 예제들과 함께 백준의 #1463 문제를 풀면서 오랜만에 문제 풀이 포스팅을 적으려다가
어쩌다보니 방향이 바뀌어버려서
글 흐름이 조금 이상할 수도 있는데 결과적으로는
다이나믹 프로그래밍이라는 알고리즘에 대해 내가 이해한 것을 정리한 개념 설명 글
입니다 . . .
나름 열심히 적어보았어요

당연한 내용들일 수도 있는데 DP 유형을 처음 접하는 사람이라면 도움이 될지도?
 
 

---

 
 
https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 
우선 DP 문제에 대한 경험이 없는 사람이 이 문제를 처음 보게 된다면 이게 왜 다이나믹 프로그래밍이지? 생각할 수 있을 것이다. 흔히 다이나믹 프로그래밍과 그리디를 헷갈려하기도 하는데,
그리디는 처음 생각한 최적의 방법이 끝까지 그대로 적용되는 경우에 사용하고,
다이나믹 프로그래밍은 모든 경우의 수에 대해 가능성을 열어두고 최적의 해를 찾는 경우에 사용한다고
생각하면 구분이 조금 될 것 같다.
 
이 문제의 경우, 그리디로 풀게 된다면 가장 큰 수부터 될 수 있는대로 나누어 1을 만들겠지만, 최소의 연산 횟수로 1을 만드는 것이 목표이기 때문에 그리디 알고리즘을 이용하는 것은 적절하지 않다. 3으로 나누거나, 2로 나누거나, 1을 빼거나 하는 이 세 가지 종류의 연산에 대해 가능성을 열어두고 연산 횟수가 최소가 되도록 하는 방법을 찾아야 하므로 여기서는 동적 계획법을 사용할 것이다.
 
 

---

 
 

그래서 어떨 때에, 어떻게 동적 계획법을 사용하면 될까?

다이나믹 프로그래밍 예제 몇 문제를 풀어보고 느낀 점을 토대로 정리해보았다.
 

1. 문제 풀이 과정에서 사용할 수 있는 방법이 여러 개(두 가지 이상) 주어진다면 DP를 의심해보자

다이나믹 프로그래밍(동적 계획법)은 기본적으로 큰 문제를 여러 개의 작은 하위 문제로 쪼개어 문제를 효율적으로 해결하는 알고리즘 기법으로, 작게 쪼개진 문제를 조합하여 최종적인 답을 구해내는 것이 특징이기 때문이다.
 
1로 만들기 문제의 경우, 정수 X를 1로 만드는 최소 연산 횟수를 구하는 것이 목적인데,
사용할 수 있는 연산으로 총 세 가지(3으로 나누기, 2로 나누기, 1 빼기)가 주어진다.
대표적인 DP 유형의 문제로 꼽히는 타일링 문제(정확히 이코테 교재 실전문제 '바닥공사')에서도, 가로 길이가 N, 세로 길이가 2인 바닥을 채우는 모든 경우의 수를 구하는데에 사용되는 덮개의 모양으로 총 세 가지 모양이 주어진다.
 
혹은 두 문제처럼 대놓고
방법 123!!!!!
이렇게 써있지 않은 경우에도 문제를 잘 읽어보면, 풀이를 위한 방법들을 줄글로 설명하고 있는걸 어렵지 않게 알아챌 수 있다.

#1904 / 풀이 과정에서 사용될 두 가지 경우의 수가 주어졌고, 추가적으로 마지막 하이라이트 친 부분에서 이 경우의 수들을 사용하여 정답을 구해내야 한다는 것까지 힌트 삼아 우리는 이 문제가 DP 문제임을 알 수 있다.

#9655

 

2. DP 유형의 문제는 문제마다 풀이법이 크게 다르지 않다.

다이나믹 프로그래밍은 크게 탑다운 방식과 보텀업 방식으로 나뉜다.
탑다운 방식은 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 그렇게 불리며, 재귀를 이용한다.
반면에 보텀업 방식은 작은 문제부터 차근차근 답을 도출해가며, 반복문을 이용한다.
 
두 방식 모두 알아둬야 하겠지만 전형적인 다이나믹 프로그래밍 풀이로는 보텀업 방식을 일반적으로 많이 사용한다.
거기다 다이나믹 프로그래밍 유형의 문제는 코테에서 크게 어렵지 않게 출제되는 경우가 많기에 조금만 연습한다면 비슷한 틀 안에서 쉽게 문제에 접근할 수 있다.
 

3. DP 테이블에 저장할 데이터가 무엇인지부터 잘 정하자

앞에서 DP 문제의 특징으로 큰 문제를 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 달성한다고 설명하였다. 이 과정에서 나누어진 하위 문제들은 중복하여 연산될 가능성이 매우 높으므로, 한 번 해결한 문제에 대해 값을 기록한다. 이는 메모리 공간을 효과적으로 사용할 수 있도록 해주며, 이렇게 결과를 저장하는 공간을 'DP 테이블'이라고 한다.
(DP 테이블은 정확히는 이 보텀업 방식에서 사용되는 결과 저장용 리스트를 가리키며, 탑다운 방식에서는 동적 계획법에서 흔히 들어봤을 '메모이제이션'이라는 표현을 사용한다.)
 
점화식을 세우기 전, DP 테이블의 용도를 확실히 정하자.
 

4. 점화식을 세울 때는 d[i]와 d[i-1]와의 관계를 생각해보면 조금 더 쉽게 식을 세울 수 있다

DP 유형은 풀이법이 다 거의 비슷비슷하다고 했다. 그렇다면 관건은 무엇일까? 
 
바로 점화식을 세우는 것이다.
DP를 처음 공부하는 사람이라면 초반에 이 사실을 알아도 점화식을 세우는 것에 어려움을 느낄 수도 있다.
점화식이란 '인접한 항들 사이의 관계식'을 의미한다. 따라서 d[i]와 d[i-1]의 관계를 생각해보면 조금 쉽게 접근할 수 있을 것이다.
 

5. d[1]부터 d[5]까지는 웬만하면 직접 손으로 그려보자

사실 문제 풀이 연습을 위해 손으로 그림을 그려보는 것은 당연한 얘기이다.
DP의 경우에도, d[1]부터 d[5]까지는 직접 그려보자. (대부분은 5까지는 어렵지 않게 그릴 수 있을 것이다.)
그러면 머릿 속에선 그려지지 않던 패턴이 눈에 보이면서 생각보다 너무 쉽게 점화식을 세울 수 있을지도 모른다.
 
 
 

---

참고 :
 
https://velog.io/@my_id/알고리즘-그리디-vs-DP

[알고리즘] 그리디 vs DP

https://jae04099.tistory.com/199

[파이썬] 백준 - 1463: 1로 만들기 (매우 자세한 해설 포함)