다이나믹 프로그래밍72 [백준] 17070번 - 파이프 옮기기 1 [Java] https://www.acmicpc.net/problem/17070 1. 아이디어 파이프 옮기기 2에서 경우의 수가 줄어든 문제로 동일하게 다이나믹 프로그래밍으로 해결할 수 있다.Top-Down 방식과 Bottom-Up 방식 두가지로 해결했다.([코딩테스트 준비/백준] - [백준] 17069번 - 파이프 옮기기 2 [Java])2. 문제풀이 두 가지 방식 모두 오른쪽 끝단의 정보를 갖고 dp 테이블을 갱신했다. dp는 위치와 파이프가 놓인 방향까지 고려해야해서 3차원 배열로 행, 열, 방향을 모두 고려했다.3. 코드 import java.io.*;import java.util.*;public class Main_TopDown_DP { private static int N; private st.. 2025. 3. 12. [백준] 17069번 - 파이프 옮기기 2 [Java] https://www.acmicpc.net/problem/17069 1. 아이디어 방법의 수가 매우 많아질 수 있어서 다이나믹 프로그래밍으로 해결할 수 있다.Top-Down 방식과 Bottom-Up 방식 두가지로 해결했다.2. 문제풀이 두 가지 방식 모두 오른쪽 끝단의 정보를 갖고 dp 테이블을 갱신했다. dp는 위치와 파이프가 놓인 방향까지 고려해야해서 3차원 배열로 행, 열, 방향을 모두 고려했다.3. 코드 import java.io.*;import java.util.*;public class Main_TopDown_DP { private static int N; private static int[][] map; private static long[][][] dp; public.. 2025. 3. 10. [백준] 7570번 - 줄 세우기 [Java] https://www.acmicpc.net/problem/7570 1. 아이디어 가장 긴 연속하며 증가하는 번호로 이루어진 부분 수열을 구하고 수열에 해당하지 않는 번호를 적절하게 앞 뒤로 이동시키는 그리디 알고리즘과 다이나믹 프로그래밍으로 해결할 수 있다.2. 문제풀이 dp 배열을 먼저 선언했고 dp 배열은 인덱스에 해당하는 숫자로 끝나는 가장 긴 연속하며 증가하는 부분 수열의 길이를 저장한다.점화식은 dp[idx] = dp[idx-1] + 1 로 연속해야하므로 해당 숫자보다 1 작은 숫자로 끝나는 가장 긴 연속하며 증가하는 부분 수열의 길이 + 1을 해주면 된다.3. 코드 import java.io.*;import java.util.*;public class Main { public stati.. 2025. 3. 4. [백준] 1106번 - 호텔 [Java] https://www.acmicpc.net/problem/1106 1. 아이디어 무한 배낭 문제로 다이나믹 프로그래밍으로 해결할 수 있다.고객을 무게, 돈을 가치로 생각하면 되며 C명 이상을 담았을 때 최솟값을 구해야 하는 점에 주의해야한다.2. 문제풀이 1차원 dp, 2차원 dp 두 가지 방식으로 풀어봤고 최솟값을 저장하는 배낭 문제여서 최댓값으로 초기화한 후 최솟값을 저장하도록 했다.C명 이상인 최솟값을 구해야하는 조건에서 정확히 C명일 때를 구하는게 아님에 주의해야하고 돈을 정수배만큼 투자할 수 있다는 점에서 무한 배낭 문제임에 주의해야한다.이를 위해 dp의 크기를 C보다 크게 설정해야하는데 한번 배낭에 담을 때 고객이 최대 100명이므로 100만큼 더 크게 설정했고 중복으로 담을 수 있어서 현재.. 2025. 3. 3. [백준] 16493번 - 최대 페이지 수 [Java] https://www.acmicpc.net/problem/16493 1. 아이디어 0-1 배낭 문제로 다이나믹 프로그래밍으로 해결할 수 있다.챕터의 종류가 최대 20가지여서 부분집합을 활용해서도 해결할 수 있었다.2. 문제풀이 부분집합은 재귀를 통한 완전탐색으로 진행하되 N일이 넘어가는 집합은 더 탐색하지 않도록 백트래킹을 했다.다이나믹 프로그래밍은 날짜를 인덱스 값을 페이지 수로 하는 일반적인 0-1 배낭으로 해결할 수 있었다.3. 코드 import java.io.*;import java.util.*;public class Main_PowerSet { private static class Item { int day; int page; public Item(i.. 2025. 2. 27. [백준] 7579번 - 앱 [Java] https://www.acmicpc.net/problem/7579 1. 아이디어 0-1 배낭 문제로 다이나믹 프로그래밍으로 해결할 수 있다.앱을 비활성화하는 비용을 무게, 앱을 비활성화해서 확보할 수 있는 메모리를 가치로 생각하면 된다.2. 문제풀이 1차원 dp, 2차원 dp 두 가지 방식으로 모두 풀어봤고 dp 테이블에는 확보할 수 있는 메모리를, 인덱스에는 비활성화하는데 필요한 비용을 두면 된다. 비활성화하는데 필요한 비용이 0일 수 있어서 인덱스 0부터 모두 사용하고 이후 정답을 찾을 때도 0번 인덱스부터 탐색을 해야한다. 정답은 최소 비용으로 M 이상의 메모리를 확보해야하는데 인덱스 자체가 이미 정렬이 된 개념이어서 앞에서부터 순회하면 된다.3. 코드 import java.io.*;import .. 2025. 2. 27. [백준] 2294번 - 동전 2 [Java] https://www.acmicpc.net/problem/2294 1. 아이디어 무한 배낭 문제로 다이나믹 프로그래밍을 활용해서 해결할 수 있다.2. 문제풀이 각 가치를 만드는데 필요한 동전의 최소 개수를 저장하는 문제로 역시 주어지는 동전의 종류가 늘어난다고 생각하는 배낭 스타일로 풀 수 있다. dp 테이블의 초기화가 중요한데 0원을 만드는데는 동전이 필요없으니 0개이고 나머지 금액을 만드는데는 동전이 무한히 많이 필요하다고 초기화를 해줘서 이후 갱신과정에서 최소 개수로 갱신이 되도록 해줘야 한다.3. 코드 import java.io.*;import java.util.*;public class Main_1D { private static final int MAX = 10001; public.. 2025. 2. 27. [백준] 2293번 - 동전 1 [Java] https://www.acmicpc.net/problem/2293 1. 아이디어 무한 배낭 문제로 다이나믹 프로그래밍을 활용해서 해결할 수 있다.2. 문제풀이 각 동전에 번호를 매긴 후 1번 동전만 주어졌을 때 사용해서 만들 수 있는 경우의 수, 1번, 2번 동전만 주어졌을 때 사용해서 만들 수 있는 경우의 수 이렇게 동전의 종류를 확장하며 풀어가면 된다. 다음 동전 종류가 주어졌을 때 기존의 조합으로도 각 경우를 만들 수 있으므로 해당 경우는 그대로 두고 새로운 동전으로 만들 수 있는 경우는 새로운 동전의 가치를 뺀 금액을 만들 수 있는 경우의 수로 찾으면 된다. 이때 같은 동전을 여러 개 사용할 수 있어서 새로운 동전이 주어진 상황에서의 금액과 비교해야한다.3. 코드 import java.io.*;.. 2025. 2. 27. [백준] 2629번 - 양팔저울 [Java] https://www.acmicpc.net/problem/2629 1. 아이디어 TopDown, BottomUp 다이나믹 프로그래밍을 활용해서 해결했다.2. 문제풀이 TopDown 방식은 부분집합을 구하는 재귀 메서드와 메모이제이션을 활용했는데 부분집합은 해당 추를 사용하지 않거나 왼쪽 팔에 추를 올리거나 오른쪽 팔에 추를 올리는 3가지 경우가 있다.추의 개수가 최대 30개이므로 모든 경우의 수는 3^30가지가 되고 이건 시간초과가 발생하게 된다. 이를 해결하기 위해 boolean 타입 2차원 배열을 활용해 해당 추까지 주어졌을 때 구할 수 있는 무게를 방문 체크하고 방문된 경우를 만나면 바로 종료하도록 했다.파라미터로는 추의 번호와 구할 수 있는 무게를 들고 다녔고 구할 수 있는 무게는 왼쪽 팔 - .. 2025. 2. 26. [백준] 9084번 - 동전 [Java] https://www.acmicpc.net/problem/9084 1. 아이디어 Coins 문제와 동일한 문제다.([코딩테스트 준비/백준] - [백준] 3067번 - Coins [Java])2. 문제풀이 동일하게 다이나믹 프로그래밍을 활용한 무한 배낭으로 해결했다.3. 코드 import java.io.*;import java.util.*;public class Main_1D { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedW.. 2025. 2. 26. [백준] 3067번 - Coins [Java] https://www.acmicpc.net/problem/3067 1. 아이디어 무한 배낭 문제로 다이나믹 프로그래밍으로 해결할 수 있다.직관적인 2차원 dp 테이블을 활용한 방식과 좀 더 발전한 1차원 dp 배열을 활용한 방식으로 해결했다.2. 문제풀이 2차원 dp 테이블은 행을 동전의 번호, 열을 방법의 수로 하면 되고 1차원 dp 배열은 방법의 수를 인덱스로 하면 된다.방법의 수는 현재 동전을 사용해서 만들 수 있는 경우의 수와 현재 동전을 사용하지 않고 만들 수 있는 경우의 수의 합으로 구할 수 있다.2차원 dp 테이블의 경우 0원을 만들 수 있는 경우는 1가지이므로 모든 행의 0번 인덱스는 1로 초기화했다.방법의 수를 구하기 위해 dp 테이블의 각 칸은 현재 동전을 사용하지 않고 만들 수 있는.. 2025. 2. 26. [백준] 12865번 - 평범한 배낭 [Java] https://www.acmicpc.net/problem/12865 1. 아이디어 대표적인 0-1 배낭 문제로 다이나믹 프로그래밍으로 해결할 수 있다.직관적인 2차원 dp 테이블을 활용한 방식과 좀 더 발전한 1차원 dp 배열을 활용한 방식으로 해결했다.2. 문제풀이 2차원 dp 테이블은 행을 물건의 번호, 열을 무게로 하면 되고 1차원 dp 배열은 무게를 인덱스로 하면 된다.2차원 dp 테이블은 행 번호가 늘어날수록 고려하는 물건의 종류가 늘어난다고 생각하면 되고 현재 번호의 물건을 담았을 때와 안 담았을 때 중 최댓값을 찾으면 된다.1차원 dp 배열은 2차원 dp 테이블이 이전 행의 정보로 현재 행을 구성하는 점에 착안해 갱신해주면 되고 이때 인덱스를 뒤에서부터 갱신해줘서 같은 물건이 중복으로 담기.. 2025. 2. 26. 이전 1 2 3 4 ··· 6 다음
