동적 계획법
-
Approach Top-down 방식으로 DP를 짜면 중복되는 계산을 줄이면서 계산을 할 수 있을 것이라는 느낌이 든다. 추가적으로 N이 매우 큰 상황이므로, 기존의 DP처럼 메모리를 미리 확보하고 저장하는 방식을 채택할 수 없고 Map 자료 구조를 활용해서 기존의 연산을 수행했는지 여부를 확인해주면 된다. 1. 기존에 연산을 수행한 값 : 메모이제이션을 사용. 즉 Map에서 value값을 그대로 읽어주면 된다. 2. 기존에 연산을 수행하지 않은 값 : Top-down을 활용하여 구해준 뒤, Map에 저장해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; t..
[백준 1351번] [Map / DP] 무한 수열Approach Top-down 방식으로 DP를 짜면 중복되는 계산을 줄이면서 계산을 할 수 있을 것이라는 느낌이 든다. 추가적으로 N이 매우 큰 상황이므로, 기존의 DP처럼 메모리를 미리 확보하고 저장하는 방식을 채택할 수 없고 Map 자료 구조를 활용해서 기존의 연산을 수행했는지 여부를 확인해주면 된다. 1. 기존에 연산을 수행한 값 : 메모이제이션을 사용. 즉 Map에서 value값을 그대로 읽어주면 된다. 2. 기존에 연산을 수행하지 않은 값 : Top-down을 활용하여 구해준 뒤, Map에 저장해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; t..
2021.10.23 -
Approach 이 문제에 대해서 잘 고찰해보면, 어떤 기업이 선택되는 것은 이전 기업에 얼마만큼의 투자했는지에 의해서 결정된다. 따라서 이러한 측면에서 관계식을 통해 표현할 수 있으므로 DP라고 인식해야 한다. Let $dp[i][j]$ : the amount of maximum profit when we investing exactly $j$ until considering $i$'th element $dp[i][j] = \underset{k \in R, \forall k \in [0,j]}{max}(dp[i - 1][j - k] + b[i][k])$ 즉, i번째 기업까지를 고려해서 투자할 때, i - 1번째 까지의 투자 데이터를 가지고 있으면 된다. 그렇게 되면 투자 금액이 동일할 때, 최대의 이익..
[백준 2552번] [동적 계획법] 기업투자Approach 이 문제에 대해서 잘 고찰해보면, 어떤 기업이 선택되는 것은 이전 기업에 얼마만큼의 투자했는지에 의해서 결정된다. 따라서 이러한 측면에서 관계식을 통해 표현할 수 있으므로 DP라고 인식해야 한다. Let $dp[i][j]$ : the amount of maximum profit when we investing exactly $j$ until considering $i$'th element $dp[i][j] = \underset{k \in R, \forall k \in [0,j]}{max}(dp[i - 1][j - k] + b[i][k])$ 즉, i번째 기업까지를 고려해서 투자할 때, i - 1번째 까지의 투자 데이터를 가지고 있으면 된다. 그렇게 되면 투자 금액이 동일할 때, 최대의 이익..
2021.07.12 -
i번째까지의 집을 칠하기 위한 비용을 구하기 위해서는 i - 1번째 집의 색칠 상태가 필요하다 즉, dp[i][0~3] = i번째 index까지 칠했을 때 필요한 비용 (단, i번쨰 index를 칠한 색이 0이면 R, 1이면 G, 2이면 B) 따라서 점화식을 세워보면 구하고자 하는 답을 간단하게 구할 수 있다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; int dp[1001][3]; int main(void){ fastio; memset(dp, 0, sizeof(dp)); int n; cin >> n; cin >> dp[0][0] >> dp[0][1] >> dp[0][2..
[백준 1149번] [동적 계획법] RGB 거리i번째까지의 집을 칠하기 위한 비용을 구하기 위해서는 i - 1번째 집의 색칠 상태가 필요하다 즉, dp[i][0~3] = i번째 index까지 칠했을 때 필요한 비용 (단, i번쨰 index를 칠한 색이 0이면 R, 1이면 G, 2이면 B) 따라서 점화식을 세워보면 구하고자 하는 답을 간단하게 구할 수 있다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; int dp[1001][3]; int main(void){ fastio; memset(dp, 0, sizeof(dp)); int n; cin >> n; cin >> dp[0][0] >> dp[0][1] >> dp[0][2..
2021.02.19 -
문제 자체는 그렇게 어렵지 않다. i번째에서 거리는 사실상 i-1번째의 상태에 의해서 결정되는 양상으로 진행된다. 추가적으로 조건을 잘 살펴보면 i분째 상태는 지침지수와 운동상태인지/쉬는 상태인지 여부에 따라 결정된다. 따라서 이러한 측면에서 3차원 DP가 필요하게 된다. dp[i][j][k] = i번째 분이 지났을 때 지침 지수가 j일때 달린 거리(단, k가 0이면 i번째 분일 때 쉰 상태, 1이면 달린 상태) 그리고 조건을 활용해서 점화식을 잘 세우면 다음과 같다. (단, d[i]는 i번째분에서 달릴 경우 갈 수 있는 거리) 1) 현재 움직히고 있는 상황인 경우(k가 1) dp[i][j][1] = dp[i - 1]j - 1][1] + d[i]가 기본적인 상황이다. 단, 만약 j가 1인 경우에는 dp[..
[백준 1757번] [동적 계획법] 달려달려문제 자체는 그렇게 어렵지 않다. i번째에서 거리는 사실상 i-1번째의 상태에 의해서 결정되는 양상으로 진행된다. 추가적으로 조건을 잘 살펴보면 i분째 상태는 지침지수와 운동상태인지/쉬는 상태인지 여부에 따라 결정된다. 따라서 이러한 측면에서 3차원 DP가 필요하게 된다. dp[i][j][k] = i번째 분이 지났을 때 지침 지수가 j일때 달린 거리(단, k가 0이면 i번째 분일 때 쉰 상태, 1이면 달린 상태) 그리고 조건을 활용해서 점화식을 잘 세우면 다음과 같다. (단, d[i]는 i번째분에서 달릴 경우 갈 수 있는 거리) 1) 현재 움직히고 있는 상황인 경우(k가 1) dp[i][j][1] = dp[i - 1]j - 1][1] + d[i]가 기본적인 상황이다. 단, 만약 j가 1인 경우에는 dp[..
2021.01.27 -
잘 생각해보면 10^6까지이므로 충분히 모두 다 조사해도 시간안에 무조건 들어온다. 다만, 중복되는 계산이 엄청나게 많을 것 처럼 보이므로 DP를 활용해서 중복되는 계산을 줄이는 것이 이 문제의 핵심이다. "dp[n] : 정수 N이 주어졌을 때 연산을 활용해서 1을 만들 수 있는 횟수의 최솟값" 이라 잡으면 점화식은 dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3]이다. 다만, dp[1] = 0, dp[2] = 2; dp[3] = 4는 Base case이므로 따로 넣어준다. #include #include #include #include using namespace std; int dp[1000001]; int recursion(int n){ if(n == 1 || n == 2 ..
[백준 1463번] [동적 계획법] 1로 만들기잘 생각해보면 10^6까지이므로 충분히 모두 다 조사해도 시간안에 무조건 들어온다. 다만, 중복되는 계산이 엄청나게 많을 것 처럼 보이므로 DP를 활용해서 중복되는 계산을 줄이는 것이 이 문제의 핵심이다. "dp[n] : 정수 N이 주어졌을 때 연산을 활용해서 1을 만들 수 있는 횟수의 최솟값" 이라 잡으면 점화식은 dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3]이다. 다만, dp[1] = 0, dp[2] = 2; dp[3] = 4는 Base case이므로 따로 넣어준다. #include #include #include #include using namespace std; int dp[1000001]; int recursion(int n){ if(n == 1 || n == 2 ..
2021.01.27 -
dp[n] : 정수 n을 1, 2, 3의 합으로 나타내는 방법 점화식 dp[n] = dp[n - 1] + dp[n - 2] + dp[n -3] 단, dp[1] = 1, dp[2] = 2, dp[3] = 4는 Base input 값이므로 따로 설정해준다. 잘 생각해보면 시작은 1, 2, 3일수 밖에 없고 그 뒤는 dp의 다른 값으로 표현함으로써 점화식을 세울 수 있다. #include #include #include #include typedef long long ll; using namespace std; ll dp[1000001]; ll sum(int n){ if(n == 1 || n == 2 || n == 3) return dp[n]; if(dp[n - 1] == 0) sum(n - 1); retur..
[백준 15988번] [동적 계획법] 1, 2, 3 더하기 3dp[n] : 정수 n을 1, 2, 3의 합으로 나타내는 방법 점화식 dp[n] = dp[n - 1] + dp[n - 2] + dp[n -3] 단, dp[1] = 1, dp[2] = 2, dp[3] = 4는 Base input 값이므로 따로 설정해준다. 잘 생각해보면 시작은 1, 2, 3일수 밖에 없고 그 뒤는 dp의 다른 값으로 표현함으로써 점화식을 세울 수 있다. #include #include #include #include typedef long long ll; using namespace std; ll dp[1000001]; ll sum(int n){ if(n == 1 || n == 2 || n == 3) return dp[n]; if(dp[n - 1] == 0) sum(n - 1); retur..
2021.01.27 -
재미있는 문제이다. 15는 3의 배수와 5의 배수 성질을 모두 가지고 있다. 즉 자릿수를 다 더한것이 3의 배수이고, 끝이 5아니면 0이다. 이러한 성질을 이용해서 DP로 풀어주면 쉽게 해결할 수 있다. 잘 생각해보면 N번째 자리는 무조건 1, 5로 시작할 수 밖에 없다. 마찬가지로 N-1번쨰 자리는 무조건 1, 5로 시작할 수 밖에 없다. 이를 활용하여 자릿수가 3이라는 것과 결부지어 생각해보자 "DP[n] : n번째 자리일 때 15배수의 갯수"로 잡았다고 하였을 때 맨 앞자리가 15로 시작하게 되면 뒤는 3의 배수이면서 자리가 n-2번쨰 자리를 만족하기만 하면 되므로 이는 DP[n-2]와 동치이다. 맨 앞자리가 51로 시작해도 마찬가지이다. 계속해서 수형도를 그려나가면서 가질 수 있는 경우의 수를 전..
[백준 20500번] [동적 계획법] Ezreal 여눈부터 가네 ㅈㅈ재미있는 문제이다. 15는 3의 배수와 5의 배수 성질을 모두 가지고 있다. 즉 자릿수를 다 더한것이 3의 배수이고, 끝이 5아니면 0이다. 이러한 성질을 이용해서 DP로 풀어주면 쉽게 해결할 수 있다. 잘 생각해보면 N번째 자리는 무조건 1, 5로 시작할 수 밖에 없다. 마찬가지로 N-1번쨰 자리는 무조건 1, 5로 시작할 수 밖에 없다. 이를 활용하여 자릿수가 3이라는 것과 결부지어 생각해보자 "DP[n] : n번째 자리일 때 15배수의 갯수"로 잡았다고 하였을 때 맨 앞자리가 15로 시작하게 되면 뒤는 3의 배수이면서 자리가 n-2번쨰 자리를 만족하기만 하면 되므로 이는 DP[n-2]와 동치이다. 맨 앞자리가 51로 시작해도 마찬가지이다. 계속해서 수형도를 그려나가면서 가질 수 있는 경우의 수를 전..
2021.01.27 -
처음에 접근한 방식은 다음과 같다. # 처음에 접근한 방법 일단 문제를 이해하면 전체 트리의 부분 트리 중 원소의 갯수가 K인 것의 갯수를 구하라는 것과 동치라는 사실을 쉽게 이해할 수 있다. 또한 트리라는 것을 감안할 때 DFS를 이용하여 루트가 밑쪽에 위치한 트리의 원소의 갯수를 활용하여 루트가 위쪽에 위치한 트리의 원소의 갯수를 도출시킬 수 있다는 사실을 파악하였다. 따라서 이러한 속성을 활용하여 dp[i][j]를 i를 Root node로 하고 해당 트리에 속한 원소의 갯수가 j를 만족하는 갯수라고 설정하였다. 이를 바탕으로 DFS를 타고 위로 올라가면서 점화식을 도출하려고 시도하였다. 다만 이 방법의 문제는 점화식을 세우는 것에 무리가 많다는 점이다. dp[i][j]를 구하기 위해서는 i 노드의 ..
[백준 12995번] [동적 계획법] 트리나라처음에 접근한 방식은 다음과 같다. # 처음에 접근한 방법 일단 문제를 이해하면 전체 트리의 부분 트리 중 원소의 갯수가 K인 것의 갯수를 구하라는 것과 동치라는 사실을 쉽게 이해할 수 있다. 또한 트리라는 것을 감안할 때 DFS를 이용하여 루트가 밑쪽에 위치한 트리의 원소의 갯수를 활용하여 루트가 위쪽에 위치한 트리의 원소의 갯수를 도출시킬 수 있다는 사실을 파악하였다. 따라서 이러한 속성을 활용하여 dp[i][j]를 i를 Root node로 하고 해당 트리에 속한 원소의 갯수가 j를 만족하는 갯수라고 설정하였다. 이를 바탕으로 DFS를 타고 위로 올라가면서 점화식을 도출하려고 시도하였다. 다만 이 방법의 문제는 점화식을 세우는 것에 무리가 많다는 점이다. dp[i][j]를 구하기 위해서는 i 노드의 ..
2021.01.15