동적계획법
-
백준 14501) 퇴사 (실버.3)알고리즘/백준 2022. 7. 15. 21:26
https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 먼저 문제의 조건을 확인해보자. 1) 직업이 상담사인 사람이 n+1일 째에 퇴사를 한다. 2) 각각의 상담에는 개별의 시간이 걸리기 때문에 다음 상담은 이전 상담이 끝나고 나서 진행할 수 있다. 3) 퇴사날 까지 일을 수행할 때 상담사가 벌 수 있는 최대 이익을 구한다. 먼저 제일 먼저 생각했던 방법은 dfs를 이용해서 상담이 가능한 모든 경우의 수를 구하고 최대 이익을 구하는 방법이었다. 만약 첫번째 상담을 하기로 했으면 그 다음 상담이 가능한 경우는 첫번째 상담일 수가 지난 후일 것이기 때문에 범위는 range(idx, n)으로 ..
-
백준 1904번) 동적계획법 1 - 01.타일알고리즘/백준 2021. 1. 29. 21:03
이코테에 있던 문제와 매우 유사한 문제. #include #include #include #include #define INF 1e9 using namespace std; int d[1000001]; int n; int main() { cin >> n; d[0] = 0; d[1] = 1; d[2] = 2; d[3] = 3; for (int i = 4; i < n + 1; i++) { d[i] = (d[i - 2] * 2 + d[i - 3]) % 15746; } cout
-
알고리즘 문제 해결 전략 - 9.7) k번째 최대 증가 부분 수열알고리즘 2021. 1. 4. 11:29
알고리즘 문제 해결 전략 책의 k번째 최대 증가 부분 수열. (동적계획법_테크닉) 기존에 풀었던 LIS문제와 달리 k번째 최대 길이 수열을 출력하는 문제였다. #include #include #include #include #include #include using namespace std; const int MAX = 2000000000 + 1;//k번째보다 1개 더 큰수 int n; int cacheLen[501], cacheCnt[501], S[500]; int lis(int start) {//S[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환 int& ret = cacheLen[start + 1];//메모이제이션 if (ret != -1) return ret; ret = 1; //항..
-
알고리즘 문제 해결 전략 - 9.6) 모스 부호 사전알고리즘 2021. 1. 4. 11:05
알고리즘 문제 해결 전략 책의 동적계획법_테크닉의 예제문제 동적계획법을 사용하는 방법 중에서도 k-1번째까지의 경우부터 1번째 경우를 구하는 방법을 택하도록 한다. #include #include #include #include #include #include using namespace std; int skip;//얘를 건너띄고 출력한다. const int M = 1000000100;//오버플로우를 막기 위해서 이보다 큰 값은 구하지 않는다(k+100) int bino[201][201];//이항계수(n, m 개의 '-''o'를 뽑을 경우의 수 void calcBino() {//이항계수표를 미리 계산해 놓자 memset(bino, 0, sizeof(bino));//미리 0으로 초기화 해 놓고 for (i..