Coding Test/BOJ
[BOJ/JAVA] 1543번: 문서 검색
1543번: 문서 검색 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 키워드 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구현 단어의 길이는 50이고, 문서의 길이는 최대 2500이다. 따라서 단순 문자열 비교 알고리즘을 사용하여 구현해도 무방하다. 가장 앞부터 단어를 만족하는지 체크하고, 그 단어 길이 이후 인덱스 부터 다시 문자열 비교 알고리즘을 사용한다. 왜 가장 앞 부터 단어를 만족하는지 체크하는가? → 최대 몇 번 중복되지 않게 등장하는지 체크하기 위해서, 다음 예시를 보자 문서 : AAAAAAAA ..
[BOJ/JAVA] 23030번: 후다다닥을 이겨 츄르를 받자!
태그: Java https://www.acmicpc.net/problem/23030 23030번: 후다다닥을 이겨 츄르를 받자! 쿠기는 평소 지하철 최단 경로를 탐색하여 소요 시간을 알려주는 '후다다닥' 어플을 사용 중이다. 그러나 쿠기는 걸음이 너무 느려서 '후다다닥'이 알려주는 경로를 따라가면 항상 지하철이 떠 www.acmicpc.net 키워드 지하철은 양방향 모두 통행이 가능하며, 지하철의 방향을 바꿔타는 시간과 지하철을 타기 위해 대기하는 시간은 걸리지 않는다. 환승을 하는 경우 걸어서 이동해야 하므로 사용자는 각자 자신이 환승을 하는 데 걸리는 시간 T 사용자가 환승 시간 T와 출발지, 도착지를 입력하면 최단 경로로 이동하였을 때 걸리는 소요 시간을 알려주는 프로그램 구현 가장 어려웠던 것은 ..
[BOJ/JAVA] 1719번: 택배
태그: Java https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 키워드 경로표는 한 집하장에서 다른 집하장으로 최단경로로 화물을 이동시키기 위해 가장 먼저 거쳐야 하는 집하장을 나타낸 것이다. 구현 바로 이동하는 것이 항상 최단경로를 의미하는 것은 아니다. 따라서 최단 경로를 찾아줘야 한다. 모든 한 노드에서 다른 노드까지의 최단경로를 구하기 위해서 floydWarshall 알고리즘을 사용했다. floydWarshall 알고리즘에서 [i]를 경유한다고 ..
[BOJ/JAVA] 13549번: 숨바꼭질 3
태그: Java 13549번: 숨바꼭질 3 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 키워드 수빈이가 이동하는 방법은 총 3가지 이다. X-1로 이동하는 경우 X+1로 이동하는 경우 2 * X 로 이동하는 경우 (이 때는 시간이 소모되지 않는다.) 가장 빠른 시간을 구해야 하므로, 너비우선탐색을 이용하여 3가지 경우 모두 탐색한다. 최적화 항상 3가지 경우를 모두 탐색해야 할까? 그건 아니다. 2 * X 이동을 하는 경우는 수빈이의 현재 위치(X)가 동생의 위치(K) 보다..
[BOJ/JAVA] 2458번: 키 순서
https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 키워드 N명의 학생들의 키는 모두 다르다. 학생의 수의 최댓값은 500이다. a번 학생의 키가 b번 학생의 키보다 작다면 a→b 그래프가 연결된다. 자신의 키가 몇 번째인지 알 수 있는 학생이 몇명인지 계산하자. 1. N명의 학생들의 키는 모두 다르다. 이를 통해서 연결된 정보만을 통해 학생 구분이 가능하다. 2. 학생의 수의 최댓값은 500이다. a번 학생의 키가 b번 학생의 키보다 작다면 a→b..
[BOJ/JAVA] 11780번: 플로이드 2
https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제에서 알 수 있듯이 FloydWarshall 알고리즘을 사용한다. 근데 응용이 추가된 주요 키워드 도시(n)의 최댓값이 100이다. 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하라 최소 비용에 포함되어있는 도시의 개수 k를 출력하라 도시 i에서 도시 j로 가는 경로를 출력하라 1. 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하라 도시(n)의 최댓값이 100이다. 라는 조건이 ..
[BOJ/JAVA] 11265번: 끝나지 않는 파티
https://www.acmicpc.net/problem/11265 11265번: 끝나지 않는 파티 입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸 www.acmicpc.net 중요한 키워드 모든 파티장이 직접적으로 연결되었다는 것 다른 파티장을 경유해서 더 빨리 가는 경우가 있을 수 있다는 것 A파티장에서 B파티장으로 C시간 내로 갈 수 있는지 판단하는 것 1. 모든 파티장이 직접적으로 연결되어 있다는 것 모든 파티장이 직접적으로 연결되어 있다는 것은 그래프의 모든 노드들이 서로 연결되어있다는 것이다. 그리고 파티장의 크기를 봤을 때..
[BOJ/JAVA] 1287번: 할 수 있다
https://www.acmicpc.net/problem/1287 1287번: 할 수 있다 곱하기가 연산자 우선순위가 빠르므로 5+(1+2)*3 = 5+3*3 = 5+9 = 14가 된다. 연산자의 우선순위는 다음과 같다. (), */, +- 여기서 *와 /가 연산자 우선순위가 같고, +와 -가 연산자 우선순위가 같다. ()가 www.acmicpc.net import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.math.BigInteger; import java..
[BOJ/JAVA] 11866번: 요세푸스 문제 0
https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.StringTokenizer; public class java_11866 { public static void main(..
[BOJ/JAVA] 2064번: IP 주소
https://www.acmicpc.net/problem/2064 2064번: IP 주소 네트워크에 연결되어 있는 컴퓨터들은 각각 하나의 IP 주소를 갖게 된다. 그리고 이러한 IP 주소를 갖는 컴퓨터들이 여러 개 모여서 하나의 IP 네트워크를 구성하게 된다. IP 네트워크는 ‘네트워 www.acmicpc.net import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class java_2064 { stat..