GOSE_KOSE

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 이번 포스팅은 백준 친구 네트워크 자바 풀이를 진행하도록 하겠습니다. 문제 출처: https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 1. 풀이 소스 import java.io.*; import java.util.HashMap; import java.util.Map; import static java.lang.Integer.parseInt; public class Main { sta..

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 이번 문제는 백준 플로이드-와샬(워샬) 문제 플로이드(11404) 자바 풀이를 진행하도록 하겠습니다. 문제 출처: https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 1. 풀이 소스 import java.io.*; import java.util.*; import static java.lang.Integer.parseInt; public class Main { static final int IN..

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 이번 포스팅은 백준 벨만포드 문제 - 타임머신 자바 풀이를 진행하도록 하겠습니다. 문제 출처: https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 1. 풀이 소스 import java.util.*; import java.io.*; import static java.lang.Integer.parseInt; public class Mai..

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 이번 포스팅은 백준 LCS 문제 풀이를 진행하고자 합니다. 문제 출처: https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 풀이 소스 import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = ..

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 이번 포스팅은 백준 이분탐색 문제 랜선 자르기 자바 풀이를 진행하도록 하겠습니다. 문제 출처: https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 1. 풀이 소스 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stri..

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 이번 포스팅은 백준 누적합 문제 - 인간 컴퓨터 상호작용 자바 풀이를 진행하도록 하겠습니다. 문제 출처: https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 1. 풀이 소스 import java.io.*; import java.util.*; import static java.lang.Integer.parseInt; public class Mai..

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 이번 포스팅은 백준 백트래킹 문제 스도쿠 자바 풀이를 진행하도록 하겠습니다. 문제 출처: https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 1. 풀이 소스 import java.util.*; import java.io.*; import static java.lang.Integer.parseInt; public class Main { static boolean sudokuBreak; // 스도..

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 이번 포스팅은 백준 트리의 독립집합 자바 풀이를 진행하도록 하겠습니다. 문제 출처: https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 1. 풀이 소스 import java.io.*; import java.util.*; import static java.lang.Integer.parseInt; public class Main { public static void..

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 이번 포스팅은 백준 트리 DP 문제 트리와 쿼리 자바 풀이를 진행하도록 하겠습니다. 문제 출처: https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 1. 풀이 소스 import java.io.*; import java.util.*; import static java.lang.Integer.parseInt; public class M..

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 이번 포스팅은 백준 유니온 파인드 문제 - 최소 스패닝 트리 자바 풀이를 진행하도록 하겠습니다. 문제 출처: https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 1. 풀이 소스 import java.util.*; import java.io.*; import static java.lang.Integer.parseInt; public class Mai..