dp
연속합 _백준 1912
백준 1912 연속합 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 연속된 수 중, 가장 큰 합을 구하는 문제이다. 크게 어려운 문제는 아니라서, 꽤 빨리 풀기도 한 문제이다. d[i] 를 구할 때, d[i-1] + a[i](수열의 i번째 수) 와 a[i]를 비교하여 더 큰 값을 d[i]로 하고, 배열 d의 최댓값을 출력하면 되는 문제이다. #include using namespace std; int d[100001]; int nums[100001]; int main(void) { int num; scanf("%d", &num); for (int i = 0; i < n..
가장 긴 증가하는 부분 수열 4_ 백준 14002
백준 14002 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 앞에서 작성했던 가장 긴 증가하는 부분 수열의 심화버전의 문제이다. (이전문제는 아래 링크로 들어가면 된다) 2020/07/22 - [백준 문제풀이] - 가장 긴 증가하는 부분 수열_ 백준11053 위 문제에서 조금 더 어려워 진 점은, 가장 긴 증가하는 부분 수열을 출력해야하는 점이다. 즉, 수열의 순서를 저장할 필요가 있는 것인데, 나는 11053 문제의 코드에 더 덧붙이는 방식으로 풀었으므로 (두 문제의 연관성이 크므로, 이 순서로 푸는 것을 추천한다) 11053 문제에서 생각했던 점화식의 흐름에 초점을 맞추어 진행했다. 각각의 부분수열을 저장할 수는 없으므로, d[i]를 구하면서, 하나의 배열을 ..
가장 긴 증가하는 부분 수열_ 백준11053
백준 11053 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오 수열의 길이와 수열의 값을 입력받아 가장 긴 증가하는 부분수열을 구하는 문제이다. 이 문제 역시 DP 문제 이므로, d[i]를 구하는 것이 중요한데, d[1] = 1 d[i]와 d[i-1] ~ d[1]의 관계 ← 이 부분에서 주의해서 살펴보았다. '가장 긴 증가하는 부분수열' 이 되기 위해서는 앞에 있는 수 중 i번째 숫자보다 작으며, d의 값이 가장 큰 것을 찾아야 한다. 그 이후에는, 그 값(d[j])에 1을 더하면, 우리가 구해야 하는 d[i]값이 나온다. 해당 내용에 맞추어 코드를 짜면 아래와 같다. #include using namespace std; int nums[1001]; int d[100..
1, 2, 3 더하기 5_ 백준15990
15990 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 단, 같은 수를 두 번 이상 연속해서 사용해서는 안됩니다. 1,2,3더하기의 심화버전인 문제이다. n이 주어졌을 때 1,2,3만의 합으로 구하는 것이며, 같은 수를 두번 이상 연속해서 사용하면 안된다는 조건이 추가되었다. 그렇다면, 같은 수인지 아닌지 확인하기 위한 추가적인 절차가 필요하다. 이를 위해서 정수의 값을 저장할 부분을 이차원 리스트로 만들었다. 즉, n이 주어졌을 1,2,3의 합으로 나타내는 경우의 수를 d[n]이라 하면 d[n] = d[1] + d[n-1] d[n] = d[2] + d[n-2] d[n] = d[3] + d[n-3] 이므로, n이 주어졌을 때 위의 세 사례로 나..
카드구매하기 _ 백준 11052& 백준 16194
이번에도 역시 DP와 관련된 문제이다. 11052 카드 N개를 구매하는 비용의 최대값을 구하는 문제. 카드 N개를 구매하는 비용의 최대값을 d[N]이라고 하면 d[N] = max(d[i] + d[N-i]) 이다. 그러므로 d[1]의 값을 넣고, 그 다음 값부터는 for문을 통해서 확인하며 수행한다. 여기서 j의 값이 i/2인 이유는 i/2이후부터는 d[j] + d[i-j]의 순서만 다를 뿐, 결과는 같기 때문에 계산을 줄이고자 값을 제한한 것이다. //11502 - 카드 구매하기 #include using namespace std; int d[1001]; int f[1000]; int main(void) { int count; int num; int i = 1; scanf("%d", &count); nu..
2xn 타일링 _ 백준 11726, 백준 11727
11726번 문제와 11727문제는 하나의 조건만 달라서 한번에 정리해보려고 한다. 11726 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 2×n 타일의 우측에 칸을 채워넣는 방식으로 생각하면, 방법은 두가지이다. 1×2가 들어가게 되면 한칸이 완전히 차게 되고, 2 X n-1이 남는다. → d[n-1] 2 X 1 이 들어가게 되면 두칸이 차게되고, 2 X n-2가 남는다 → d[n-2] DP문제이니만큼, 점화식을 세워보면, 2 x n 크기의 타일을 채우는 방법의 수를 d[n]이라고 하면 d[n] = d[n-1] + d[n-2]이 되는 것이다. 여기서 조금 헤맨 부분을 이야기하자면, 그냥 이렇게 세워서 문제를 풀다보니 계속 답이 틀렸다고 하는 문제가 ..
1로 만들기_ 백준 1463
1로만들기는 DP를 활용해서 푸는 문제이다. 문제에서 제시되는 내용으로는 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이고, 이를 활용하여 정수 N이 주어졌을 때, 연산 세 개를 적절히 사용해서 1을 만드는 연산횟수의 최솟값을 구하는 것이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 그러면 D[i]가 i를 1로 만드는데 필요한 최소 연산횟수라고 했을 때, D[i] = D[i/3] + 1 D[i] = D[i/2] + 1 D[i] = D[i-1] + 1 셋중에 하나가 최솟값으로 들어가게 된다. 기본적으로 D[1] = 0이므로, 이를 기반으로 해서 bottom up 방식으로 코드를 구현하면 아래와 같다. #include #include u..
다이나믹 프로그래밍 기초
오늘부터는 다이나믹 프로그래밍 (DP)와 관련되어서 문제를 쭉 풀어보려고 한다. 다이나믹 프로그래밍의 구현 방식에는 크게 두가지 방법이 있다. 1. Top-down 방식 : 재귀를 활용해서, 큰 문제를 작은 문제로 쪼개는 방식 (ex 피보나치) 2. Bottom-up 방식 : 반복문을 활용해서, 작은 문제를 모아 큰 문제를 해결하는 방식 이 두 방식의 시간차이는 경우에 따라 다르게 때문에, 일단 둘중에 하나를 먼저 골라서 공부하면서 익숙해지는 것이 중요하다고 한다. 기본적으로는 스택오버플로우와 같은 문제가 발생한다면 이는 시간차이라기보다는 코드의 문제일 가능성이 크기 때문에 일단 기초적인 수준에서는 둘중 하나를 중점적으로 공부하는 것이 중요하다는 것! 다이나믹 문제 풀이의 전략으로는 "문제에서 구하려는 ..