박카스러버

https://programmers.co.kr/learn/courses/30/lessons/12979 코딩테스트 연습 - 기지국 설치 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5 programmers.co.kr 저는 해당 문제를 구현을 통해서 문제를 해결하였습니다. 저는 1번 아파트와 각각 기지국, N번 아파트의 길이를 기지국의 커버 길이(2w + 1)를 나누고 모듈러 연산을 통해 각각의 사이에 몇 개의 기지국이 들어가야하는지를 구하였습니다. class Solution { public int solution(int n, int[] stations, ..

https://programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 저는 해당 문제를 크루스칼을 통해서 문제를 해결하였습니다. 일단 시작점이나 끝점에 대해서 정해져있지 않아서 BFS나 DFS를 하기에 시간복잡도가 너무 커질 것이라 생각하였습니다. 저는 각 점들이 어떻게된 연결만 된다고 생각하여 MST를 생각하여 크루스칼로 해결하는 방법을 생각하였습니다. 각 ..

https://programmers.co.kr/learn/courses/30/lessons/87390 코딩테스트 연습 - n^2 배열 자르기 정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다. n행 n열 크기의 비어있는 2차원 배열을 만듭니다. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다. 1행 1열부 programmers.co.kr 저는 구현을 통해서 문제를 해결하였습니다. 저는 배열을 만들고 자르고 하지 않고 규칙을 찾아서 문제를 해결하였습니다. 각각의 값이 0,0과 얼마나 떨어져 있냐라기 보다는 행과 열중에 큰 값에 따라 배열 안의 값이 결정 된다는 것을 찾았습니다. 이를 통해 left와 right의 좌표를 찾고 left에서 r..

https://programmers.co.kr/learn/courses/30/lessons/86052 코딩테스트 연습 - 빛의 경로 사이클 각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진 programmers.co.kr 저는 구현을 통해서 해당 문제를 해결하였습니다. 저는 boolean[][][] visited 배열을 통해 해당 경로를 다시 사이클을 체크하지 않도록 구현하였습니다. 또한, Map checkVisited 를 통해 해당 y,x,dir에 대해서 사이클의 몇번째로 진행 중인지를 저장하였습니다. 이를 통해 현재 몇개의 노드를 거쳤는지를 확인하..

https://programmers.co.kr/learn/courses/30/lessons/1832 코딩테스트 연습 - 보행자 천국 3 3 [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 6 3 6 [[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]] 2 programmers.co.kr 저는 해당 문제를 DP와 DFS를 이용하여 문제를 해결하였습니다. 각각의 경로로 가는 경로의 수를 구하였고, DP를 이용하여 한번 계산한 곳은 다시 계산하지 않도록 하였습니다. 저는 DP를 dp[y좌표][x좌표][해당 좌표로 어떤 방향으로 왔는지]로 정의하였습니다. 해당 좌표를 어떤 방향으로 왔는지에 따라 경로의 경우의 수가 달라지기 때문에 위와 같이 정..

https://programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr 저는 boolean배열을 통해 문제를 해결하였습니다. boolean배열을 visited[y][x][방향]으로 하여 현재 지점에서 가는 방향으로 방문 체크를 하였습니다. 하지만 문제는 처음 가본 길의 길이기 때문에 저는 도착지점에서 출발지점의 방문체크도 같이 진행하였습니다. 이후 visited가 false라면 결과값을 늘리고 아니라면 늘리지 않았습니다. class Solution { private static final int[] dy = {-1,0,1,0}; private static final int[] dx = {0,1,0,-1}; pri..

https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 저는 해당 문제를 BFS를 이용해 문제를 해결하였습니다. 저는 칭찬을 받고 바로 BFS를 돌리지 않고 scores에 각각의 직원들이 받은 칭찬을 저장했습니다. 그리고 BFS를 통해 자신이 받은 칭찬의 수를 각각의 직속 부하에 더해주고, 각각의 직속 부하들도 자신이 처음에 받은 칭찬 + 상사에게 받은 칭찬을 각각의 직속부하들에게 전파하도록 구현하였습니다. (칭찬이 부하가 부하의 직속 부하를 연쇄적..

https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 저는 해당 문제를 이분 탐색을 통해서 해결하였습니다. 저는 이분탐색을 작은 값은 1 큰 값은 1,000,000,000 * 1,000,000,000로 하였습니다. ( N=1 , M = 1,000,000,000 , T1 = 1,000,000,000 이렇게 주어진다면 결과 값이 1,000,000,000 * 1,000,000,000 될 것이라 생각하였습니다.) 이분 탐색을 하면서 그 값안에..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 저는 Best First Search를 통해서 해당 문제를 해결하였습니다. 저는 우선순위 큐를 통해서 가장 시간이 작은 것을 먼저 나오게 하였습니다. 또한, 2 * 100,000 까지만 가도록 하였습니다. 동생이 0부터 100,000사이에만 존재하기 때문에 2 * 100,000 이상 이동하는 것은 의미 없다고 생각하였습니다. package BOJ.bfs; impo..

https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 저는 해당 문제를 다익스트라를 이용해 문제를 해결하였습니다. 다익스트라를 통해 1번부터 각 점에 대해 최소 거리를 구하였습니다. 저는 다익스트라를 진행하면서 연결되어 있지 않거나 최소 길이가 k초과가 된다면 바로 리턴하도록 하였습니다. package Programmers.ETC; import java.util.ArrayList; impo..