b1002. 터렛
·
Algorithm & Data Structures/BOJ
https://www.acmicpc.net/problem/1002 🎯 자바로 푸는 터렛 📌 문제 개요 두 터렛이 각각의 위치에서 일정한 반지름만큼의 범위를 감지한다.두 터렛이 동시에 감지할 수 있는 적의 위치 좌표 수를 구하는 문제이다. 터렛의 감지 범위는 원이 되고,두 원이 만나는 지점의 개수를 구하는 기하학적 문제이다. 🧪 예제 입력/출력 예제 입력30 0 13 40 0 370 0 3 0 7 41 1 1 1 1 5 예제 출력210 💡 핵심 아이디어 두 원이 만나거나, 만나지 않는 경우를 기하학적으로 분류하면 된다. 두 원의 중심 거리 = d반지름 각각 r1, r2조건설명결과d == 0 && r1 == r2원이 완전히 겹침 (무한히 많은 점)-1d > r1 + r2원이 서로 멀리 떨어..
b17413. 촌수계산
·
Algorithm & Data Structures/BOJ
https://www.acmicpc.net/problem/17413 🔄 자바로 푸는 단어뒤집기 2 📌 문제 개요 HTML 태그와 단어가 섞여 있는 문자열이 주어진다. 로 감싸진 부분은 그대로 출력하고나머지 단어들은 뒤집어서 출력해야 한다.단, 공백 단위로만 단어를 나누며, 태그 안에서는 문자를 뒤집지 않는다. 💡 예제 입력 & 출력 입력baekjoon online judge 출력noojkeab enilno egduj 입력tag 출력gat 🧠 알고리즘 접근 방식 문자열을 한 글자씩 순회하며,가 나오면 태그 시작 → isTag = true>가 나오면 태그 끝 → isTag = false태그 바깥에서는 단어를 StringBuilder에 저장하고, 공백이나 태그 시작 시 뒤집어서 출력마지막에 남..
b1068. 트리
·
Algorithm & Data Structures/BOJ
https://www.acmicpc.net/problem/1068 🌲 자바로 푸는 트리 문제 풀이 (백준 1068 - 트리) 📌 문제 개요 N개의 노드로 이루어진 트리가 주어짐노드 중 하나를 삭제했을 때, 남은 트리의 리프 노드 개수를 구하는 문제 제약 조건 트리의 노드는 0번부터 N-1번까지루트는 부모가 -1인 노드삭제 시 해당 노드와 그 하위 노드 전부 제거 💡 예제 입력5-1 0 0 1 12→ 노드 2번을 지우면, 남은 트리 구조는 다음과 같다: 0 / \ 1 (X) / \ 3 4→ 리프 노드는 3, 4 → 2개 예제 출력2 🧠 알고리즘 접근 방식 입력 배열을 기반으로 트리 구조 생성tree[i] = [자식1, 자식2, ...]..
b1655. 가운데를 말해요
·
Algorithm & Data Structures/BOJ
https://www.acmicpc.net/problem/1655 🎤 자바로 푸는 가운데를 말해요 문제 풀이 📌 문제 개요 숫자가 하나씩 주어질 때마다, 지금까지 입력된 수들 중 가운데 수를 출력하는 문제입니다.단, 입력은 실시간으로 주어지며, 모든 수는 정수입니다. 💡 예제 입력715210-9975 예제 출력1 1 2 2 2 2 5 🛠 알고리즘 접근 방식 이 문제는 중간값(Median)을 실시간으로 관리하는 것이 핵심입니다. ✅ 핵심 아이디어: 두 개의 힙(PriorityQueue) 최대 힙 (왼쪽): 중간값보다 작은 수들을 저장최소 힙 (오른쪽): 중간값보다 큰 수들을 저장중간값은 항상 최대 힙의 top에 위치하도록 관리 힙의 크기를 조정하면서 항상 최대 힙 ≥ 최소 힙 ..
b1774. 우주신과의 교감
·
Algorithm & Data Structures/BOJ
https://www.acmicpc.net/problem/1774 🌌 자바로 푸는 우주신과의 교감 문제 풀이 📌 문제 개요 백준 1774번 우주신과의 교감 문제는N개의 신들과 이미 연결된 M개의 통로 정보가 주어졌을 때,모든 우주신이 연결되도록 추가로 연결해야 할 최소 거리의 합을 구하는 문제입니다. 각 우주신은 2차원 좌표 위에 존재이미 연결된 통로는 추가 비용 없이 사용 가능목표는 전체 우주신을 연결하는 최소 비용 💡 예제 입력4 11 12 22 43 31 4 예제 출력2.00 🛠 알고리즘 접근 방식 이 문제는 기존 연결 정보를 고려한 최소 신장 트리(MST) 문제입니다. ✅ 핵심 아이디어 크루스칼 알고리즘을 사용해 거리 기준 오름차순 간선 선택M개의 이미 연결된 통로는 먼저 uni..
b4386. 별자리 만들기
·
Algorithm & Data Structures/BOJ
https://www.acmicpc.net/problem/4386 ✨ 자바로 푸는 별자리 만들기 문제 풀이 📌 문제 개요 백준 4386번 “별자리 만들기”는주어진 N개의 별 좌표를 기반으로 별자리를 만들 때,모든 별을 연결하면서 최소한의 선분 길이 합을 구하는 문제입니다. 즉, 모든 별을 잇되 최소 비용으로 연결하는 구조를 요구하며, 이는 전형적인 최소 신장 트리(MST, Minimum Spanning Tree) 문제입니다. 💡 예제 입력31.0 1.02.0 2.02.0 4.0 예제 출력3.41 🛠 알고리즘 접근 방식 별들 간 거리를 간선으로 보고,이 중에서 가장 적은 거리의 간선들만을 선택해 모든 별을 연결해야 합니다. 이를 위해 프림 알고리즘을 사용합니다.(크루스칼도 가능하지만, 이 코..
b20040. 사이클게임
·
Algorithm & Data Structures/BOJ
🔁 자바로 푸는 사이클 게임 문제 풀이 📌 문제 개요 백준 20040 - 사이클 게임 문제는N개의 정점이 있고, M개의 간선을 순차적으로 연결할 때사이클이 처음 생기는 시점을 출력하는 문제입니다. 간선은 차례로 연결되며,간선을 연결할 때 사이클이 생기면 그 **차례(1-indexed)**를 출력끝까지 사이클이 없으면 0을 출력 💡 예제 입력6 50 11 22 30 34 5 예제 출력4 🧠 알고리즘 접근 방식 이 문제는 전형적인 Union-Find(서로소 집합) 알고리즘을 활용해사이클을 탐지하는 문제입니다. 간선을 하나씩 연결하며, 두 노드가 이미 같은 집합이면 사이클 발생그렇지 않으면 두 집합을 합침 (union)사이클이 생긴 첫 번째 간선의 번호를 출력 🧾 코드 해설// 부모 배열 초기..
b9372. 상근이의 여행
·
Algorithm & Data Structures/BOJ
https://www.acmicpc.net/problem/9372 🛫 자바로 푸는 상근이의 여행 문제 풀이 📌 문제 개요 백준 9372번 “상근이의 여행” 문제는N개의 국가와 M개의 비행기 노선이 주어졌을 때,모든 국가를 방문할 수 있는 최소한의 비행기 수를 구하는 문제입니다. 비행 노선은 양방향(왕복)입니다.주어진 국가와 노선들은 항상 연결 그래프를 이룹니다.중요한 조건은 “직접 연결된 비행기만 타는 것이 아니라, 경유도 가능“하다는 점입니다. 💡 예제 입력23 31 22 31 35 42 12 34 34 5 예제 출력24 🛠 알고리즘 접근 방식 이 문제는 사실상 그래프 이론 문제이며,그래프가 연결되어 있다는 전제 하에, 모든 노드를 방문하려면 필요한 간선 수는 다음과 같습니다: ✅ 핵..
b4195. 친구네트워크
·
Algorithm & Data Structures/BOJ
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) 알고리즘이름이 문자열이기..
b1976. 여행가자
·
Algorithm & Data Structures/BOJ
https://www.acmicpc.net/problem/1976 ✈ 자바로 푸는 여행가자 문제 풀이📌 문제 개요 여행 계획에 따라 여러 도시를 순서대로 방문할 수 있는지 판단하는 문제입니다.도시 간의 연결 여부가 주어지며, 여행 경로에 포함된 모든 도시가 **같은 네트워크(연결된 그룹)**에 있어야 합니다. 1은 도시간 연결을 의미하고 0은 연결이 없음을 의미합니다.Union-Find(Disjoint Set)를 활용하여 각 도시가 같은 그룹에 속하는지 판단하면 됩니다. 💡 예제 입력330 1 01 0 10 1 01 2 3출력:YES 🧠 알고리즘 접근 방식 Union-Find 자료구조를 사용해 도시 간 연결 정보를 하나의 집합으로 병합합니다.여행 계획에 포함된 도시들이 **모두 같은 집합..