ImJay

📌 [BOJ/Java] 12422. 창문 깨기 (Large)🔗 문제 링크📖 문제 해석본 문제는 K개의 창문으로 둘러싸인 방에서 진행되는 상황을 모델링한다. 창문은 기본적으로 돌 한 개에 깨지나, H개의 창문은 강화되어 있어 첫 번째 돌은 견디고 두 번째 돌에 깨진다. 모임 전에 M명의 일꾼이 각각 무작위로 한 창문을 선택하여 추가 강화 작업을 수행하며, 한 번 강화할 때마다 해당 창문은 돌을 한 번 더 버틸 수 있다. 모임 당일에는 N명의 악당이 각자 한 개의 창문을 선택하여 돌을 던지며, 이미 깨진 창문에 돌이 던져지면 돌은 그대로 통과한다. 문제의 목표는 모임 후에 최소 한 개 이상의 창문이 깨질 확률을 구하는 것이다.🛠️ 풀이 과정본 문제는 각 창문의 내구성을 강화와 돌 던지기의 결과로 모델..

🌍💥 [BOJ/Java] 3628. Knockdown 💣🔥🔗 문제 링크📌 3628번 - Knockdown📖 문제 해석이 문제는 전 세계를 파괴하기 위해 특정 지점에 폭탄을 배치하는 시나리오를 다룬다. 💀💣각 폭탄은 동일한 파괴 반경을 가지며, 전 세계를 파괴할 수 있는 최소한의 반경을 찾아야 한다. 🌍➡️💥지구는 반지름이 1인 단위 구(Sphere) 로 모델링되며, 폭탄의 위치는 위도(latitude, φ)와 경도(longitude, λ) 로 주어진다.거리는 구면 거리(Spherical Distance) 로 측정된다. 🌐📏🧐 풀이 과정1️⃣ 구 좌표 변환 (위도/경도 → 3D 좌표) 🗺️➡️🛸지구는 구형이므로, 주어진 위도와 경도를 3D 좌표계로 변환해야 한다.위도(φ)와 경..

📌 [BOJ/Java] 6902. Orko🔗 문제 링크: 문제 보기📖 문제 해석Dumitru가 이상한 꿈을 꾸게 된다. 꿈 속에서 문이 잠긴 방에 갇힌 Dumitru는 n개의 박스를 발견하며, 각 박스에는 m개의 접시가 있다. 각 접시에는 1 이상의 정수가 적혀 있다. 그러던 중, 두 개의 정수 k와 l이 적힌 쪽지를 발견하고, 쪽지에는 아래와 같은 작업을 하라는 지시가 적혀 있다. 1단계: 첫 번째 박스부터 n번째 박스까지 순서대로 각 박스에서 한 개의 접시를 선택한다. 선택한 접시의 숫자를 노트에 기록한 후, 해당 접시의 숫자를 1로 변경한다. 2단계: n-1번째 박스부터 두 번째 박스까지 역순으로 각 박스에서 한 개의 접시를 선택한다.목표는 노트에 기록된 숫자들의 곱이 k로 나누어 떨어지도록 ..

📌 [BOJ/Java] 5266. Strange Dream🔗 문제 링크: 문제 보기📖 문제 해석Dumitru가 이상한 꿈을 꿨다. 꿈속에서 문이 잠긴 방에 갇힌 Dumitru는 n개의 박스를 발견했다. 각 박스에는 m개의 접시가 있었고, 각 접시에는 1 이상의 정수가 적혀 있었다. 그러던 중 두 개의 정수 k와 l이 적힌 쪽지를 발견했다. 쪽지에는 다음과 같은 작업을 하라고 되어 있었다. 1단계: 첫 번째 박스부터 n번째 박스까지 순서대로 각 박스에서 한 개의 접시를 선택한다. 선택한 접시의 숫자를 노트에 기록한 후, 해당 접시의 숫자를 1로 바꾼다.2단계: n-1번째 박스부터 두 번째 박스까지 역순으로 각 박스에서 한 개의 접시를 선택한다.목표는 노트에 기록된 숫자들의 곱이 k로 나누어 떨어지도록..

