박카스러버

https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 저는 해당 문제를 플루이드-워샬로 해결하였습니다. 처음에 연결되면 경유지를 그 값으로 초기화시켜주었습니다. 그리고 플루이드-워샬 알고리즘으로 값이 변경되면 경유지도 같이 변경해주었습니다. package BOJ.ETC; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.u..

https://programmers.co.kr/learn/courses/30/lessons/92335 코딩테스트 연습 - k진수에서 소수 개수 구하기 문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소 programmers.co.kr 저는 먼저 수를 k진수의 String 값으로 변경하였습니다. (k진수로 변환은 수를 계속 k로 모듈러연산을 하고 이 값을 reverse하였습니다.) 이 결과값(String)을 0 을 기준으로 나누고 각각의 값이 소수인지를 판별하여 문제를 풀었습니다. package Programmers.KAKAO_2022; im..

https://programmers.co.kr/learn/courses/30/lessons/92334 코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr 저는 Map(map)을 이용해 사용자와 인덱스를 매핑시켰습니다. Set(isCheckReportor)를 이용해 각각의 인덱스에 대해 신고했는지를 판단하였고, List(reports)를 통해 누가 이사람을 신고하였는지를 저장하였습니다. 마지막으로 List(reports)를 통해 각각의 사람이 몇개의 결과 메일을 받았는지를 확인하였습니다. package Pr..

https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 저는 해당 문제를 조합과 BFS를 통해서 문제를 해결하였습니다. choice를 통해서 조합으로 2를 m개만큼 선택하고 q에 넣어서 BFS를 사용하였습니다. check를 통해 벽을 제외한 모든 곳을 방문하였는지 체크하였습니다. 이때 바이러스가 방문한 곳을 2로 변경하여 처리하는 것이 아니라 map과 visited 배열을 통해 확인하였습니다. 해당 좌표가 map에서 1이 아니고 (벽이 아니고) 방문한 적이 없..

https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 저는 해당 문제를 DP를 활용하여 문제를 해결하였습니다. 해당 DP[depth] = 카드를 살 수 있는 수가 depth만큼 남았을때 최소 값을 가지게 하였습니다. package BOJ.DP; import java.io.BufferedReader; import java.io.InputStream; import java.io.InputStreamReader; import java.util.StringTo..

https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 저는 해당 문제를 BFS를 통해서 문제를 해결하였습니다. 처음 생각으로는 플루이드-워샬을 생각하였지만, 플루이드 워샬을 시간복잡도 O(n^3)이기 때문에 N의 범위를 보고 시간초과가 나올 것이라고 생각하였습니다. 저는 BFS를 하여 시작점부터 탐색해 가중치가 K보가 크다면 계속 진행하고 작다면 진행하지 않게 구현하여 문제를 해결하였습니다. pac..

https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 저는 해당 문제를 LCA를 활용하여 문제를 해결하였습니다. 각각의 노드에 parent와 degree를 통해 부모와 깊이가 어느정도인지를 확인하였습니다. 먼저 알아보고자 하는 노드의 degree를 비교하여 둘이 같은지를 확인하고 다르다면 깊이를 먼저 맞춰주고 부모가 같은지를 재귀적으로 확인합니다. package BOJ.Tree; import jav..

https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 저는 해당 문제를 재귀를 이용하여 문제를 해결하였습니다. 숫자 배열을 통해 각각의 수를 넣어주고 해당 배열이 좋은 수열인지를 판단하고 맞다면 계속 진행하고 아니라면 진행하지 않았습니다. (처음에는 모든 수를 구하고 좋은 수열인지 판단하였지만 이렇게하면 시간초과를 피할 수 없습니다.) 위의 방법은 int배열을 통해 문제를 해결하였고, 밑의 방법은 substring을 통해 문제를 해결하였습니다. 개인적으로 메모리..

https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 저는 해당 문제를 dfs를 통해서 문제를 해결하였습니다. 저는 dfs의 파라미터로 이전 좌표를 줌으로써 이전 좌표로 가지 않도록 하였고, visited배열을 통해서 방문 체크를 하였습니다. 해당 좌표의 값이 같고 바로 이전 좌표가 아니면서 방문한 기록이 있다면 사이클이 있다고 판단하여 문제를 해결하였습니다. package BOJ.DFS; import java.io.BufferedReade..

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 저는 해당 문제를 한번 정렬해서 문제를 해결하였습니다. 오름차순 정렬을 하게 되면 해당 값보다 뒤에 있는 것들은 이 값보다 크기 때문에 해당 무게와 뒤에 있는 로프의 개수만큼의 무게를 들 수 있게 됩니다. 이 값들의 최대 값을 결과로 출력하였습니다. package BOJ.ETC; import java.io.BufferedReader; import java.io.InputStreamRead..