백준 문제풀이
가장 긴 증가하는 부분 수열_ 백준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..
이친수_2193
2193 N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오. 이친수: 이진수중 다음의 두 조건을 만족하는 수. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 그러므로 점화식을 세울 때 우리는 끝의 문자에 따라 d[n][1], d[n][0]으로 나누어 생각하여야 한다. 이친수는 0으로 시작하지 않으므로 초기값은 d[1][1] = 1, d[1][0] = 0 이다. 그렇다면 이 초기값을 기준으로, 나머지 점화식을 세울 수 있다. 여기서는 두번째 조건에 집중하면 된다. 1은 연속해서 사용할 수 없기 때문에 두번째 조건에 집중하면 점화식은 d[n][1] = d[n-1][0], d[n][0] ..
쉬운 계단 수 _ 백준 10844
10844 N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.) 계단 수 : 인접한 모든 자리수의 차이가 1인 수. 여기서 d[n] = 길이가 N인 계단 수의 개수라고 볼 수 있지만, 여기서 우리는 인접한 수의 차이가 1 인것도 고려해야 한다. 그렇다면 마지막 숫자를 배열에 추가하여 d[n][i] = 길이가 n인 계단 수이며, 마지막 숫자가 i인것으로 하여 점화식을 세우면 된다. 처음에 잘못생각해서, 마지막 숫자가 아니라 첫번째 숫자로 생각했더니 문제가 발생했기 때문에... 마지막 숫자라는 것을 유의했으면 좋겠다. 따라서 점화식을 세우면 d[n][i] = d[n-1][i-1] + d[n-1][i+1]이다. 다만, i가 0, 9 일 때에는..
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 방식 : 반복문을 활용해서, 작은 문제를 모아 큰 문제를 해결하는 방식 이 두 방식의 시간차이는 경우에 따라 다르게 때문에, 일단 둘중에 하나를 먼저 골라서 공부하면서 익숙해지는 것이 중요하다고 한다. 기본적으로는 스택오버플로우와 같은 문제가 발생한다면 이는 시간차이라기보다는 코드의 문제일 가능성이 크기 때문에 일단 기초적인 수준에서는 둘중 하나를 중점적으로 공부하는 것이 중요하다는 것! 다이나믹 문제 풀이의 전략으로는 "문제에서 구하려는 ..
골드바흐 파티션_ 백준 17103
골드바흐 파티션은 이전에 풀었던 골드바흐의 추측과 관련된 문제입니다. 2020/05/17 - [백준 문제풀이] - 골드바흐의 추측 _ 백준 6588 골드바흐의 추측은 2보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 라는 추측이다. 이번 문제는 이 골드바흐의 추측을 기반으로 짝수 N을 두 소수의 합으로 나타내는 골드바흐 파티션을 구하는 문제이다. 여기서 두 소수의 순서만 다른 것은, 같은 파티션으로 취급한다. 에라토스테네스의 체를 활용하여 소수를 먼저 확인해놓고, 그 뒤에 결과값을 출력하는 형식으로 알고리즘을 짜면 된다. 골드바흐 파티션을 계산할 때, '두 소수의 순서만 다른 것은, 같은 파티션으로 취급한다.'라는 조건에 따라 해당 값을 반으로 나눈 값까지만 세면 된다. 코드는 다음과 같다..
숨바꼭질6 _ 백준 17087
동생 N명과 숨바꼭질을 하면서, 한번에 X만큼 움직일 수 있다고 할때, 한번에 움직이기 위한 값을 구하는 문제이다. 이번 문제에서 중요한 것은 GCD이다. 즉, 최대공약수를 구해야 한다는 것. 왜 최대공약수가 필요하냐면 한번에 이동할 수 있는 위치값을 찾아서, 동생들의 위치에 모두 도달해야 하기 때문이다. 즉, 수빈이의 위치 - 동생의 위치의 절댓값들의 최대공약수를 찾으면 되는 문제이다. GCD함수를 구현하고, 문제를 해석하면 어렵지 않은 문제이다. 나는 배열을 사용하긴 했는데, 지금 풀고 나니까 굳이 배열이 없이도 풀 수 있는 문제인 것 같다. #include #include using namespace std; int nums[100000]; int GCD(int a, int b) { if (b ==..