SY DevLog

1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 문제의 예제로 각 연주마다 가능한 볼륨을 표현하면 다음과 같다. 연주가 반복될 때마다 위의 그래프처럼 가지가 증가하므로 뒤로 갈수록 계산해야 하는 양이 많아진다. N의 범위가 최대 100이므로, N번째에는 2의 100승에 가까운 경우의 수를 검사해야 한다. -> 메모리 초과 혹은 시간 초과 다른 방법을 생각하다가 M+1크기의 배열을 생성하고, 다음과 같이 의미를 부여했다. int[] arr = new int[M+1]; arr..

1720번: 타일 코드 2×N 크기의 넓은 판을 1×2 (또는 2×1) 크기와 2×2 크기의 타일로 채우려고 한다. 여러 가지 경우가 있을 수 있으므로, 각각을 하나의 코드로 대응시켜서 암호화에 이용하려고 한다. 그런데 문제가 www.acmicpc.net 이 문제는 다이나믹 프로그래밍으로 풀었다. 좌우대칭인 한 결과는 동일한 것으로 간주해야 한다는 점에서 처음에 점화식을 세우기 어려웠다. 만약 좌우대칭을 신경쓰지 않는다면 점화식을 다음과 같이 세울 수 있다. dp[n] = dp[n-1] + dp[n-2] * 2 타일의 가로 길이가 n일 때의 가능한 경우의 수는 ① 타일의 가로 길이가 n-1일 때에서 2x1짜리 타일을 하나 추가한 경우 -> dp[n-1] ② 타일의 기로 길이가 n-2일 때에서 2x2짜리 ..

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

1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 다이나믹 프로그래밍으로 해결할 수 있다. dp[n][l][r] : n번째 빌딩을 세울 때, 왼쪽에서 보이는 빌딩의 수가 l개, 오른쪽에서 보이는 빌딩의 수가 r개가 되도록 건물을 배치하는 모든 경우의 수 먼저, 처음으로 빌딩을 하나 세웠다고 치자. 건물이 하나밖에 없으므로 왼쪽에서 보이는 건물의 수는 1개, 오른쪽에서 보이는 건물의 수도 1개가 된다. -> dp[1][1][1] = 1 그 다음으로 두번째 빌딩을 하나 세운다. 그러면 두 가지 중 하나이다. 왼쪽에..

4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 다이나믹 프로그래밍으로 문제를 해결하였다. 메모이제이션을 위해 3차원 dp배열을 생성했다. int[][][] dp = new int[2*N+1][2*N+1][N+1]; 첫번째 인덱스는 몇일이 지났는지를 의미하고, 두번째 인덱스는 현재 시점에서 반알짜리 알약의 개수, 세번째 인덱스는 한알짜리 알약의 개수를 의미한다. dp[t][h][w] : t일이 지났을 때, 반알짜리 알약의 개수가 h개이고, 한알짜리 알약의 개수가 w개일 때 가능한 모든 문자열의 개수 점화식을 세우면 아래와 같..

2228번: 구간 나누기 N(1≤N≤100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1≤M≤⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 www.acmicpc.net dp[n][m] : n개의 수를 m개의 구간으로 나누었을 때 최대 합 arr[i] : 입력받은 수들을 저장 n번째 수가 m번째 구간에 포함되어 있는지, 포함되어 있지 않는지 두 가지 경우로 나눌 수 있다. - n번째 수가 구간 m에 포함되지 않은 경우 : dp[n][m] = dp[n-1][m] n-1번째 수가 구간 m에 포함된 경우의 최대 합(dp[n-1][m])과 동일하다. - n번째 수가 구간 m에 포함된 경우 : dp[n][m] = max(d..

2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 합이 k원이 되면서, 순서만 다르고 조합이 같은 경우는 하나의 경우로 여긴다. 우선 각각의 동전의 가치를 coin 배열을 생성하여 차례대로 넣어주었다. int[] coin = new int[n]; coin[0] = 1 coin[1] = 2 coin[2] = 5 이 문제를 다이나믹 프로그래밍으로 풀기 위해 점화식을 세웠다. 처음에는 합이 k원이 되는 조합을 dp[k]라고 할 때, dp[k] = dp[k-coin[0]] + dp[k-coin[1]] + dp[k-coi..

2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net dp 2차원 배열을 이용하여 다이나믹 프로그래밍으로 문제를 해결하였다. 이 문제에서의 점화식은 다음과 같다. dp[n][0] : n번째 수열까지 중, 가장 긴 연속하는 증가하는 수열의 길이 dp[n][1] : n번째 수열까지 중, 가장 긴 연속하는 감소하는 수열의 길이 수열의 n번째 수를 n-1번째 수와 비교한다. n-1번째 수 < n번째 수 n-1번째 수가 더 작으므로 오름차순이 유지가 된다. 유지가 된다는 것은 n-1번째까지의 가장 긴 증가하는 수열의 길이(dp..

1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 www.acmicpc.net 트리에서 다이나믹 프로그래밍을 이용하여 푸는 문제다. dfs방식으로 루트노드에서부터 리프노드까지 top - down 으로 내려간 후, 다시 리프노드에서부터 위로 올라가면서 dp배열을 업데이트한다. dp배열은 이차원 배열로 생성하여서 n번 마을이 우수 마을인 경우와 그렇지 않은 경우로 나누었다. dp[n][0] : n번 마을이 우수 마을이 아닐 때, n번 마을을 루트노드로 하는 하위트리의 마을 주민 수의 총합 dp[n][1] : n번 마을이 우수 ..

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)이 주어지고 둘째 ..