냄비
동적 계획법의 개념은 문제에서 주어진 최종적인 결괏값을 만드는 것을 여러 개로 쪼개어 그 아랫단계로 만들어 내는 것이다.
즉 i번째의 결과를 도출해내기 위하여 i-1번째를 보고 i-1번째를 만들기 위하여 i-2번째를 참조하는 식이다.
다만 이런 예시는 단순히 반복문만으로 하드코딩을 하더라도 풀어낼 수 있다.
하지만 만약 i번째의 결과를 만들기 위하여 3가지 경우의 수가 존재한다면?
DP[i] = DP[i-1] + DP[i-2]
DP[i] = DP[i-2] + DP[i-3]
DP[i] = DP[i-1] + DP[i-3]
와 같은 점화식이 나오고 그중에서 최댓값 혹은 최솟값을 구해야 한다면 반복문으로는 풀 수 없는 한계점에 이르게 된다. 단순히 3가지의 경우만 있더라도 10번째 최솟값을 구하기 위해선 3^10 = 59049번의 반복문을 돌려야 하고 만약 20번째가 될 경우에는 약 35억 번의 반복문을 돌려야 한다.
따라서 우리는 동적 계획법에 대한 문제를 풀 때 먼저 점화식을 세워야 하고 동적 계획법에 해당되는 문제가 나왔을 때 가장 먼저 해야 하는 것은 최종적인 결과를 도출해내기 위하여 경우의 수가 몇 가지 있고 해당되는 경우의 수들을 얼마나 빠르게 점화식으로 풀어내는가 이다.
(이하는 백준과 프로그래머스에 등장하는 DP문제들이며 단계는 완벽하게 주관적인 평가로 이루어졌으며, 다만 개인적으로 이런 순서로 풀어나가면 될 것이라고 추천하는 바이다.)
1단계인 백준 2748번 피보나치수열을 보자.
피보나치수열은 앞의 두 숫자를 더하여 현재 내가 바라보는 숫자를 만들어내는 수열이다.
즉 DP[i] = DP[i-1] + DP[i-2]가 되는 것이다.
피보나치수열은 초기값 0,1,2 번째만 기본값으로 정해주면 쉽게 해결할 수 있다.
henrynoh.tistory.com/6?category=952032
2748번 피보나치수2 BOJ 백준 C언어
문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2
henrynoh.tistory.com
1단계 수준의 문제는 1003번 피보나치 함수 / 1904번 01타일 정도이다.
2단계는 백준 2579번에 해당되는 계단 오르기 문제이다.
계단 오르기 문제부터 이제 동적 프로그래밍의 시작이라 볼 수 있다.
해당 문제에서 주어지는 조건들을 점화식으로 구현하자면 결국 2가지 점화식이 나오게 된다.
DP[i] = DP[i-2] + ARR[i]
DP[i] = DP[i-3] + ARR[i-1] + ARR[i]
henrynoh.tistory.com/26?category=952032
2579번 계단 오르기 BOJ 백준 C언어
문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있
henrynoh.tistory.com
위와 같이 점화식을 찾는 방법만 이해하고 있다면
9461번 파도반 수열 / 1149번 RGB거리 / 1463번 1로 만들기 / 2156번 포도주 시식 까지는 무난하게 풀 수 있게 된다.
하지만 이까지는 이제 DP의 몸풀기에 불과하다.
3단계 정도의 수준으로 넘어가면 11053번 가장 긴 증가하는 부분 수열 문제 정도가 된다.
이 정도 수준의 문제부터 서서히 자료구조를 여러 개를 사용하며 앞선 문제들처럼 단순히 점화식만을 찾아서 쉽게 해결하기엔 힘든 문제들이 등장하기 시작한다.
사실 앞으로 소개할 문제도 앞선 2단계 수준의 문제만 해결할 수 있다면 조금만 노력을 하면 풀 수 있는 문제이다.
하지만 블로그 유입 수도 가장 많은 게시글이기도 하고 왜 이 문제가 어려운가를 생각해보니 딱 한 가지 이유인 것 같다.
이 문제를 어떻게 DP로 해결하는지에 대한 방법을 몰라서이다.
가장 긴 증가하는 부분 수열의 경우 처음 문제를 본 순간에 최종 결괏값으로부터 점화식을 이끌어내기가 상당히 힘든 축에 속한다. 일반적으로 머리로 생각하기에는 "앞에서부터 그냥 커지면 더해주고 작아지면 안 더해주면 된다"라는 간단한 풀이 구조를 가지고 있지만 해당 알고리즘을 어떠한 자료구조와 변수를 써서 문제를 해결하는가에 대한 연습이 안 돼있어서 일 것이다.
henrynoh.tistory.com/32?category=952032
11053번 가장 긴 증가하는 부분수열 BOJ 백준 C언어
문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10,20, 10,30, 20,50} 이
henrynoh.tistory.com
위 문제와 비슷한 유형은 11054번 가장 긴 바이토닉 부분 수열 / 2565번 전깃줄 정도가 있다.
3단계 수준에서 약간 다른 유형을 꼽자면 1912번 연속합 문제가 있다.
연속합 문제를 보면 마찬가지로 DP로 해결을 하지만 DP를 생성할 때 일반적이지 않은 예시들이 나온다.
해당 문제에서는 음수를 포함하더라도 최대합이 되는 경우가 생기는 것처럼 말이다.
henrynoh.tistory.com/35?category=952032
1912번 연속합 BOJ 백준 C언어
문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들
henrynoh.tistory.com
해당 문제와 비슷한 느낌의 문제는 10844번 쉬운 계단수 정도가 있다.
이 정도까지가 Programmers Level 2 정도에 해당된다.
Level 2에 해당되는 문제들을 약 30분가량 정도에 풀 수 있게 된다면 이후에는 프로그래머스 Level 3에 도전하는 것을 추천한다.
4단계로는 Programmers Level3 N으로 표현이라는 문제가 있다.
N으로 표현 문제는 아직까지 포스팅은 하지 않았지만 DP문제에선 개인적으로 상당히 어려운 축에 속한다고 생각된다.
N번째의 결과를 도출하기 위하여 (1,N-1) / (2,N-2) / ... / (N-1,1) 까지 모두 찾아서 넣어줘야 하기 때문이다.
(링크는 해당 문제에 대한 포스팅이 완료된 후에 수정 예정)
사실 N으로 표현 정도의 문제를 혼자서 스스로 1시간 내에만 해결할 수 있다면 코딩 테스트 수준의 DP문제는 다 풀 수 있을 것이라고 본다.
(주관적이지만 실질적으로 level 4 정도의 문제는 DP로 나오는 것을 본 적이 거의 없다.)
해당 문제를 풀 수 있다면 프로그래머스 level3 등굣길(문제링크) / 백준 1932번이자 프로그래머스 level3 정수삼각형 정도를 풀어 볼 것을 추천한다.
4단계까지도 무난하게 푸시는 분들이라면 분명 이 글을 보지 않고 있을 것이라고 생각되고 사실상 코딩 테스트에 등장하는 DP문제는 쉽게는 3단계 ~ 4단계 수준의 문제들이 나온다고 생각하면 된다.
DP는 결국 점화식과의 싸움이다. 내가 얼마나 빠르게 점화식을 만들어낼 수 있는지를 테스트하는 문제라고 보아도 무방하다.
다만 DP문제를 풀 때 가장 주의해야 할 점은
- C++로 코딩 테스트를 할 경우에는 int 대신 필히 long long 선언
- DP 배열의 초반 값들에 대한 기본값 설정
- 내가 빼먹은 점화식이나 예외가 없는지에 대한 확인
정도의 과정을 거치면 될 것이다.
이상 DP에 대한 정리를 마친다.
'Algorithm > DP' 카테고리의 다른 글
| 1912번 연속합 BOJ 백준 C언어 (0) | 2020.08.26 |
|---|---|
| 2565번 전깃줄 BOJ 백준 C언어 (0) | 2020.08.25 |
| 11054번 가장 긴 바이토닉 부분 수열 BOJ 백준 C언어 (0) | 2020.08.24 |
| 11053번 가장 긴 증가하는 부분수열 BOJ 백준 C언어 (0) | 2020.08.24 |
| 2156번 포도주 시식 BOJ 백준 C언어 (0) | 2020.08.07 |
댓글