알고리즘 설명
한마디로 설명하면 "캐싱된 재귀문제" 이다.
탑다운 방식(메모이제이션)과 바텀업 방식(반복문)이 있다.
탑다운이 이해하기 쉬우니 탑다운 방식으로 생각해보고 시간초과가 난다면 바텀업으로 변경하자.
연습문제
BOJ_1463번: 1로 만들기
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
예제 입력 1
2
예제 출력 1
1
풀이
#include <bits/stdc++.h>
using namespace std;
int N;
int T_memo[1000004];
int T(int n){
if(n == 1) return 0;
if(T_memo[n] != 0) return T_memo[n];
T_memo[n-1] = T(n-1);
int result = T_memo[n-1];
if(n % 2 == 0){
T_memo[n/2] = T(n / 2);
if(T_memo[n/2] < result) result = T_memo[n/2];
}
if(n % 3 == 0){
T_memo[n/3] = T(n / 3);
if(T_memo[n/3] < result) result = T_memo[n/3];
}
T_memo[n] = result + 1;
return T_memo[n];
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin >> N;
cout << T(N);
return 0;
}팁
base condition일 경우 memo배열에 접근할 필요도 없이 바로 리턴하면 된다.
그 후에 memo배열에 접근한다.
BOJ_9095번: 1,2,3 더하기
1, 2, 3 더하기 성공다국어
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 (추가 시간 없음) 512 MB 148864 98934 69090 65.077%
문제
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.
출력
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
예제 입력 1
3
4
7
10
예제 출력 1
7
44
274
풀이
#include <bits/stdc++.h>
using namespace std;
int memo[12];
int DP(int n){
if (n == 1) return 1;
if (n == 2) return 2;
if (n == 3) return 4;
if (memo[n]) return memo[n];
int result = DP(n-1) + DP(n-2) + DP(n-3);
memo[n] = result;
return result;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int T;
cin >> T;
while(T--){
int n;
cin >> n;
cout << DP(n) << "\n";
}
return 0;
}팁
n의 개수가 작아, 백트래킹으로 풀어도 된다.
BOJ_2579번: 계단 오르기
문제
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.
<그림 1>
예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.
<그림 2>
계단 오르는 데는 다음과 같은 규칙이 있다.
계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
마지막 도착 계단은 반드시 밟아야 한다.
따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.
각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.
입력
입력의 첫째 줄에 계단의 개수가 주어진다.
둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.
출력
첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.
예제 입력 1
6
10
20
15
25
10
20
예제 출력 1
75
풀이
#include <bits/stdc++.h>
using namespace std;
array<int, 304> arr;
int memo[304][4];
int T(int n, int k){
if(n == 1 && k == 1) return arr[1];
if(n == 1 && k == 2) return 0;
if(n == 2 && k == 1) return arr[2];
if(n == 2 && k == 2) return arr[1] + arr[2];
if(memo[n][k]) return memo[n][k];
if(k == 1){
memo[n][1] = max(T(n-2, 1), T(n-2, 2)) + arr[n];
return memo[n][1];
}else{
memo[n][2] = T(n-1, 1) + arr[n];
return memo[n][2];
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> arr[i];
int result = max(T(n, 1), T(n, 2));
cout << result;
// T(N, k): N번째 계단을 밟았을 때의 최대값, k는 연속해서 밟은 계단 수 (1, 2, 3)
return 0;
}팁
점화식이란, 이전항과 현재항과이 관계이다.
현재 계단이 몇 번째 계단인지는 이전 계단이 몇 번째 계단인지를 알아야 한다.
뿐만 아니라, 이전 계단이 연속해서 몇번 밟은 계단인지를 알아야 현재 계단도 그에 대응할 수 있다.
그러므로 상태를 의미하는 인자가 2개이다.
경로 추적
BOJ_12852번: 1로 만들기2
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.
예제 입력 1
2
예제 출력 1
1
2 1
풀이
#include <bits/stdc++.h>
using namespace std;
int dp[1000004];
int pre[1000004];
int T(int n){
if(n == 1) {
return 0;
}
else if(n == 2 || n == 3){
pre[n] = 1;
return 1;
}
if(dp[n]) return dp[n];
int result = T(n-1) + 1;
pre[n] = n-1;
if(n % 2 == 0) {
int temp = T(n/2) + 1;
if(temp < result){
result = temp;
pre[n] = n / 2;
}
}
if(n % 3 == 0){
int temp = T(n/3) + 1;
if(temp < result) {
result = temp;
pre[n] = n / 3;
}
}
dp[n] = result;
return result;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int N;
cin >> N;
// T(N): N이 1이 되기까지의 최소 연산 수
cout << T(N) << "\n";
int cur = N;
while(true){
cout << cur << " ";
if(cur == 1) break;
cur = pre[cur];
}
return 0;
}팁
경로를 추적하려면 경로추적용 배열을 같은 크기만큼 하나 더 만든다.
그리고 T(n)이 정해질때 어느 곳에서 부터 오는 것인지 마킹한다.
마지막에 while문으로 경로를 추적하면 된다.
정수 범위 판단
BOJ_2193번: 이친수
문제
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.
이친수는 0으로 시작하지 않는다.
이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.
예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.
N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다.
출력
첫째 줄에 N자리 이친수의 개수를 출력한다.
예제 입력 1
3
예제 출력 1
2
풀이
#include <bits/stdc++.h>
using namespace std;
array<array<long long, 2>, 92> memo;
long long T(int n, int k){
if(n == 1 && k == 0) return 0;
if(n == 1 && k == 1) return 1;
if(memo[n][k] != -1) return memo[n][k];
long long result;
if(k == 0){
result = T(n-1, 0) + T(n-1, 1);
}else{
result = T(n-1, 0);
}
memo[n][k] = result;
return memo[n][k];
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int N;
cin >> N;
// T(N, k) : N자리의 이친수 개수, k는 연속된 1의 카운트 k in (0, 1)
for(int i = 1; i <= N; i++) fill(memo[i].begin(), memo[i].end(), -1);
long long result = T(N, 0) + T(N, 1);
cout << result;
return 0;
}팁
T(n)의 값의 범위를 항상 유의하자.
저 위의 T(n)은 피보나치 수열과 비슷하다.
for문으로 최대값으로 계산해보면 수십경 단위가 나온다.
또한, 메모할 때 0이 사용되는 문제라면 -1로 초기화 하자.
최적 부분구조의 다양화
여태까지는 T(n) = T(n-1) + K 와 같이 T(n)은 T(n-1) 또는 T(n-2)처럼 특정 값으로 부터 도출해내었다.
이는 "최적부분구조" 의 특징으로, "큰 문제의 해답에 작은 문제의 해답이 포함된 경우" 를 의미한다.
그러나 특정 상태가 아닌 이전의 모든 상태를 참조하여 현재의 값을 도출 해 내는 경우도 "최적부분구조"로 볼 수 있다.
즉, T(n) = T(n-k) ... + K 가 아니라 T(n) = min(T(1), T(2), ..., T(n-1)) 처럼 이전의 모든 값을 참조하여 현재의 값을 도출 할 수도 있다.
BOJ_11055번: 가장 큰 증가하는 부분 수열
문제
수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.
예제 입력 1
10
1 100 2 50 60 3 5 6 7 8
예제 출력 1
113
풀이
#include <bits/stdc++.h>
using namespace std;
array<int, 1004> arr;
array<int, 1004> memo;
int T(int n){
if(n == 1) return arr[1];
if(memo[n]) return memo[n];
int mx = arr[n];
for(int i = 1; i < n; i++){
if(arr[i] < arr[n]) mx = max(mx, T(i) + arr[n]);
}
memo[n] = mx;
return mx;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int N;
cin >> N;
for(int i = 1; i <= N; i++) cin >> arr[i];
// T(N): 1번째부터 N번째 까지의 부분 수열 중 N번째 요소를 포함한 최대 합
int mx = 0;
for(int i = 1; i <= N; i++){
mx = max(mx, T(i));
}
cout << mx;
return 0;
}팁
T(n)이 처음부터 N번째 까지의 범위 중에 N번째 요소를 포함한 최대 값이다.
즉, T(n)은 다음의 후보군을 가진다.
- arr(n) : n번째 요소만 포함
- T(1) + arr(n) : 1번째 까지의 범위 중에 1번째 요소가 포함된 최대 값 + n번째 요소
- T(2) + arr(n) : 2번째 까지의 범위 중에 2번째 요소가 포함된 최대 값 + n번째 요소
- T(3) + arr(n) : 3번째 까지의 범위 중에 3번째 요소가 포함된 최대 값 + n번째 요소
...
이렇게 T(1) + T(n)까지의 모든 값을 구해 메모이제이션을 한다.
마지막에 출력할 값은 T(n)이 아니다.
가장 큰 수열의 끝나는 부분은 모르니까 for문으로 T(1)부터 T(n)까지 돌려서 제일 큰 값을 출력한다.
역순 점화식
T(n) = T(n-1) + D 와 같은 점화식이 아닌
T(n) = T(n+1) + D 와 같이 n이 커지는 점화식도 가능하다.
수식에서는 항의 이동을 통해 T(n+1) = T(n) - D 처럼 만들 수 있겠지만, 알고리즘 상에서는 간단하지가 않다.
일반적으로 현재의 값은 이전의 값을 통해 결정이 된다.
하지만 역순 관점의 경우, 현재의 값은 미래의 값을 통해 결정이 된다.
재귀함수의 인자로 구하고자하는 "현재"를 넣지 않고 "과거"를 넣는다.
또한 base condition이 "미래"가 된다.
BOJ_14501번: 퇴사
문제
상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.
오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.
각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.
N = 7인 경우에 다음과 같은 상담 일정표를 보자.
1일 2일 3일 4일 5일 6일 7일
Ti 3 5 1 1 2 4 2
Pi 10 20 10 20 15 40 200
1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.
상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.
또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.
퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.
상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.
둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)
출력
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
예제 입력 1
7
3 10
5 20
1 10
1 20
2 15
4 40
2 200
예제 출력 1
45
풀이
#include <bits/stdc++.h>
using namespace std;
array<int, 16> T;
array<int, 16> P;
array<int, 24> memo;
int N;
int DP(int startDay){
if(startDay > N) return 0;
if(memo[startDay] != -1) return memo[startDay];
int skip = DP(startDay+1);
int mx = skip;
if(startDay + T[startDay] - 1 <= N){
mx = max(P[startDay] + DP(startDay+T[startDay]), mx);
}
memo[startDay] = mx;
return mx;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin >> N;
for(int i = 1; i <= N; i++){
cin >> T[i] >> P[i];
}
fill(memo.begin(), memo.end(), -1);
// DP(day) : day부터 시작하는 최대 수익
cout << DP(1);
return 0;
}팁
startDay부터 시작하는 최대이익을 구할 때
startDay를 포함한 경우와 startDay를 포함하지 않은 경우 중에 큰 값을 구해야 한다.
startDay를 포함한 경우에는 해당 값과 특정 날짜가 지난 이후의 "재귀"값을 구해야 한다.
물론 특정 날짜가 지난 이후의 날짜가 범위를 벗어나면 당연히 포함해서는 안된다.
startDay를 포함하지 않을 때는 그 다음날의 "재귀"값을 구하면 된다.
만약 지금까지처럼 과거 기반으로 풀이를 작성하고자 한다면 날짜 계산이 복잡해진다.
#include <bits/stdc++.h>
using namespace std;
int T[20], P[20], memo[20];
int N;
// DP(day): 1일부터 day일까지 얻을 수 있는 최대 수익
int DP(int day) {
if (day == 0) return 0;
if (memo[day] != -1) return memo[day];
// 상담을 하지 않고 넘어온 경우
int skip = DP(day - 1);
// 상담을 해서 day에 끝나는 경우를 찾음
int take = 0;
for (int i = 1; i <= day; i++) {
if (i + T[i] - 1 == day) {
take = max(take, DP(i - 1) + P[i]);
}
}
return memo[day] = max(skip, take);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) cin >> T[i] >> P[i];
fill(memo, memo + 20, -1);
cout << DP(N);
}day일 까지의 최대값을 구할 때, day를 포함하거나 포함하지 않는 두 경우로 나눠서 생각해야 하는건 앞과 비슷하다.
포함하지 않을 때는 이전날의 재귀값을 이용하면 되지만,
포함할때는 이전날을 특정하기가 복잡하다.
day가 포함할때의 의미가 "상담 시작" 이 아닌, "상담 끝" 이라고 생각해야 한다.
그래서 day에 상담이 끝나도록하는 상담 시작 날짜를 구해야한다.
그리고 그 때의 값과 그 이전의 "재귀 값"을 더한다.
day에 상담이 끝나는 "상담 시작" 날짜가 여러개 일 수 있으므로 for문으로 탐색해서 제일 큰 값을 골라야 한다.
