본문 바로가기

boj127

[Java] BOJ 1647번 도시 분할 계획 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 크루스칼 알고리즘을 사용하여 해결했습니다. 크루스칼을 사용할 때, 가중치를 기준으로 오름차순 정렬을 시켜야 하는데 이때 Arrays.sort()를 사용하는 것보다 PriorityQueue를 사용하는 게 약 2배 정도 빨랐습니다. 자세한 내용은 코드의 주석을 참고해주세요. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputSt.. 2021. 8. 31.
[Java] BOJ 1744번 수 묶기 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 풀이 정렬을 사용해서 최대값을 만들도록 하여 해결했습니다. 자세한 사항은 코드의 주석을 참고해주세요. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static int N, answer; public static int[] arr; public .. 2021. 8. 30.
[Java] BOJ 13913번 숨바꼭질 4 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS를 사용하여 해결했습니다. 경로를 기록하기 위해 배열을 초기화할 때, 점은 0부터 시작해야 한다는 것을 주의해야합니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Qu.. 2021. 8. 26.
[Java] BOJ 1963번 소수 경로 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 풀이 에라토스테네스의 체와 BFS를 사용하여 해결했습니다. 이때, 미리 4자리 까지의 소수를 구하고 판별하는 방법과 매번 숫자가 소수인지를 판별하는 방법을 따로 시도했었는데 미리 4자리 까지의 소수를 구하여 판별하는 방법이 좀더 빠름을 알 수 있었습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedLis.. 2021. 8. 25.
[Java] BOJ 14002번 가장 긴 증가하는 부분 수열 4 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 DP를 사용하여 해결했습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static int N, answer; public static St.. 2021. 8. 24.
[Java] BOJ 5052번 전화번호 목록 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 풀이 Trie를 사용해서 해결했습니다. 자바를 사용한 Trie 코드를 잘 설명한 블로그가 있어 링크를 공유하겠습니다. [자료구조] Trie(트라이)-2 : 자바로 구현하기 안녕하세요. 개발개입니다. 지난 시간 기초 개념에 이어, Trie를 자바로 구현하는 과정을 알아보겠습니다. 구현 과정에서 람다를 사용하기 때문에 Java8이상으로 진행합니다. [KR/자료구조] - [자료 the-dev.tistory.com 코드 import java.io.. 2021. 8. 23.

티스토리툴바