SY DevLog

동적 계획법(Dynamic Programming) 동적 프로그래밍, 다이나믹 프로그래밍 이라고도 한다. 동적 계획법이란 하나의 큰 문제를 작은 문제로 쪼개어서 문제를 해결하는 방법이다. 동적 계획법에서 가장 중요한 개념은 메모이제이션(Memoization)과 점화식이다. 메모이제이션(Memoization) : 동일한 계산이 반복될 때, 이전에 계산한 결과를 메모리에 저장하여 동일한 계산을 반복하는 것을 피하는 방법이다. 이전에 계산한 결과를 메모리에 저장하기 때문에 중복된 계산을 할 필요가 없으므로 속도가 빠르다는 장점이 있다. 그리고 동적 계획법에서는 이 메모이제이션을 위해 점화식을 세우는 과정이 필요하다. 동적 프로그래밍하면 가장 대표적인 예시가 바로 피보나치 수열이다. 피보나치 수열은 앞의 두 항의..

1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 정답률에 비해 어려웠던 문제였다. 비트마스크가 아직 익숙하지 않아서 그런지 비트마스크를 이용해서 메모이제이션을 어떻게 해야할지 고민하는데 시간이 오래 걸렸다. n번째 자리에 k라는 수가 오기 위해서는 n-1번째 자리에 k+1 혹은 k-1가 있어야 한다. 만약 비트마스크를 이용하지 않고 메모이제이션을 하면 다음과 같이 점화식을 세울 수 있다. dp[n][k] = dp[n-1][k-1] + dp[n-1][k+1] 그런데 이 문제에서는 해결해야하는 조건이 있다. 0부터 9까지 모든 수를 한번씩 사용해야 한다. 따라서, 0~9중에서 어떤 수를 사용했는가를 비트마스크를 이용하여 기록해야 ..

13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 백준 1912번 : 연속합 문제에서 좀 더 발전한 문제이다. 이번에는 주어진 수열에서 연속합을 구하되, 중간에 수 하나를 제거할 수가 있다. 백준 1912번 문제에서는 dp 1차원 배열을 이용하여 문제를 풀었는데, 이번에는 2차원 배열로 만들어서 풀었다. 아래는 백준 1912번 문제 풀이한 링크이다. lotuslee.tistory.com/89 [백준 1912번] 연속합 (java) 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 ..

1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 다이나믹 프로그래밍으로 풀었다. 다이나믹 프로그래밍은 무엇보다 점화식을 세우는 것이 중요하다. 나는 int[] dp = new int[n]; 로 1차원 dp배열을 생성하였고, dp[n]의 의미는 다음과 같이하였다. dp[n] : n번째 수가 연속합의 마지막일 때, 최대가 되는 연속합 무슨 말이냐면, 입력받은 수열을 배열 arr에 저장한다고 했을 때, arr[0] + ... + arr[n] : 0번째 수부터 n번째 수까지의 연속합 arr[1] + ... + arr[n] : ..