프로그래민👨‍💻

단순 구현 문제이다. 단순 구현 문제이긴 하지만 조건들이 까다롭고 문제이해가 오래 걸려서 구현함에 있어 고생을 하였다. 이 문제를 품에 있어 시간을 60진수로 간주하고 int화 시켜서 문제를 접근하였다. 그리고 bus들을 map에 저장하여 남은 자리를들을 체크해주었고, 크루들을 한명씩 체크하며 버스의 마지막자리에 탈때의 시간, 그리고 남는 버스자리의 시간들을 비교하여 콘이 탈 시간의 최대값을 찾았다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 6..

모든 정점을 N-1개로 연결하는 MST 문제이다. MST를 해결하기 위해선 간선기준인 Kruskal 알고리즘과 정점기준인 Prim 알고리즘을 사용할 수 있다. 두 문제는 어쨋든 출발점, 도착점 비용을 알아야하기 때문에 문제에서 비용을 구하는 방법을 생각해보았다. N이 최대 100,000임으로 2중for문은 사용불가하여 고민해본 결과, 전체 정점을 x,y,z로 각 각 정렬했을때 하나 뒤의 정점과의 x,y,z 차이를 이용하여 간선을 구하는 방법을 고안하였다. 이렇게 모든 간선들의 비용을 PriorityQueue에 저장한다음 UnionFind를 이용하여 MST를 구하였다. 그래프의 간선들을 만듬에 있어 충분한 고민이 필요했던 문제였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17..

간단해 보이는 문제지만 동적프로그래밍을 사용해야하는 문제이다. N=1000 이고 M=100000이므로 최악의 경우에는 for문을 사용하였을때 1억을 넘어가므로 일반적인 방식으로는 풀이를 할 수 없다. 그래서 arr에 저장할때 행별로 더해주며 누적값을 저장하였다. 그 후 행별로 누적된 값을 이용하여 연산을 하는 방식으로 문제를 해결해주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 package boj2; import java.io.BufferedReader; import java.io.InputS..

유니온파인드를 이용하는 문제이다. 프로그래머스의 호텔방배정과 상당히 유사한 문제이다. 다만 이문제는 이하를 찾는점이 앞의 문제와 다른점이다. 비행기의 번호가 들어오면 그 비행기의 부모를 찾아주고, 그찾은 부모와 하나 부모이하를 union해주는 과정을 거친다. 만일 비행기의 부모가 0이 오면 더이상 추가할수가 없다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 package boj2; import java.io.BufferedReader; import java.io.InputStream..

유니온 파인드를 이용하는 문제이다. 이차원 배열상 서로 연결되어있다고 표시된 지역은 merge(union)함수를 이용하여 서로 부모를 맞추어주는 작업을 끝낸다음 마지막에 find를 이용하여 모든 여행지점이 같은 부모를 같는지 확인하는 방식으로 풀이하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 package boj1; i..

최소 비용을 구하는 문제이다. 이 문제의 경우엔 최대 n이 100이하이고 출력시 모든 점에서 모든 점에 대한 최소비용을 출력해야함으로 가장 간단히 구현할 수 있는 플로이드와샬 알고리즘을 사용하면 된다. 플로이드와샬은 3중 for문을 이용한 알고리즘으로 만일 한점을 거친 거리가 더 가깝다면 갱신을 해주는 식으로 모든 정정들을 확인하는 알고리즘이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 package boj2; import java.io...

이문제는 복잡한 구현 문제이다. 문제에 주어진 대로 구현을 하면 되는데, 구현을 함에 있어 재귀와 다양한 함수를 활용하였다. 재귀와 백트래킹을 같이 사용하였는데 2차원 배열의 백트래킹을 할땐 재귀함수 안에서 지역변수로 temp[][] 를 선언하고 원래 2차원 배열을 복사해놓고 재귀가 끝나면 다시 붙여넣는 작업을 통해 백트래킹을 구현할 수 있다. 이 부분에 있어 전역변수로 하다가 코드가 꼬이는 현상이 발생했는데 필히 지역변수를 사용해야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53..

DFS를 이용하여 푸는 문제이다. 유향 그래프이기때문에 하나의 정점을 기준으로 1.정방향 DFS, 2.역뱡항 DFS 둘다를 거쳤을 때 모든 정점을 방문한형태를 나타낸다면 자신의 위치를 알고있는 정점으로 간주할수 있게되는 성질을 이용하여 풀었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 package boj2; import java.io.B..

이 문제는 BFS를 응용하는 문제이다. 문제에서 a~f까지 키가 주어지는데 이것을 가지고 있는 상태에서 움직여야한다. 그래서 비트연산을 통하여 각 Pos클래스에 가지도록 변수 alp를 선언해주었고, 열쇠를 가진상태에서 방문또한 변화가있으므로 visit배열도 3차원으로 visit[R][C][1

비트연산을 이용하는 문제이다. 비트연산 | 을 이용하고 2진수로 바꿔주는 간단한 문제이다. 이문제에선 주의할점은 n의 크기만큼 문자열을 맞추기 위해 공백을 추가하는 작업이 필요한데 이작업이 없다면 테스트케이스에서 틀리는 부분이 존재한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 package programmers; public class Solution_2018카카오_비밀지도 { public static void main(String[] ..