다이나믹_프로그래밍

[C++] 백준 11057번 오르막 수

다이나믹 프로그래밍 문제. 지난번에 풀었던 쉬운 계단 수 문제와 비슷한 문제였다. [C++] 백준 10844번 쉬운 계단 수 다이나믹 프로그래밍 문제. 생각보다 너무 어려워서 이틀동안 계속 머리에 담아두다가 구글링의 도움을 받고 풀었다. 접근 방법 먼저, N자리 수는 N이 1일때는 1~9 2일때는 다음과 같다. 맨 앞자리 kimyunseok.tistory.com 지난 번에 이 문제를 풀었을 땐 풀기 어려워서 못 풀었었는데 비슷한 이문제는 비교적 쉽게 풀어서 이 때 정리를 나름 잘 한것 같아서 뿌듯했다. 문제 접근 방식 처음에 문제를 보자마자 위에서 설명했듯 쉬운 계단수를 풀었던 기억이 떠올렸다. 다이나믹 프로그래밍이라고 바로 생각했고 마지막 수에 따라 자리수의 마지막 수 이전에 어떤 수가 올 수 있는지 ..

[C++] 백준 1904번 01타일

다이나믹 프로그래밍 문제. 점화식이 바로 보여서 쉽게 풀 수 있지만 왜 그렇게 되는지도 생각해서 풀어보았다. 문제풀이 나는 위에 같은 경우로 경우의 수를 나누었다. 그림에 대한 설명을 하자면 N = 1, 1 -> 1개 N = 2, 00, 11 -> 2개 N = 3, 001, 100, 111 -> 3개 N = 4, 0000, 0011, 1001, 1100, 1111 -> 5개 N = 5, 00001, 00100, 10000, 00111, 10011, 11001, 11100, 11111 -> 8개 여기까지만 해도 An = A(n-1) + A(n-2)라는 결과를 얻을 수가 있다. 그러면 왜 그렇게 되는 것일까? An은 A(n-1)에서 한 자리가 추가되는 것이다. 한 자리가 추가되는 것은 무조건 타일 1이 추가..

[C++] 백준 10844번 쉬운 계단 수

다이나믹 프로그래밍 문제. 생각보다 너무 어려워서 이틀동안 계속 머리에 담아두다가 구글링의 도움을 받고 풀었다. 접근 방법 먼저, N자리 수는 N이 1일때는 1~9 2일때는 다음과 같다. 맨 앞자리가 1일때 : 10, 12 맨 앞자리가 2일때 : 21, 23 ... 맨 앞자리가 9일때 : 98 3일때는 다음과 같다. 맨 앞자리가 1일때 : 101, 121, 123 맨 앞자리가 2일때 : 210, 212, 232, 234 ... 맨 앞자리가 9일때 : 987, 989 따라서 다음과 같은 정리가 가능하다. 마지막 숫자가 0이라면 다음으로 갈 수 있는 수는 1 뿐이다. -> 마지막 숫자 앞의 수가 1인 경우만 마지막 숫자가 0이 가능하다. 마지막 숫자가 9라면 다음으로 갈 수 있는 수는 8 뿐이다. -> 마지..

[C++] 백준 9461번 파도반 수열

다이나믹 프로그래밍 문제. 친절하게 P(1)부터 P(10)까지의 값이 모두 주어졌다. DP는 Bottom Up 방식으로 풀면 주어지는 값이 많으면 많을수록 유추하기 쉽기 때문에 풀기 쉽다. 문제풀이 주어지는 값들의 규칙을 찾아보면 점화식을 바로 찾을 수 있다. n>=4일때, An = A(n - 2) + A(n - 3) 이다. 코드가 짧다. n이 4부터 시작하므로 1, 2, 3값은 초기화를 미리 시켜준다. 그리고 자료형은 long long으로 해주어야 오버플로우가 나지 않는다. GitHub - kimyunseok/study-record: my study-record my study-record. Contribute to kimyunseok/study-record development by creating ..

[C++] 백준 11727번 2xn 타일링 2

다이나믹 프로그래밍 문제. 처음에 이 문제를 풀 때 점화식을 잘못잡아서 계속 답이 이상하게 나왔었다. 그래서 어떤 방식으로 푸는지 구글링의 도움을 좀 받았는데, 역시 점화식을 구해서 푸는 방식이였다. 이런 문제 유형도 있음을 알아두어야 될 것 같다. 문제 접근 방법 먼저 An을 구할 때, A(n-1)에서 한 칸만 더 추가되는 방식이다. 이 때 2x1이 추가되는 것과 마찬가지 이다. 따라서 A(n-1)에서 2x1을 추가한 것 A(n-2)에서는 2 x 1 두개 추가한 것 : 그러나 이 방식은 A(n-1)에서 2x1을 추가한 것에 포함되어 있다. 1 x 2 두개 추가한 것 2 x 2 추가한 것 A(n-3)부터는 어차피 이미 다 포함되어 있으므로 생각할 필요가 없다. 따라서 점화식은 An = A(n-1) + 2..

[C++] 백준 2193번 이친수

