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

https://www.acmicpc.net/problem/1516[백준/BOJ] 1516번: 게임 개발 - Java 풀이 (위상 정렬)안녕하세요! 이번 포스팅에서는 백준(BOJ) 1516번 '게임 개발' 문제를 Java로 해결하는 방법을 자세히 알아보겠습니다. 이 문제는 여러 작업과 각 작업의 선행 조건이 주어졌을 때, 각 작업의 최소 완료 시간을 구하는 전형적인 위상 정렬(Topological Sort) 문제입니다.📜 문제 이해문제의 조건은 다음과 같습니다.여러 종류의 건물을 지어야 하며, 각 건물은 짓는 데 특정 시간이 걸린다.어떤 건물들은 특정 건물이 먼저 지어져야만 지을 수 있는 선행 조건(dependency)을 가지고 있다.여러 건물을 동시에 짓는 것이 가능하다.우리가 구해야 할 것은 각 건물..

https://www.acmicpc.net/problem/17404 [백준/BOJ] 17404번: RGB거리 2 - Java 풀이 (DP)안녕하세요! 이번 포스팅에서는 백준(BOJ) 17404번 'RGB거리 2' 문제를 Java로 해결하는 방법을 알아보겠습니다. 이 문제는 유명한 DP 문제인 'RGB거리 1'의 심화 버전으로, 한 가지 제약 조건이 추가되어 난이도가 올라갔습니다.📜 문제 이해: RGB거리 1과의 차이점기본적인 규칙은 RGB거리 1과 동일합니다.집은 1번부터 N번까지 순서대로 있다.각 집은 빨강(R), 초록(G), 파랑(B) 중 하나의 색으로 칠해야 한다.각 집을 특정 색으로 칠하는 비용이 주어진다.이웃한 집은 서로 다른 색으로 칠해야 한다.여기에 가장 중요한 제약 조건이 추가됩니다.1번..

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원을 거슬러 줄 때 ..

https://www.acmicpc.net/problem/1106백준 1106번: 호텔 문제(Java) 풀이안녕하세요! 오늘은 백준 1106번 '호텔' 문제를 동적 계획법(DP)을 활용하여 풀어내는 Java 코드에 대해 알아보겠습니다. 이 문제는 최소 비용으로 특정 목표를 초과 달성해야 하는, 전형적인 Unbounded Knapsack(무제한 배낭) 문제의 변형입니다.문제의 핵심목표: 호텔 홍보를 통해 적어도 C명의 고객을 유치해야 합니다.비용: 각 홍보 활동(도시)마다 비용과 그로 인해 얻는 고객 수가 정해져 있습니다.조건: 모든 홍보 활동은 원하는 만큼 반복해서 수행할 수 있습니다.가장 중요한 포인트는 '적어도 C명'이라는 조건입니다. 즉, C명을 넘어 C+1명, C+5명 등을 유치하는 비용이 오히려..

https://www.acmicpc.net/problem/1890백준 1890번: 점프 문제 풀이 (Java)안녕하세요, 오늘은 백준 1890번 '점프' 문제를 Java로 해결하는 방법을 알아보겠습니다. 이 문제는 동적 계획법(Dynamic Programming)을 사용하여 경로의 개수를 찾는 흥미로운 문제입니다.문제 파악N×N 크기의 게임판이 주어집니다. 각 칸에는 숫자가 적혀 있으며, 이 숫자는 해당 칸에서 점프할 수 있는 거리를 의미합니다. 가장 왼쪽 위 칸(0, 0)에서 시작하여 가장 오른쪽 아래 칸(N-1, N-1)까지 규칙에 맞게 점프하여 도달하는 경로의 개수를 구하는 것이 목표입니다.규칙은 다음과 같습니다.현재 칸 (i, j)에 적힌 숫자가 k라면, 오른쪽으로 k만큼 이동한 (i, j+k)나..