dp

[골3] 7579 - 앱

#include #include #include #include using namespace std; using ll = long long; #pragma region 상하좌우 / 위치 const pair dir[] { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 }, }; #define y first #define x second #pragma endregion #pragma region 빠른 입출력 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion #define MAX 10000 int main() { FAST_IO(); int n,..

[골4] 17404 - RGB거리 2

#include #include #include #include using namespace std; using ll = long long; #pragma region 상하좌우 / 위치 const pair dir[] { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 }, }; #define y first #define x second #pragma endregion #pragma region 빠른 입출력 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion #define MAX 1001 int main() { FAST_IO(); int col..

[골5] 16500 - 문자열 판별

#include #include using namespace std; #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion int main() { string a[100]; string s; int dp[101]; int n; cin >> s >> n; for (int i = 0; i > a[i]; int sl = s.length(); dp[sl] = 1; for (int i = sl - 1; i >= 0; i--) { for (int j = 0; j

[골3] 1958 - LCS 3

#include #include using namespace std; #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion #define MAX 101 int dp[MAX][MAX][MAX]; int max(int a, int b, int c) { return max(a, max(b, c)); } int main() { FAST_IO(); string s1, s2, s3; cin >> s1 >> s2 >> s3; int sz1 = s1.length(), sz2 = s2.length(), sz3 = s3.length(); f..

[실4] 15489 - 파스칼의 삼각형

dp를 활용했다 #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion #include using namespace std; #define SIZE 30 int dp[SIZE + 1][SIZE + 1]; int main() { FAST_IO(); int r, c, w; cin >> r >> c >> w; dp[1][1] = 1; for (int i = 1; i

DP(동적계획법)을 이용한 이항계수 (Binomial Coefficient)

이항계수는 다음과 같이 표현되며 다음과 같은 성질을 따른다. int binomial(int n, int k) { if (k == 0 || k == n) { return 1; } return binomial(n - 1, k) + binomial(n - 1, k - 1); } 이렇게 간단하게 구현 가능하지만, 효율적이지는 않다. 알고리즘을 재귀호출하면서 이미 했던 계산을 반복해서 수행하기 때문이다 하지만 동적프로그래밍을 이용하면 중복되는 부분을 커버하여 효율적인 알고리즘을 만들 수 있다. Divide and conquer가 top-down 방식이였다면 dynamic progr..

[골5] 2294 - 동전2

#include #include #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion using namespace std; int main() { FAST_IO(); int n, k; cin >> n >> k; vector v(n), dp(k + 1); for (int i = 0; i > v[i]; for (int i = 1; i

최장 증가 부분 수열 (LIS)

개념 어떤 임의의 수열이 주어졌을 때, 수열에서 앞에서부터 차례대로 몇 개의 숫자들을 뽑아서 부분수열을 만들 수 있다. 이렇게 만들 수 있는 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)라고 한다. 예를 들어 [5, 2, 1, 4, 3, 5] 라는 수열이 있다고 가정해보자. 해당 수열에서 최장 증가 부분 수열에 해당하는 수열은 무엇일까? 세번째에 있는 숫자 1을 꺼낸다. 다섯번째에 있는 숫자 3을 꺼낸다. 여섯번째에 있는 숫자 5를 꺼낸다. 이렇게 만들어진 수열 [1, 3, 5]가 위 수열에서 만들 수 있는 최장 증가 부분 수열에 해당하고 길이는 3이 된다. 구할 수 있는 방법에는 크게 2가지가 있고 시간 복잡도에서..

[골5] 12865 - 평범한 배낭

#include #include #include using namespace std; #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion vector w, v; vector dp; int main() { FAST_IO(); int n, k; cin >> n >> k; w.resize(n + 1); v.resize(n + 1); dp.resize(n + 1, vector(k + 1)); for (int i = 1; i > w[i] >> v[i]; for (int i = 1; i

[실1] 15724 - 주지수

#include #include using namespace std; #define SIZE 1050 int n, m, t, arr[SIZE][SIZE]{ 0 }; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 1; i a; arr[i][j] = a + arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1]; } } cin >> t; while (t--) { int x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2; cout