반응형 알고리즘/다이나믹 프로그래밍13 백준 12865번 : 평범한 배낭 java 이 문제는 knapsack problem이라는 최적화 조합을 찾는 다이나믹 프로그래밍 문제입니다. 이 문제에서는 들 수 있는 무게가 정해져 있을 때 가장 가치합이 큰 값을 찾아내는 문제입니다. 저는 이 문제를 풀 때 특정한 무게에 따라서 각각의 물건들을 들 수 있는지를 따져가며 풀었습니다. 예제 1번을 통해서 그림과 같이 제가 이 문제를 푼 방식에 대해서 설명드리겠습니다. 예제 1번에서는 무게를 7kg까지 들 수 있고 물건이 4개가 주어진다고 하였기 때문에 다음과 같이 표를 그렸습니다. 무게가 0일 때는 아무것도 들 수 없고 물품이 0일 때는 아무 물건도 챙길 수 없다는 의미입니다. 따라서 무게가 0일 때와 물품이 0일 때의 셀에는 가치합이 0이 됩니다. 이제 각각의 무게에서 그 번호의 물품을 들 수 있.. 2022. 6. 1. 백준 1149번 : RGB거리 java 이 문제는 이전의 row와 다음의 row를 비교하여 같은 column에 수들이 들어있지 않게 더하여 최솟값이 나오게 하는 문제입니다. 저는 이 문제를 아래로 내려가면서 각 항의 합이 최솟값이 되는 조건을 찾아서 더해가며 풀었습니다. 왼쪽의 그림은 예제 1번의 입력값입니다. 이 그림을 통해서 어떤 규칙으로 문제를 푸는지 보여드리겠습니다. 이미 지나간 row는 파란색으로 표시하였고 지나가지 않은 row는 검은색으로 표시하였습니다. 이제 다음 row의 항들의 중에서 합이 최솟값이 되기 위해서는 어떤 항을 더해야하는지를 알아보겠습니다. 이 그림에서 빨간 항에서의 조건에 따른 최솟값을 구하기 위해서는 빨간 항이 있는 row의 위의 row에서 column이 다를 때의 최솟값을 더해야 합니다. 더할 수 있는 항들을 .. 2022. 5. 27. 백준 1932번 : 정수 삼각형 java 이 문제는 다이나믹 프로그래밍을 이용하여 이전의 최선의 경우의 수를 배열에 저장하며 푸는 문제입니다. 코드를 보면서 이 문제를 설명해드리겠습니다. import java.util.*; import java.io.*; 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][]; for(int i = 1; i 2022. 5. 27. 백준 9465번 : 스티커 java 이 문제는 2줄에 총 2 x N개의 자료가 들어왔을 때 주어진 조건에 따라 가장 큰 합을 구하는 문제입니다. 이 문제를 예제의 첫 번째 경우를 예로 들어 설명하겠습니다. 예시를 표로 나타내면 이렇게 됩니다. 이 표에서는 1번째 column에서 무조건 1개의 항을 선택해야 합니다. 그 이유는 2번째 column에서 혹은 3번째 column에서 어떠한 항을 선택하더라도 첫 번째 column에서 선택할 수 있는 항이 남기 때문입니다. 이를 그림으로 설명해드리겠습니다. 저는 선택한 항을 빨간 박스로 표시했고 그 주변에 문제에 따라서 찢어져서 사용할 수 없는 스티커들을 초록백 박스로 표시하였습니다. 이 경우에 1번 column에서 30이 추가가 될 수 있습니다. 반대로 2번 column에서 10이 아닌 50을 선.. 2022. 5. 26. 백준 11660번 : 구간 합 구하기 5 java 이 문제는 일정 범위의 구간 합을 미리 구해놓아서 원하는 범위의 합을 알고 싶을 때 빠르게 결과를 구하는 문제입니다. 저는 이 문제를 좌에서 우로 위에서 아래로 갈수록 수들을 합하여 저장해 놓도록 설계하였습니다. 아래에서 그림을 통해 자세히 설명드리도록 하겠습니다. 문제에 나와있는 예제로 구간 합을 구해보겠습니다. 위에서 설명드린 대로 화살표 방향으로 갈수록 값이 커집니다. 우선 가장 윗줄과 왼쪽 줄에서 구간합을 구하겠습니다. 첫 번째 구간합에서는 윗 줄은 자신 왼쪽에 있던 수만 더하면 되고 왼쪽 줄은 자신의 위에 있던 수만 더하면 됩니다. 하지만 이 수들을 제외하고는 자신을 오른쪽 아래 꼭짓점으로 하는 사각형 안의 구간합을 구해야 합니다. 예를 들어 파란 박스 안에 있는 숫자가 있는 공간에는 빨간 박스.. 2022. 5. 25. 이전 1 2 다음 반응형
