https://www.acmicpc.net/problem/11048백준 11048번: 이동하기 문제 풀이 (Java)안녕하세요! 이번에는 백준 11048번 '이동하기' 문제를 Java로 해결하는 과정을 공유하려고 합니다. 이 문제는 주어진 미로에서 가장 많은 사탕을 얻는 경로를 찾는 동적 계획법(Dynamic Programming) 문제입니다.문제 분석(1, 1) 위치에서 시작하여 (N, M) 위치까지 이동하면서 사탕을 줍는 문제입니다. 이동은 오른쪽, 아래, 또는 오른쪽 아래 대각선으로만 가능합니다. 각 칸에 놓인 사탕의 개수가 주어졌을 때, 얻을 수 있는 사탕의 최대 개수를 구해야 합니다.해결 아이디어: 동적 계획법 (DP)이 문제는 DP를 사용하기에 아주 적합합니다. dp[i][j]를 '(i, j)..

# 백준 1309번: 동물원 문제 풀이 (Java) 안녕하세요! 오늘은 백준 알고리즘 1309번 '동물원' 문제를 Java로 해결하는 방법에 대해 알아보겠습니다. 이 문제는 동적 계획법(Dynamic Programming)을 활용하는 대표적인 문제입니다. ## 문제 이해 문제는 2xN 크기의 우리에 사자를 배치하는 경우의 수를 찾는 것입니다. 단, 사자들은 가로로도, 세로로도 붙어있을 수 없습니다. ## 해결 전략: 동적 계획법 이 문제는 N번째 줄에 사자를 어떻게 배치하는지에 따라 경우의 수가 달라집니다. N번째 줄의 상태는 다음 세 가지로 나눌 수 있습니다. 1. 사자를 배치하지 않는 경우2. 왼쪽 칸에만 사자를 배치하는 경우3. 오른쪽 칸에만 사자를 배치하는 경우 하지만 제공된 코드는 더 간결한 점..

✨ 자바로 푸는 가장 큰 증가하는 부분 수열 문제 풀이 📌 문제 개요 “가장 큰 증가하는 부분 수열” 문제는 다음과 같은 조건을 만족하는 부분 수열을 찾는 문제입니다. 수열 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 이..

✨ 자바로 푸는 전력난 문제 풀이 📌 문제 개요 “전력난” 문제는 모든 집(노드)을 전깃줄(간선)로 잇되,기존 모든 전선 설치 비용에서 최소한의 유지 비용만 남기기 위한 문제입니다. 즉, 모든 집이 연결되어야 하고최소한의 전기선만 남겨절약 가능한 비용을 구하는 것이 목표입니다. 이 구조는 전형적인 최소 신장 트리(MST) 문제입니다. 💡 예제 입력7 110 1 70 3 51 2 81 3 91 4 72 4 53 4 153 5 64 5 84 6 95 6 110 0 🛠 알고리즘 접근 방식 전체 간선 비용 합계를 구하고크루스칼 알고리즘으로 최소 신장 트리를 구성전체 비용 - MST 비용 = 절약된 전기 요금 ✅ 핵심 아이디어 간선을 비용 순으로 정렬하고,Union-Find(서로소 집합)을 통해 사이..

🔁 자바로 푸는 사이클 게임 문제 풀이 📌 문제 개요 백준 20040 - 사이클 게임 문제는N개의 정점이 있고, M개의 간선을 순차적으로 연결할 때사이클이 처음 생기는 시점을 출력하는 문제입니다. 간선은 차례로 연결되며,간선을 연결할 때 사이클이 생기면 그 **차례(1-indexed)**를 출력끝까지 사이클이 없으면 0을 출력 💡 예제 입력6 50 11 22 30 34 5 예제 출력4 🧠 알고리즘 접근 방식 이 문제는 전형적인 Union-Find(서로소 집합) 알고리즘을 활용해사이클을 탐지하는 문제입니다. 간선을 하나씩 연결하며, 두 노드가 이미 같은 집합이면 사이클 발생그렇지 않으면 두 집합을 합침 (union)사이클이 생긴 첫 번째 간선의 번호를 출력 🧾 코드 해설// 부모 배열 초기..

https://www.acmicpc.net/problem/9370   📌 자바(Java)로 푸는 미확인 도착지 문제 - 백준 9370 🚗📍 🔎 문제 개요 백준 9370번 - 미확인 도착지 문제입니다.출발지(S)에서 목적지 후보들 중,특정 도로(G-H)를 반드시 지나면서 도달할 수 있는 목적지를 찾아야 합니다.다익스트라 알고리즘을 활용하여 최단 경로를 구하는 문제입니다. 💡 예제 입력26 9 21 2 31 2 11 3 22 3 23 4 33 5 54 5 44 6 15 6 256💡 예제 출력65 6➡ 목적지 후보 중 특정 도로(G-H)를 지나면서 도달할 수 있는 곳을 출력 🛠 알고리즘 접근 방식 이 문제를 해결하기 위해 다익스트라 최단 경로 알고리즘(Dijkstra) 을 활용합니다. ✏️ 주요 ..