DP

문제출저 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제풀이 배낭 문제, 냅색 알고리즘 문제로 조합 최적화를 찾아야 한다. 허용치 k인 배낭에 무게 w의 물건들을 담아서 물건들의 가치 v가 가장 높은 경우를 구해야한다. 문제를 해결하기 위해 2차원 int 배열인 dp를 활용한다. 2차원 배열인 dp의 가로줄은 배낭의 무게, 세로줄은 아이템을 배치한다. 1 2 3 4 5 6 ..

문제출저 https://www.acmicpc.net/problem/1480 1480번: 보석 모으기 첫째 줄에 보석의 개수 N, 가방의 개수 M, 가방의 최대 한도 C가 주어진다. N은 1보다 크거나 같고, 13보다 작거나 같은 자연수이고, M은 1보다 크거나 같고, 10보다 작거나 같은 자연수이다. C는 1보 www.acmicpc.net 문제풀이 주어진 가방을 이용해 최대한 많은 보석을 담는 방법을 구하는 문제이다. 이를 위해 중복을 줄여주는 비트마스크와 다이나믹프로그래밍, 완전탐색을 위한 DFS를 활용한다. int MAX = 14; dp = new int[1

문제출저 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.lang.reflect.Array; import java.nio.Buffer; import java.securi..

문제출저 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 소스코드 package studyGroup.June.june27; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class 백준2096내려가기 { static int n; // 줄의 갯수 static String..

문제출저 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; /* https://sangbeomkim.tistory.com/84 */ publ..

문제출저 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 소스코드 package studyGroup.June.june9; import java.util.*; import java.io.*; public class 백준11054가장긴바이토닉부분수열 { static int n; static int[] board; public static void main(String[] args) throws IOException { BufferedReader br = new Buf..

DP 개요 DP, 다이나믹 프로그래밍은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 문제해결에 패러다임으로 볼 수 있습니다. 큰 문제를 작은 문제로 나누어서 그 답을 저장해두고 재활용한다. 사용이유 DP는 일반적인 재귀(Navie Recursion) 방법과 유사합니다. 하지만 일반적인 재귀를 사용할 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있습니다. 피보나치 수열을 예시로 들겠습니다. 피보나치의 재귀 함수는 아래와 같습니다. return f(n) = f(n-1) + f(n-2) f(n)을 구하기 위해서 f(n-1)에서 한 번 구한 값들을 f(n-2)에서 같은 과정을 반..

문제출저 : https://www.acmicpc.net/problem/14945 14945번: 불장난 랩실의 크기가 3일 경우 (기웅, 민수)가 이동 가능한 방법은 (아래-아래, 대각-아래), (아래-아래, 대각-대각), (아래-대각, 대각-대각), (대각-아래, 아래-아래), (대각-대각, 아래-아래), (대각-대각, www.acmicpc.net 소스코드 : package studyGroup.June.june3; import java.util.*; import java.io.*; /* 중복되는 문제가 있기 때문에 DP로 접근한다. 이동할 수 있는 경우의 수는 4가지이다. 1. 둘 다 아래 (거리 그대로) 2. 1번 아래, 2번 오른쪽 (거리 +1) 3. 1번 오른쪽, 2번 오른쪽 (거리 그대로) 4. ..