본문 바로가기

다이나믹 프로그래밍32

[백준 11053] 가장 긴 증가하는 부분 수열 [Python] 풀이 LIS (Longest Increasing Subsequence)는 최장 증가 부분 수열로, N개의 원소에 대해 요소를 골라 만든 부분 수열을 만들 때 각 원소가 이전 요소보다 큰 원소로 이루어진 부분 수열을 의미한다. 즉, 가장 긴 비연속 부분 수열의 길이를 알아내면 된다. 그렇다면, LIS는 어떻게 만들어 지는가? 기본적으로 위에서 언급했 듯 이전 요소보다 큰 요소가 나오면 된다. 문제의 입력에서 알 수 있듯 항상 증가만 하는 요소로 주어지지 않는다. 아래 그림을 보자. 입력받은 배열 A와, 배열에 대한 LIS 길이를 기록할 dp배열이 있다. 그 아래에는 단순히 이전 요소보다 큰 요소가 나오는 경우만 기록한 Increasing Subsequence이다. 첫 번째 경우 10 - 20 - 30 - .. 2023. 4. 29.
[백준 17404] RGB거리 2 [C] 풀이 "백준 1149, RGB거리"에 조건이 추가된 문제이다. 입력받은 비용들을 여러 번 사용해야 하고, 처음에 고른 색에 따라 최소비용을 계산해주어야 한다. 소스코드 #include #define MAX 1000001 #define MIN(a,b) (a < b ? a : b) int main(){ int N, result = MAX; scanf("%d", &N); int cost[N][3], min[3] = {0,}, old[3] = {0,}; for (int i = 0; i < N; i++) scanf("%d %d %d", &cost[i][0], &cost[i][1], &cost[i][2]); for (int i = 0; i < 3; i++){ old[0] = old[1] = old[2] = MAX;.. 2021. 9. 5.
[백준 7579] 앱 [C] 풀이 입력받은 비용들의 총 합을 구해주고, 비용별로 확보할 수 있는 메모리의 최댓값을 구해야 한다. for (int i = 0; i = c[i]; cost--) dp[cost] = max(dp[cost], dp[cost-c[i]] + m[i]); 그 후 입력받은 M만큼의 메모리 이상을 확보하는 비용을 찾아 출력하면 된다. 소스코드 #include #define MAX 101 #define max(a, b) a > b ? a : b int c[MAX], m[MAX], dp[10001]; int main(){ int N, M; scanf("%d %d", &N, &M); for (int i = 0; i < N; i++) scanf("%d", &.. 2021. 9. 2.
[백준 11402] 이항 계수 4 [C] 풀이 Fermat’s little theorem을 기반으로 한 Lucas' theorem으로 풀이했다. Lucas' theorem는 다음과 같다. 쉽게, nCk를 M으로 나눈 나머지를 구하기 위해서는 N과 K를 M진 전개해 얻은 각 자릿수의 조합끼리 곱하고 M으로 나누면 된다. ex) input : 100 45 13 100 = 13*7 + 1*9 45 = 13*3 + 1*6 int result = 1; while (N || K){ result = result*nCk(N%M, K%M, M) %M; N /= M, K /= M; } nCk는 Fermat’s little theorem으로 구했다. 소스코드 #include int nCk(int N, int K, int M){ int A = 1, B = 1; fo.. 2021. 8. 28.
[백준 1005] ACM Craft [C] 풀이 건물 W를 완성하기 위해서는 건물 1에서 건물 W로 향하는 건물들이 완성되어야 하기 때문에, W값에서 역으로 DFS방식을 사용했다. W에서 1로 향하는 건물들이 모두 건설되어야 하기 때문에 D값이 가장 큰 값을 time에 넣어주어 반환해야 한다. 좀더 효율적인 탐색을 위해 총 time을 check에 넣는 memoization방식으로 해결했다. 단, D값은 0이상이기 때문에 -1로 초기화해서 사용해야 한다. 소스코드 #include #include #include #define max(a, b) a > b ? a : b int D[1001], N, check[1001]; bool O[1001][1001]; int construction(int c){ if (check[c] != -1) return c.. 2021. 8. 25.
[백준 9252] LCS 2 [C] 풀이 "백준 9251, LCS"에서 LCS를 출력하기위해 사용했던 j, i값을 이용해 문자열이 동일한 경우를 Recursion방식으로 찾았다. 소스코드 #include #define max(a, b) a > b ? a : b int dp[1001][1001]; char str[2][1001]; void LCS(int j, int i){ if (dp[j][i]) if (str[0][i-1] == str[1][j-1]){ LCS(j-1, i-1); printf("%c", str[0][i-1]); }else dp[j-1][i] > dp[j][i-1] ? LCS(j-1, i) : LCS(j, i-1); } int main(){ scanf("%s %s", &str[0], &str[1]); int i, j; for.. 2021. 8. 24.

티스토리툴바