📝24416번: 피보나치 수 1
문제 설명
피보나치 수 1
해결 방법
동적 계획법의메모이제이션을 활용한다. 메모이제이션이란, 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술을 말한다. 재귀호출을 이용하여 피보나치 수를 구현한 것보다 시간적인 측면에서 훨씬 효율적임을 알 수 있다. 다만 메모리라는 공간 비용을 투입해 계산에 소요되는 시간 비용을 줄이는 방식이기 때문에 메모리를 더 많이 사용한다는 특징이 있다.
💻소스코드
#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
int f_arr[40];
int N;
int re_cnt = 0, dp_cnt = 0; // 재귀호출 카운트, 동적 프로그래밍 카운트
int fib_re(int n) {
if (n == 1 || n == 2) {
re_cnt++;
return 1;
}
else {
// re_cnt++;
return fib_re(n - 2) + fib_re(n - 1);
}
}
void fib_dp(int n) {
f_arr[0] = 1; f_arr[1] = 1;
for (int i = 2; i < n; i++) {
f_arr[i] = f_arr[i - 1] + f_arr[i - 2];
dp_cnt++;
}
}
int main()
{
// 피보나치 수 1
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> N;
fib_re(N);
fib_dp(N);
cout << re_cnt << ' ' << dp_cnt << '\n';
}📝9184번: 신나는 함수 실행
문제 설명
신나는 함수 실행
해결 방법
재귀 호출로 인해 동일한 계산의 반복 수행이 너무 많아져서 시간 초과가 발생하기 때문에 동적 계획법의 메모이제이션을 활용한다. w 함수는 문제에서 그대로 주어져 있다. 크기 [21][21][21]인 3차원 배열 arr을 선언한다. 입력으로 받은 a, b, c 중에서 하나라도 20보다 크다면 w(20, 20, 20)을 반환할 것이기에 크기는 21로도 충분하다. 재귀 호출로만 이루어진 w 함수를 배열을 활용해서 코드를 수정한다. 재귀 함수를 호출할 때 연산을 하는 것이 아닌 미리 저장된 값을 반환한다. 그래서 배열 arr에 해당하는 값이 0이 아니라면 배열 arr에 위치한 값을 출력하고 이외에는 연산을 한 뒤 값을 저장한 후 반환한다.
💻소스코드
#include <iostream>
using namespace std;
int arr[21][21][21]; // memoization
int w(int a, int b, int c) { // 문제에서 주어진 조건
if (a <= 0 || b <= 0 || c <= 0)
return 1;
if (a > 20 || b > 20 || c > 20)
return w(20, 20, 20);
if (arr[a][b][c] != 0) // 이미 저장된 값
return arr[a][b][c];
if (a < b && b < c) {
arr[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
return arr[a][b][c];
}
arr[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
return arr[a][b][c];
}
int main()
{
// 신나는 함수 실행
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int a, b, c;
while (true) {
cin >> a >> b >> c;
if (a == -1 && b == -1 && c == -1)
break;
cout << "w(" << a << ", " << b << ", " << c << ") = ";
cout << w(a, b, c) << '\n';
}
}📝1904번: 01타일
문제 설명
01타일
해결 방법
만들 수 있는 타일 개수의 규칙을 찾기 위해서 N이 1일 때부터 6일 때까지 경우의 수를 나열해 보았다. 그 결과, 타일의 개수가 피보나치 수열 형태를 나타내는 규칙성을 발견했고 f(n) = f(n - 1) + f(n - 2) 점화식을 사용하여 동적 프로그래밍 메모이제이션 기법을 사용해서 해결했다.
💻소스코드
#include <iostream>
using namespace std;
int arr[1000001];
int main()
{
// 01타일
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int N;
cin >> N; // 입력
arr[1] = 1; arr[2] = 2;
for (int i = 3; i <= N; i++) {
arr[i] = (arr[i - 1] + arr[i - 2]) % 15746;
}
cout << arr[N]<< '\n';
}📝9461번: 파도반 수열
문제 설명
파도반 수열
해결 방법
1, 1, 1, 2, 2, 3, 4, 5, 7, 9, ... 규칙을 찾아보니 점화식dp[j] = dp[j - 2] + dp[j - 3]이 도출되었다. 배열을 선언하고 메모이제이션을 활용해서 입력 받은 N에 대한 수를 출력한다. 이 때 자료형이 int면 큰 수를 입력 받았을 때 오버플로우가 발생하기 때문에 long long으로 선언한다.
💻소스코드
#include <iostream>
using namespace std;
long long dp[101]; // int로 하면 틀림
int main()
{
// 파도반 수열
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int N, T; // 입력, 테스트 케이스 수
dp[1] = 1; dp[2] = 1; dp[3] = 1;
cin >> T;
for (int i = 0; i < T; i++) {
cin >> N;
for (int j = 4; j <= N; j++) {
dp[j] = dp[j - 2] + dp[j - 3]; // P(N) 점화식
}
cout << dp[N] << '\n';
}
}📝1912번: 연속합
문제 설명
연속합
해결 방법
입력 받은 숫자들을 저장할 배열 arr, 메모이제이션을 적용할 배열 dp를 선언, max_num은 연속합의 최댓값
dp[i]를 i번째에서 끝나는 제일 큰 연속합이라 할 때, dp[i]는 i - 1 번째에서 끝나는 제일 큰 연속합 + arr[i]의 값dp[i] = dp[i - 1] + arr[i]으로 나타낼 수 있다. 이 때 arr[i]가 더 클 경우도 존재하기 때문에 둘 중 더 큰 값을 dp[i]에 저장한다. 그리고 그 값을 max_num과 비교해서 더 큰 값을 max_num에 저장하고 출력한다.
💻소스코드
#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
// 연속합
ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n; // input
int dp[100000], arr[100000];
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i]; // 입력 받은 숫자들을 arr에 저장
}
int max_num = arr[0];
dp[0] = arr[0];
for (int i = 1; i < n; i++) { // dp는 i번째에서 끝나는 제일 큰 연속합
dp[i] = max(dp[i - 1] + arr[i], arr[i]); // i번째에서 끝나는 제일 큰 연속합과 arr[i] 중 큰 값
max_num = max(dp[i], max_num); // 연속합의 최댓값과 dp[i]의 값 중 더 큰 값
}
cout << max_num << '\n';
}📝1149번: RGB거리
문제 설명
RGB거리
해결 방법
입력을 저장하기 위한 배열rgb[1001][3]를 선언: 행은 집의 수, 열은 각각 빨강, 초록, 파랑을 칠했을 때 비용을 의미한다.
r, g, b를 각각 입력 받아서rgb[i][0]에 i번째 집을 빨간색으로 칠했을 때의 최소 비용,rgb[i][1]에 i번째 집을 초록색으로 칠했을 때의 최소 비용,rgb[i][2]에 i번째 집을 파란색으로 칠했을 때의 최소 비용을 저장한다. i번째 집을 칠했을 때의 최소 비용을 구하기 위해서 i - 1 번째 집을 i 번째 집과는 다른 색으로 칠했을 때의 비용 중 더 작은 값을 구해서 현재 집을 칠할 색의 비용과 더해주면 된다. 예를 들어 2번째 집을 빨간색으로 칠했을 때rgb[2][0]의 최소비용은r + min(rgb[1][1], rgb[1][2])이다. 전체 집을 칠했을 때의 최소비용min_cost은 현재까지 집을 칠했을 때의 비용 중 최소 비용을 구하면 된다.
💻소스코드
#include <iostream>
#include <algorithm>
using namespace std;
int rgb[1001][3]; // 입력을 저장하기 위한 배열
int main()
{
// RGB거리
ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int N;
int r, g, b;
int min_cost = 0; // 최소비용
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> r >> g >> b;
rgb[i][0] = r + (min(rgb[i - 1][1], rgb[i - 1][2]));
rgb[i][1] = g + (min(rgb[i - 1][0], rgb[i - 1][2]));
rgb[i][2] = b + (min(rgb[i - 1][0], rgb[i - 1][1]));
min_cost = min(rgb[i][0], min(rgb[i][1], rgb[i][2]));
}
cout << min_cost << '\n';
}