https://www.acmicpc.net/problem/2056[백준/BOJ] 2056번: 작업 - Java 풀이 (위상 정렬)안녕하세요! 이번 포스팅에서는 백준(BOJ) 2056번 '작업' 문제를 Java로 해결하는 방법을 알아보겠습니다. 이 문제는 여러 작업들과 그 선행 관계가 주어졌을 때, 모든 작업을 완료하는 데 걸리는 최소 시간을 구하는 문제입니다. '게임 개발(1516번)' 문제와 매우 유사하며, 위상 정렬(Topological Sort)을 이용해 효율적으로 해결할 수 있습니다.📜 문제 이해문제의 핵심은 다음과 같습니다.N개의 작업이 있으며, 각 작업은 수행하는 데 특정 시간이 걸린다.몇몇 작업은 선행되어야 할 작업들이 있다.모든 작업을 완료하기 위해 필요한 총 시간을 구해야 한다.여기서 ..

https://www.acmicpc.net/problem/1965 [백준/BOJ] 1965번: 상자넣기 - Java 풀이 (DP)안녕하세요! 이번 포스팅에서는 백준(BOJ) 1965번 '상자넣기' 문제를 Java를 이용해 해결하는 방법을 알아보겠습니다. 이 문제는 동적 계획법(Dynamic Programming), 그중에서도 가장 대표적인 유형 중 하나인 가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence, LIS) 알고리즘을 사용하여 해결할 수 있습니다.📜 문제 이해문제는 간단합니다. 여러 개의 상자가 있고, 각 상자는 크기를 가집니다. 작은 상자는 큰 상자 안에 넣을 수 있습니다. 한 상자 안에 여러 개의 상자를 넣을 수는 없습니다. 이 때, 한 번에 가장 많은 ..

https://www.acmicpc.net/problem/1915[백준/BOJ] 1915번: 가장 큰 정사각형 - Java 풀이 (DP)문제 소개백준 1915번: 가장 큰 정사각형 문제는 0과 1로 채워진 N x M 크기의 행렬에서, 1로만 이루어진 가장 큰 정사각형의 넓이를 구하는 문제입니다.이 문제는 동적 계획법(Dynamic Programming, DP)을 사용하여 효율적으로 해결할 수 있는 고전적인 문제입니다. 모든 좌표에서 시작하는 모든 크기의 정사각형을 일일이 확인하는 완전 탐색 방식으로는 시간 초과가 발생하기 쉽기 때문에 DP를 통한 접근이 필수적입니다.문제 분석 및 DP 점화식 설계이 문제의 핵심은 '특정 칸을 오른쪽 아래 꼭짓점으로 하는 가장 큰 정사각형'의 크기를 어떻게 효율적으로 구할..

[백준/BOJ] 1937번: 욕심쟁이 판다 - Java 풀이 (DFS + DP)문제 소개백준 1937번: 욕심쟁이 판다 문제는 N x N 크기의 대나무 숲에서 판다가 최대한 오래 생존할 수 있는 일수를 구하는 문제입니다. 판다는 현재 있는 칸보다 대나무가 더 많은 칸으로만 이동할 수 있으며, 한 번 이동하면 하루가 지나는 것으로 간주합니다.이 문제는 모든 칸에서 출발하는 경우를 고려해야 하며, 각 출발점에서 가장 긴 이동 경로를 찾아야 합니다. 단순한 완전 탐색(Brute-force)으로 접근하면 시간 초과가 발생하기 쉬워, 동적 계획법(Dynamic Programming, DP)과 깊이 우선 탐색(DFS)을 결합하여 해결해야 하는 대표적인 문제입니다.문제 분석 및 접근 방식처음 문제를 접하면, 모든 칸..

https://www.acmicpc.net/problem/15988백준 15988번: 1, 2, 3 더하기 3 풀이 (Java DP)안녕하세요! 오늘은 정수를 1, 2, 3의 합으로 나타내는 경우의 수를 찾는, 백준 15988번 '1, 2, 3 더하기 3' 문제를 동적 계획법(DP)으로 풀어보겠습니다. 이 문제는 여러 개의 테스트 케이스와 큰 입력 범위, 그리고 나머지 연산이 추가된 고전적인 DP 문제입니다.문제 분석목표: 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구해야 합니다.핵심 제약 조건:합을 나타내는 순서가 다르면 다른 경우로 간주합니다. (예: 1+2와 2+1은 다름)결과가 매우 커질 수 있으므로, 1,000,000,009로 나눈 나머지를 출력해야 합니다.여러 ..

