개발하는 리프터 꽃게맨입니다.
다이나믹 프로그래밍 솔루션:: 백준 11051, 9251, 1520 본문
1. 문제 10051
https://www.acmicpc.net/problem/11051
1) 주의해야 할 점
모듈러 계산에서는 나눗셈을 정의하지 않기 때문에
팩토리얼을 통한 조합 계산이 문제 조건상 허용되지 않는다.
그렇기에 파스칼 삼각형을 이용해서 풀어야 한다.
2) 탑-다운 풀이
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 10'007
int N, K;
vector<vector<int>> dp;
int Combine(int n, int k)
{
if (dp[n][k] != -1)
return dp[n][k];
if (k == 0 || n == 0 || k == n)
return dp[n][k] = 1;
if (k == 1)
return dp[n][k] = n;
return dp[n][k] = (Combine(n - 1, k - 1) + Combine(n - 1, k)) % MAX;
}
int main()
{
cin >> N >> K;
dp.resize(N+1, vector<int>(N + 1, -1));
cout << Combine(N, K);
return 0;
}
3) 바텀-업 풀이
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 10'007
int N, K;
vector<vector<int>> dp;
int main()
{
cin >> N >> K;
dp.resize(N+1, vector<int>(N + 1, 1));
for(int i=2;i<=N;i++)
for (int j = 1; j < i; j++)
dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % MAX;
cout << dp[N][K];
return 0;
}
2. 문제 10051
1. 주의해야 할 점
분할정복적 사고가 핵심인 문제
2차원 표를 만들어서 고민해보면 푸는데 도움이 된다.
2. 탑-다운 방식
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 10'007
int N, K;
string str1, str2;
vector<vector<int>> dp;
int Solution(int x, int y)
{
if (x == -1 || y == -1)
return 0;
if (dp[x][y] != -1)
return dp[x][y];
if (str1[x] == str2[y])
return dp[x][y] = Solution(x - 1, y - 1) + 1;
return dp[x][y] = max(Solution(x - 1, y), Solution(x, y - 1));
}
int main()
{
cin >> str1 >> str2;
str1 = str1;
str2 = str2;
dp.resize(str1.size() + 1, vector<int>(str2.size() + 1, -1));
cout << Solution(str1.size()-1, str2.size() - 1);
return 0;
}
3. 바텀-업 방식
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 10'007
int N, K;
string str1, str2;
vector<vector<int>> dp;
int main()
{
cin >> str1 >> str2;
str1 = " " + str1;
str2 = " " + str2;
dp.resize(str1.size() + 1, vector<int>(str2.size() + 1, 0));
for (int i = 1; i < str1.size(); i++)
{
for (int j = 1; j < str2.size(); j++)
{
if (str1[i] == str2[j])
{
dp[i][j] = dp[i - 1][j-1] + 1;
}
else
{
dp[i][j] = max(dp[i-1][j], dp[i][j - 1]);
}
}
}
auto it = *max_element(dp.begin(), dp.end());
cout << *max_element(it.begin(), it.end());
return 0;
}
3. 문제 1520
1. 주의해야 할 점
전수조사를 해야하는 문제이기 때문에 BFS 탐색으로는 풀기 어려운 문제다.
그렇기에 DFS를 사용하는 것이 문제푸는데 도움이 될 것이고,
DFS 특성상 stack으로 구현하는 것 보다는 재귀로 구현하는 것이 훨씬 깔끔하다.
처음 문제를 만났을 때 과연 이 문제에서 DP를 어떻게 활용할까에 대한 고민을 길게했다.
이 문제는 어디서 중복되는 계산이 발생하는지 인지하는 것이 핵심인 문제이다.
2. 탑-다운 방식 방식
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int table[501][501];
int visited[501][501];
int dp[501][501];
int M, N;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int Solution(int y, int x)
{
if (y == M - 1 && x == N - 1)
return 1;
if (visited[y][x])
return dp[y][x];
visited[y][x] = true;
for (int dir = 0; dir < 4; dir++)
{
int nX = x + dx[dir];
int nY = y + dy[dir];
if (nY < 0 || nX < 0 || nY >= M || nX >= N)
continue;
if (table[nY][nX] >= table[y][x])
continue;
dp[y][x] = dp[y][x] + Solution(nY, nX);
}
return dp[y][x];
}
int main()
{
cin >> M >> N;
for(int i=0;i<M;i++)
for (int j = 0; j < N; j++)
cin >> table[i][j];
cout << Solution(0, 0);
return 0;
}
'스터디 자료' 카테고리의 다른 글
[알고리즘 스터디 솔루션] 17404, 10282, 13418 (2) | 2024.05.29 |
---|---|
(공사중) 동적 계획법, 다이나믹 프로그래밍 (공사중) (0) | 2024.05.22 |
[알고리즘 스터디] 컴퓨터 과학에서 말하는 그래프 - 下 (1) | 2024.04.28 |
[알고리즘 스터디] 컴퓨터 과학에서 말하는 그래프 - 上 (1) | 2024.04.27 |