반응형 알고리즘/다이나믹 프로그래밍13 백준 2294번 동전 2 java 이 문제는 다이나믹 프로그래밍을 이용하여 동전과 가치의 합이 주어질 때 동전의 개수가 최소가 될 때를 찾는 문제입니다. 이 문제는 아래의 문제와 비슷한 풀이로 풀 수 있으니 아래의 문제를 보고 오시는 것을 추천드립니다. 백준 2293번 : 동전 1 java 이 문제는 다이나믹 프로그래밍을 이용하여 N개의 동전을 이용하여 K원이 되게 하는 경우의 수를 구하는 문제입니다. 저는 이 문제를 N개의 동전의 가치들을 배열에 저장한 후 1원을 만들 때의 dy-coding.tistory.com 저는 이 문제를 N개의 동전의 가치들을 배열에 저장한 후 1원을 만들 때의 동전의 수부터 N원을 만들 때의 동전의 수를 저장해가며 해결하였습니다. 예제 1번을 이용하여 문제를 해결하는 과정을 설명드리겠습니다. cnt[i]는 동.. 2022. 6. 15. 백준 2293번 : 동전 1 java 이 문제는 다이나믹 프로그래밍을 이용하여 N개의 동전을 이용하여 K원이 되게 하는 경우의 수를 구하는 문제입니다. 저는 이 문제를 N개의 동전의 가치들을 배열에 저장한 후 1원을 만들 때의 경우의 수부터 N원을 만들 때의 경우의 수를 각각의 동전을 사용할 수 있을 때로 나누어 구해주었습니다. 이에 대해서 예제 1번을 이용하여 자세히 설명드리겠습니다. 위의 예제 1번을 보시면 3개의 동전을 사용하여 가치의 합이 10이 될 때를 구해야 합니다. 우선 cnt 배열의 위에 있는 수는 각 셀에 들어갈 수 있는 가치의 최댓값을 나타낸 것입니다. 이제 코인의 가치 중 가장 가치가 낮은 1원짜리 동전으로만 cnt 배열을 채워보겠습니다. cnt 배열을 채우는 점화식은 cnt[i] = cnt[i] + cnt[i-coin[.. 2022. 6. 15. 백준 11052번 : 카드 구매하기 java 이 문제를 처음 봤을 때 저는 어떤 방식으로 문제를 해결해야 할까가 의문이었습니다. 1장짜리 카드팩으로만 N개를 살 수도 있고 1장짜리 카드팩에 2장짜리 카드팩을 몇 개 섞을 수도 있습니다. 이 모든 상황들을 백트래킹으로 풀기에는 너무 많은 시간이 걸리기 때문에 시도하기 어려웠습니다. 그래서 이 문제의 분류를 보니 다이나믹 프로그래밍이였습니다. 이렇게 경우의 수가 많아 보이는데 어떻게 다이나믹 프로그래밍으로 문제를 해결해야 하나 고민을 하다가 살 수 있는 카드의 개수에 따라서 dp를 만들면 되지 않을까 생각하였습니다. 그래서 dp[1]은 카드 1개를 살 때로 정하였고 dp[2]는 카드 2개를 살 때의 최대 비용으로 정하였습니다. dp[2]을 정하기 위해서는 2장이 들어있는 카드팩 1개와 dp[1]과 1장.. 2022. 6. 14. 백준 2096번 : 내려가기 java 이 문제는 다이나믹 프로그래밍을 이용하여 푸는 문제입니다. 그런데 이 문제를 보시면 N이 어떤 값이 입력되든지 한 행에는 3개의 값이 들어옵니다. 이렇게 일정한 크기의 부분들에서 반복되는 작업을 할 때 우리는 이것을 더 효율적으로 하기 위해서 슬라이딩 윈도우라는 알고리즘을 사용할 수 있습니다. 슬라이딩 윈도우에 대해서 먼저 설명드리겠습니다. 다음과 같이 위 문제에서 입력값이 들어왔다고 가정해보겠습니다. 이 문제에서 입력값은 한 행의 크기가 3으로 고정되어 있기 때문에 우리는 이것을 한 행씩 처리할 수 있습니다. 1번 행을 처리하고 그 다음 행의 연산을 처리하는 식으로 고정된 크기의 영역을 처리하며 문제를 해결할 수 있습니다. 위 그림의 구간을 먼저 처리한 후 아래 그림의 과정들을 계속 처리합니다. 이 알.. 2022. 6. 13. 백준 11053번 : 가장 긴 증가하는 부분 수열 java 이 문제는 다이나믹 프로그래밍을 이용하여 증가하는 부분 수열을 만드는 문제입니다. 저는 입력받은 값들을 저장하는 intArr 배열과 메모이제이션한 값들을 넣은 dp배열을 사용하였습니다. 추가적인 설명은 코드를 보면서 드리도록 하겠습니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[] intArr = new int[N]; int[] .. 2022. 6. 8. 백준 1912번 : 연속합 java 이 문제는 다이나믹 프로그래밍 분야의 문제로 들어오는 값을 이전의 값들의 합이 최대 일 때와 비교해서 대입하면 됩니다. 예제 1번을 보면 처음에 10이 입력이 되는데 이때 비교할 이전 값이 없으니 intArr[0]번은 10입니다. 그 다음 -4의 값이 입력이 되는데 이전의 값이 10이고 10 + (-4) = 6으로 -4보다 6이 크니 intArr[1]번은 6이 됩니다. 3이 입력이 되면 3과 9(3+6) 중에서 9가 더 크므로 intArr[2]는 9가 됩니다. 이런 규칙으로 intArr[3] = 9+1, intArr[4] = 10 + 5, intArr[5] = 15 + 6, intArr[6] = 21 + (-35)이 대입됩니다. intArr[6]에 -14가 들어있을 때 다음 입력값은 12입니다. -14 .. 2022. 6. 7. 백준 1904번 : 01타일 java 이 문제는 규칙을 찾아서 점화식을 만들어 푸는 다이나믹 프로그래밍 문제입니다. 이 문제에서는 N이 1일 때 1개, 2일 때 2개, 3일 때 3개 4일 때 5개 이런 식으로 만들 수 있습니다. 이때 찾을 수 있는 점화식은 오른쪽의 식과 같습니다. 이러한 규칙으로 늘어나는 것은 피보나치 수열의 형태와 같습니다. 따라서 저는 이러한 형태가 되도록 코드를 구현했습니다. import java.io.*; public class Main { static int[] dp; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N .. 2022. 6. 5. 백준 9251번 : LCS java 이 문제는 LCS(Longest Common Subsequence) 알고리즘입니다. 이 알고리즘을 위 문제의 예제 입력을 통해 설명드리겠습니다. 주어진 입력들을 받아서 다음과 같이 표로 나타냅니다. 각 셀은 이 구간까지 탐색했을 때 겹치는 subsequence가 얼마나 있느냐입니다. 예를 들어 (2, 3)에 들어가 있는 수는 CA와 ACA가 얼마나 겹치는가입니다. 이 규칙대로 위의 표를 채워보겠습니다. C 하나와 비교했을 때 2번 column의 C의 subsequence가 되니 그 이후는 전후 1입니다. CA와 비교할 때 A만 있을 때는 subsequence가 A이지만 ACA와 CA를 비교하면 CA가 겹치니 2가 됩니다. 마찬가지로 CAP가 겹치니 3까지 나옵니다. CAPC는 위의 문자열과 겹치지 않으므.. 2022. 6. 2. 이전 1 2 다음 반응형