https://www.acmicpc.net/problem/14916백준 14916번: 거스름돈 문제 풀이 (Java DP)안녕하세요! 오늘은 백준 14916번 '거스름돈' 문제를 동적 계획법(Dynamic Programming)을 사용하여 해결하는 방법에 대해 공유하고자 합니다. 이 문제는 최소 개수의 동전을 찾는 전형적인 DP 문제입니다.문제 이해문제는 간단합니다. 손님에게 2원과 5원짜리 동전으로 거스름돈 N원을 주려고 할 때, 필요한 동전의 최소 개수를 구하는 것입니다. 만약 정확하게 N원을 거슬러 줄 수 없다면 -1을 출력합니다.해결 아이디어: 동적 계획법 (DP)이 문제를 해결하는 가장 확실한 방법 중 하나는 동적 계획법을 사용하는 것입니다.DP 상태 정의: dp[i]를 "i원을 거슬러 줄 때 ..

✨ 자바로 푸는 타일 채우기 문제 풀이 📌 문제 개요 3×N 크기의 벽을 2×1, 1×2 타일로 채우는 경우의 수를 구하는 문제입니다.단, 타일은 겹치지 않고 벽을 완전히 채워야 합니다. 입력: 정수 N (1 ≤ N ≤ 30, N은 짝수만 의미 있음)출력: 벽을 채우는 모든 경우의 수 💡 예제 입력8 💡 예제 출력153 🛠 알고리즘 접근 방식 이 문제는 단순한 피보나치나 일반적인 dp[i] = dp[i-1] + dp[i-2] 형태로 해결되지 않습니다.특수 패턴이 반복적으로 등장하기 때문에 이에 맞는 점화식을 구성해야 합니다. ✅ 핵심 아이디어 홀수 크기(N % 2 == 1)인 경우 절대 채울 수 없습니다 → 경우의 수 0기본적으로는 dp[i] = dp[i - 2] * 3여기에 특수 타일 패..

✨ 자바로 푸는 합분해 문제 풀이 📌 문제 개요 정수 N과 정수 K가 주어졌을 때,정수 N을 K개의 정수의 합으로 나타내는 경우의 수를 구하는 문제입니다. 단, 0도 정수에 포함되며, 순서가 다른 것은 다른 경우로 칩니다. 💡 예제 입력20 2 💡 예제 출력21 🛠 알고리즘 접근 방식 이 문제는 전형적인 DP(동적 계획법) 문제입니다. dp[n][k] = 정수 n을 k개의 정수 합으로 표현하는 경우의 수 🔸 점화식 아이디어 dp[n][k] = dp[n-1][k] + dp[n][k-1] dp[n-1][k]: 마지막 수가 1 이상일 때, 전체 합에서 1을 빼고 다시 나누는 경우dp[n][k-1]: K-1개의 정수로 n을 만들고 마지막에 0을 더하는 경우 ✅ 핵심 초기값 dp[1][i] = ..

✨ 자바로 푸는 가장 큰 증가하는 부분 수열 문제 풀이 📌 문제 개요 “가장 큰 증가하는 부분 수열” 문제는 다음과 같은 조건을 만족하는 부분 수열을 찾는 문제입니다. 수열 A에서 증가하는 부분 수열 중, 합이 가장 큰 부분 수열의 합을 구하라! 즉, 단순히 길이가 아니라 합이 최대인 증가 수열을 구하는 문제입니다. 💡 예제 입력10 1 100 2 50 60 3 5 6 7 8 💡 예제 출력113→ 부분 수열: 1 + 2 + 50 + 60 = 113 (또는 1 + 100) 🛠 알고리즘 접근 방식 이 문제는 **DP(동적 계획법)**을 통해 해결할 수 있습니다. 우리는 아래와 같은 배열을 정의합니다. dp[i]: i번째 수를 마지막으로 하는 증가 수열의 최대 합 이후, 앞의 원소들과 비교하며 ..

✨ 자바로 푸는 오르막 수 문제 풀이 📌 문제 개요 오르막 수란, 각 자릿수가 비내림차순(내림하지 않는 순서)으로 구성된 수를 말합니다.예를 들어 1234, 1123, 5555는 오르막 수입니다.321, 201과 같이 감소하는 수가 있는 경우는 오르막 수가 아닙니다. 문제 목표는길이가 N인 오르막 수의 개수를 구하는 것이며,정답은 10007로 나눈 나머지를 출력합니다. 💡 예제 입력1 💡 예제 출력10 🛠 알고리즘 접근 방식 이 문제는 DP(동적 프로그래밍) 을 사용해 해결할 수 있습니다.우리는 다음 조건을 만족하는 점화식을 세울 수 있습니다. dp[i][j] : 길이가 i이고, 마지막 자릿수가 j인 오르막 수의 개수dp[i][j] = dp[i][j+1] + dp[i-1][j]끝자리가 j 이..