DP 문제 이런 류의 DP 문제는 항상 1부터 차례대로 해 보면서 점화식을 세우는 것이 중요하다. 시도 방식 & 문제 풀이 점화식을 구해서 코드로 구현했다. 규칙성이 바로 보이므로 점화식을 찾는데는 문제가 없었다. 근데 여기서 N이 90이 되면 엄청나게 큰 수가 된다. 따라서 dp배열을 int가 아닌, long long형태의 배열로 만들어 주는 것이 중요하다. 처음 시도는 TOP DOWN방식의 재귀형태로 시도했는데, 시간초과가 났다. 그리고 위 방식대로 풀었는데, OVERFLOW가 나서 틀렸습니다 가 나왔다. 자료형을 바꾸고 나서는 바로 맞출 수 있었다. GitHub - kimyunseok/study-record: my study-record my study-record. Contribute to kim..

[C++] 백준 2156번 포도주 시식

다이나믹 프로그래밍 문제. 처음 문제를 보고 예전에 풀었던 계단 오르기와 비슷한 문제라고 생각했다. [C++] 백준 2579번 계단 오르기 다이나믹 프로그래밍 문제. 처음 이문제를 봤을 때 처음에 백트래킹으로 시도했다가 시간초과가 너무 많이났다. (생각해보면 계단 개수가 최대 300개 인데, 이를 고려하면 경우의 수가 2의 지수 kimyunseok.tistory.com 그런데 막상 문제를 풀어보니 엄청 많이 틀렸고, 반례들을 통해 잘못된 점을 알게됐다. 문제 접근방식 우선 조건으로 주어지는 건 간단하다. 최대한 많은 양을 먹어야 하고 3잔을 연속으로 먹는 건 불가능하다. 천국의 계단 같은 경우는 어차피 +1 아니면 +2였기 때문에 이 문제도 똑같은 방식으로 접근했다. 이 두 개 조건을 가지고 문제를 풀려..

[C++] 백준 1912번 연속합

DP 문제. 수를 연속해서 선택하는데, 어떤 경우에 해당하는 번째의 수가 최대값을 가지게 되는지 구하는 문제이다. 문제에 접근한 방식 문제를 읽어보고, DP Bottom Up 방식으로 접근을 시도했다. 값을 더했을 때 계속 양수인 경우, 계속해서 더해주면 그게 구할 수 있는 가장 큰 합이 된다. 값을 더했을 때 음수가 나오는 경우, 그 값을 더하지 않는 것이 더 큰 값이므로 더이상 더해주지 않고 새로 시작한다. 따라서 점화식은 최대값이 An이고, 현재 수가 Bn을 나타낼 때 An = max( A(n-1) + Bn, Bn)이 된다. 이렇게 두 개를 고려하고 문제를 접근하면 된다. 자세하게 고려하고 풀지는 않았는데, 지금 보니 왜 저렇게 생각했는지 풀었으면 더 좋았을 것 같다. 문제풀이 최대값을 갱신시켜 주..

[C++] 백준 1932번 정수 삼각형

다이나믹 프로그래밍 문제. 경우의 수를 나눠서 Bottom Up 방식으로 문제를 해결하면 된다. 처음에 그림을 보고 트리 -> 그래프 탐색인 줄 알았는데 문제를 읽어보고 그림을 그려보니까 다이나믹 프로그래밍이란 것을 알았다. 그림을 보면 각 노드에서 아래로 내려오면서 그 노드의 최대값을 갱신해 나가면 된다. 이 때 방향을 보면 맨 첫번째 노드는 각 전단계의 첫번째 노드에서만 온다는 것을 알 수 있다. 그리고 마지막 노드는 전단계의 마지막 번째의 노드에서만 온다는 것을 알 수 있다. 첫번째, 마지막 둘 다 아니라면 전 단계의 왼쪽, 오른쪽 노드에서 온다는 것을 알 수 있다. 점화식을 세우면 다음 그림과 같다. dp[i][j]는 i, j의 최대값을 저장하는 배열이고 triangle[i][j]는 i, j의 가..

[C++] 백준 2579번 계단 오르기

다이나믹 프로그래밍 문제. 처음 이문제를 봤을 때 처음에 백트래킹으로 시도했다가 시간초과가 너무 많이났다. (생각해보면 계단 개수가 최대 300개 인데, 이를 고려하면 경우의 수가 2의 지수승이 어마어마하게 크기 때문에 잘못된 접근이다.) 사실 시간초과 부분에 관련해서 게시물을 찾다가 반복문으로 충분히 해결가능 하다는 답변을 보았고, 얼핏 스쳐가는 코드에서 max 메서드를 보았다. max 메서드는 오래동안 안 써왔어서 생각을 못했는데, max 메서드를 써서 접근하기로 했다. 따라서 이건 포기하고 다이나믹 프로그래밍의 Bottom Up 방식으로 접근하기로 했다. 다시 접근할 때 max 메서드를 오랜만에 써서 그런지 머리가 잘 안돌아갔다. max(A, B)는 A와 B중 큰 값을 return해주는 algori..