✨ 자바로 푸는 전력난 문제 풀이 📌 문제 개요 “전력난” 문제는 모든 집(노드)을 전깃줄(간선)로 잇되,기존 모든 전선 설치 비용에서 최소한의 유지 비용만 남기기 위한 문제입니다. 즉, 모든 집이 연결되어야 하고최소한의 전기선만 남겨절약 가능한 비용을 구하는 것이 목표입니다. 이 구조는 전형적인 최소 신장 트리(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(서로소 집합)을 통해 사이..

https://www.acmicpc.net/problem/9328 🔑 자바로 푸는 열쇠 문제 풀이 (백준 9328) 📌 문제 개요 감옥의 평면도가 주어졌을 때, 상하좌우 이동을 통해 가능한 많은 문서(’$’)를 얻는 것이 목표입니다. 벽은 *, 빈 공간은 ., 문은 A~Z, 열쇠는 a~z, 문서는 $열쇠가 있어야 문을 통과할 수 있음열쇠는 한 번 획득하면 해당 종류의 문을 모두 열 수 있음감옥의 외곽 어느 지점에서든 침입 가능 💡 예제 입력15 17*****************.............**$**B*A*P*C**X*Y*.X.*y*x*a*p**$*$**$******************cz 예제 출력3 🧠 알고리즘 접근 방식 이 문제는 BFS(너비 우선 탐색) 을 기반으로 풀..

https://www.acmicpc.net/problem/1774 🌌 자바로 푸는 우주신과의 교감 문제 풀이 📌 문제 개요 백준 1774번 우주신과의 교감 문제는N개의 신들과 이미 연결된 M개의 통로 정보가 주어졌을 때,모든 우주신이 연결되도록 추가로 연결해야 할 최소 거리의 합을 구하는 문제입니다. 각 우주신은 2차원 좌표 위에 존재이미 연결된 통로는 추가 비용 없이 사용 가능목표는 전체 우주신을 연결하는 최소 비용 💡 예제 입력4 11 12 22 43 31 4 예제 출력2.00 🛠 알고리즘 접근 방식 이 문제는 기존 연결 정보를 고려한 최소 신장 트리(MST) 문제입니다. ✅ 핵심 아이디어 크루스칼 알고리즘을 사용해 거리 기준 오름차순 간선 선택M개의 이미 연결된 통로는 먼저 uni..

https://www.acmicpc.net/problem/4386 ✨ 자바로 푸는 별자리 만들기 문제 풀이 📌 문제 개요 백준 4386번 “별자리 만들기”는주어진 N개의 별 좌표를 기반으로 별자리를 만들 때,모든 별을 연결하면서 최소한의 선분 길이 합을 구하는 문제입니다. 즉, 모든 별을 잇되 최소 비용으로 연결하는 구조를 요구하며, 이는 전형적인 최소 신장 트리(MST, Minimum Spanning Tree) 문제입니다. 💡 예제 입력31.0 1.02.0 2.02.0 4.0 예제 출력3.41 🛠 알고리즘 접근 방식 별들 간 거리를 간선으로 보고,이 중에서 가장 적은 거리의 간선들만을 선택해 모든 별을 연결해야 합니다. 이를 위해 프림 알고리즘을 사용합니다.(크루스칼도 가능하지만, 이 코..

https://www.acmicpc.net/problem/4195 👥 자바로 푸는 친구 네트워크 문제 풀이 📌 문제 개요 백준 4195번 - 친구 네트워크 문제는여러 명이 친구 관계로 연결될 때,각 관계마다 현재 친구 네트워크의 크기를 출력하는 문제입니다. 친구 관계가 주어짐 (A B → A와 B가 친구)친구 관계가 생길 때마다, A와 B가 속한 전체 네트워크(연결된 집합)의 크기를 출력이름은 문자열로 주어짐 💡 예제 입력23Fred BarneyBarney BettyBetty Wilma3Fred BarneyBetty WilmaBarney Betty 예제 출력2 3 4 2 2 4 🛠 알고리즘 접근 방식 핵심은 Union-Find (Disjoint Set) 알고리즘이름이 문자열이기..

https://www.acmicpc.net/problem/11780 📌 자바(Java)로 푸는 플로이드 2 - 백준 11780 🛣️최단 거리 + 경로 출력까지 포함한 플로이드 워셜(Floyd-Warshall) 🔎 문제 개요 백준 11780 - 플로이드 2는모든 도시 쌍에 대해 최단 경로의 거리를 구하는 것뿐만 아니라,각 최단 경로를 직접 경로로 출력하는 문제입니다. 💡 예제 입력5141 2 21 3 31 4 1... 💡 예제 출력0 2 3 1 1002 1 23 1 32 1 4... 🛠 알고리즘 접근 방식 이 문제는 전형적인 Floyd-Warshall (플로이드-워셜) 알고리즘에✔ 경로 추적까지 덧붙이는 구조입니다. costs[i][j]: 도시 i에서 j까지의 최소 비용lists[i][j..

https://www.acmicpc.net/problem/14002 📌 자바(Java)로 푸는 가장 긴 증가하는 부분수열 4 - 백준 14002 📈최장 증가 부분 수열(LIS)을 구하고, 해당 수열을 출력하라!🔎 문제 개요 백준 14002번 - 가장 긴 증가하는 부분 수열 4 문제는기본적인 LIS(최장 증가 부분 수열) 문제에👉 “LIS 경로까지 출력”이 추가된 버전입니다.💡 예제 입력6 10 20 10 30 20 50 💡 예제 출력4 10 20 30 50 🛠 알고리즘 접근 방식 이 문제는 기본 LIS 문제에서“LIS의 경로를 저장”해야 하기 때문에✔ 단순한 DP 배열뿐 아니라✔ prev[] (이전 인덱스), lastIndex[] (길이별 마지막 인덱스) 추적이 필요합니다. 🔹 핵심..

https://www.acmicpc.net/problem/12852 📌 자바(Java)로 푸는 1로 만들기 2 - 백준 12852 🔢최소 연산 횟수 + 경로 추적까지 하는 DP 문제! 🔎 문제 개요 백준 12852번 - 1로 만들기 2 문제는정수 N이 주어졌을 때,1로 만들기 위해 사용할 수 있는 연산은 다음 세 가지입니다: X → X / 3 (3으로 나누어떨어질 때만)X → X / 2 (2로 나누어떨어질 때만)X → X - 1 최소 연산 횟수를 출력하고그 경로에 해당하는 숫자 순서도 출력해야 합니다. 💡 예제 입력10 💡 예제 출력310 9 3 1 🛠 알고리즘 접근 방식: Dynamic Programming (DP) ✏️ 핵심 전략 dp[i]: i를 1로 만들기 위한 최소 연산 횟수c..

https://www.acmicpc.net/problem/1450   📌 자바(Java)로 푸는 부분 수열의 합 문제 - 백준 1450 🎒 🔎 문제 개요 백준 1450번 - 냅색 문제는최대 N = 30개의 물건이 주어질 때,각 물건의 무게를 더해 총합이 C 이하인 경우의 수를 구하는 문제입니다. 1 ≤ N ≤ 30, 1 ≤ C ≤ 1e9무작정 모든 조합을 돌리면 2³⁰ ≈ 10억 개, 시간 초과 발생❌➡ 그래서 “Meet in the Middle(중간에서 만나기)” 전략을 사용합니다. 🛠 알고리즘 접근 방식: Meet in the Middle  ✏️ 핵심 전략 배열을 반으로 나누고 각각 가능한 부분합의 조합을 모두 구함한 쪽 배열의 조합을 기준으로, 나머지에서 더해도 C 이하가 되는 조합 개수를 ..

https://school.programmers.co.kr/learn/courses/30/lessons/42891 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr   📌 자바(Java)로 푸는 무지의 먹방 라이브 문제 - 프로그래머스 🍜⏱ 🔎 문제 개요 프로그래머스 Lv.4 - 무지의 먹방 라이브 문제는무지가 각 음식의 걸리는 시간만큼 음식을 순서대로 먹고,k초 후에 몇 번째 음식을 먹고 있어야 하는지를 구하는 문제입니다. 단, **음식 순서는 원형(끝나면 처음으로)**이고,시간이 부족하면 -1을 반환해야 합니다. 💡 예제 입력food_times = [3, 1, 2]k = 5 💡 예제 출력1➡ ..