📌 [BOJ/Java] 11404. 플로이드문제 링크💡 문제 해석N개의 도시가 있고, M개의 버스 노선이 존재한다.각 버스는 특정한 비용이 있으며, 도시 간 최단 비용을 구하는 문제이다.🔹 주어진 정보N: 도시의 개수 (2 ≤ N ≤ 100)M: 버스 노선의 개수 (1 ≤ M ≤ 100,000)A B C: A번 도시에서 B번 도시로 가는 비용이 C (중복 가능)✅ 목표:1️⃣ 모든 도시 쌍(i → j)에 대한 최소 비용 경로를 구하기2️⃣ 경로가 없는 경우 0을 출력📝 풀이 과정1️⃣ 플로이드-워셜 알고리즘 사용모든 노드에서 모든 노드까지의 최단 거리를 구하는 문제이므로 플로이드-워셜 알고리즘을 사용시간 복잡도: O(N³), N=100이므로 충분히 가능2️⃣ 초기화무한대(INF) 값 설정 (dis..

📌 [BOJ/Java] 2931. 가스관문제 링크💡 문제 해석도시에는 여러 개의 가스관이 설치되어 있으며, 가스관은 일정한 패턴의 블록으로 이루어져 있다.어느 날 하나의 블록이 사라지는 사고가 발생하여, 이를 찾아 원래의 블록을 복구해야 한다.🔹 주어진 정보N × M 크기의 도시 지도 (.: 빈칸, + - | 1 2 3 4 M Z: 가스관)M: 가스가 시작되는 위치Z: 가스가 도착하는 위치✅ 목표:1️⃣ 사라진 블록의 위치를 찾아 출력2️⃣ 해당 위치에 들어갈 올바른 블록 종류를 출력📝 풀이 과정1️⃣ 사라진 블록(.) 찾기가스관을 따라가다가 연결이 끊긴 지점을 찾는다.2️⃣ 사라진 블록이 가질 수 있는 형태 탐색+ - | 1 2 3 4 중 올바른 블록을 결정연결된 블록들의 방향을 고려하여 가능한..

📌 [BOJ/Java] 11657. 타임머신문제 링크💡 문제 해석한 도시에서 다른 도시로 이동하는 버스 노선이 주어진다.일부 노선에는 음의 가중치(시간)가 존재하며, 음수 사이클이 발생할 수도 있다.🔹 주어진 정보N: 도시의 개수 (노드)M: 버스 노선의 개수 (간선)A B C: A번 도시에서 B번 도시로 가는 시간이 C(양수 또는 음수)✅ 목표:1️⃣ 1번 도시에서 모든 도시로 가는 최단 시간을 구한다.2️⃣ 음수 사이클이 존재하는지 판별한다.3 41 2 41 3 32 3 -13 1 -2🚀 1 → 2 → 3 → 1로 돌아오면 음수 사이클 발생!📝 풀이 과정1️⃣ 벨만-포드 (Bellman-Ford) 알고리즘 사용✔ 음수 가중치가 존재할 수 있기 때문에 다익스트라가 아닌 벨만-포드 알고리즘을 사..

📌 [BOJ/Java] 1981. 배열에서 이동문제 링크💡 문제 해석N × N 크기의 2차원 배열이 주어진다.왼쪽 상단 (0,0)에서 시작하여 오른쪽 하단 (N-1, N-1)까지 이동하는 경로를 찾아야 한다.🔹 이동 조건상하좌우 이동 가능이동 중 최소값과 최대값의 차이(max - min)가 최소가 되어야 한다.✅ 목표:이동 경로에서의 최소값과 최대값의 차이를 최소화하는 값을 구하는 것!📝 풀이 과정1️⃣ 이분 탐색 + BFS 활용✔ 이분 탐색의 범위:배열의 값이 0 ~ 200이므로 최소값을 설정할 수 있는 범위를 이분 탐색최소값을 low, 최대값을 high로 두고 탐색✔ BFS로 경로 탐색:low부터 low + 최소 차이를 만족하는 값들을 BFS로 탐색이동 가능하면 mid 값을 줄이고, 불가능하면..

📌 [BOJ/Java] 9370. 미확인 도착지문제 링크💡 문제 해석어떤 도시에서 출발하여 목적지 후보들 중 특정 경로를 반드시 거쳐 도착하는 경우를 찾아야 한다.즉, 출발지에서 특정 도로를 지나 목적지에 도달할 수 있는지를 확인하는 문제이다.🚗 주어진 정보:n: 교차로(노드) 개수m: 도로(간선) 개수t: 목적지 후보 개수s: 출발지g, h: 반드시 지나야 하는 도로의 두 정점m개의 간선 정보 (양방향, 가중치 포함)t개의 목적지 후보🚀 목표:s → 목적지로 가는 최단 경로 중 g-h 도로를 반드시 지나야 하는 경우 찾기가능한 목적지들을 오름차순 출력예제 입력: 26 9 22 3 61 2 11 3 22 4 42 5 33 6 54 6 25 6 346 위의 예제에서 2 → 6으로 갈 때 3-6을 반..

📌 [BOJ/Java] 1039. 교환문제 링크💡 문제 해석자연수 N(최대 1,000,000)과 교환 횟수 K(최대 10)가 주어진다.숫자 N의 각 자릿수를 정확히 K번 교환하여 만들 수 있는 가장 큰 수를 구해야 한다.단, 0으로 시작하는 숫자는 불가능하므로, 교환 결과가 0으로 시작하면 해당 경우는 제외해야 한다.예를 들어,✅ N = 132, K = 1일 때 → (312, 231) 중 312가 최대✅ N = 100, K = 1일 때 → 가능한 교환이 없으므로 -1문제의 핵심은 BFS(너비 우선 탐색)를 사용하여 가능한 모든 숫자 조합을 탐색하는 것이다.📝 풀이 과정1️⃣ BFS를 활용한 완전 탐색현재 숫자 상태를 Queue에 저장하고, Set을 활용해 방문 여부를 체크한다.K번 동안 모든 가능한..