계단을 오르듯이

2차원과 같은 방식으로 접근하였고, 차이점은 방문처리도, 토마토를 넣는 배열도 3차원이고, 방향을 나타내는 배열의 방향이 2개 늘어 6개가 되었다는 점이다. 방향을 나타내는 dir 배열은 똑같은 2차원 배열에서 2차원의 수가 2에서 3으로 늘었다. 배열은 [높이][세로][가로] 로 하였다. 토마토에서 아직 덜 익은 0의 값의 수를 구하였고, 큐에 미리 익은 토마토를 넣어주었다. 큐에는 Node 클래스를 이용해 시간을 나타내는 time의 변수로 연산의 시간을 측정하였다. 익지 않은 토마토가 익게 되면 덜 익은 토마토의 수를 감소시켰고, 그 수가 0이 되면 연산이 종료되며 그 토마토가 익은 시간을 출력한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22..

처음에는 입력받는 문자열의 문자를 배열에 저장하였고, 중복을 줄이기 위해 set을 이용했으나 메모리 초과가 나왔다. 예상은 했으나 딱히 다른 방법이 생각나지 않았다. 검색을 해보니 방식은 26개의 알파벳으로 한정되어있기 때문에 26개의 배열을 마련하고 거기서 해당 문자의 수만큼 배열의 값을 증가시키는 방식을 통해 구현하였고, 그렇게 되면 for문을 돌리면 해당 알파벳의 배열에서 값이 0보다 크면 그 알파벳을 사용하고 아니면 사용하지 못하며, 중복을 방지할 수 있다. 즉, 알파벳 하나씩을 배열에 넣으면 arr[0]도 arr[1] 도 a를 가지고 있다면 for문을 통해 중복이 되지만, arr[0]에 2라는 값으로 2번 들어있다는 것을 의미하면 for문은 0일 때만 a를 선택하므로 중복을 없앨 수 있게 되는 ..

별자리를 최소의 비용으로 만들기 위해 프림 알고리즘을 사용하였다. 우선 Node 클래스를 이용해 각 별의 자리를 배열로 놓고, Edge 클래스를 이용해 최소의 거리를 우선순위 큐를 이용해 구하였다. 마지막은 예시와 맞추기 위해 String.format("%.2f", result); 를 통해 형식을 맞추어 주었다. 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 package a..

Queen은 대각선, 같은 행, 열에 존재하면 서로 공격할 수 있다. 즉, 서로 공격할 수 없는 퀸의 위치는 모두 각각의 위치에서 행과 열에서 만날 수 없고, 대각선 상으로도 위치하고 있지 않아야 한다. 처음에는 메모리 초과가 발생하였다. 각 위치를 비교해야하므로 이전 위치를 Node 클래스를 만들어서 list 비교를 진행했었다. 하지만 그럴 필요 없이 1차원 배열만으로 해결이 가능하였다. 그 이유는 N이 주어졌을 때 N개의 퀸이 위치해야하므로 모든 행에 대해서는 무조건 퀸이 존재해야 만족한다. 따라서 우리는 열의 위치만을 생각하면 된다. 1차원 배열에서 인덱스는 행을 의미하고 행에 따른 배열의 값이 바로 열의 위치를 알려준다고 생각하면 1차원 배열로 모든 퀸의 위치를 알 수 있게 된다. 퀸의 위치는 처..

도시를 분할 때 2개의 도시를 만들고 연결하는 최소의 유지비용을 구하는 문제이다. 최소의 거리값을 구하는 크루스칼 알고리즘을 사용하였다. 우선 최소의 비용을 구하기 위해 가장 작은 비용으로 모든 집을 연결해야했고, 그 중 최소의 연결 비용을 위해 가장 큰 값의 연결 유지비용을 제외해 마을을 나누어야 한다. 문제에서 2개의 도시는 최소 1개 이상의 집이 존재하여야 한다고 하였으므로 각 마을의 집을 모두 최소의 비용으로 연결한 후 마지막 가장 큰 비용으로 연결되어지는 하나의 집을 제외하여 다른 마을로 만들면 그 방식이 가장 최소의 비용으로 모든 집을 연결하고, 가장 큰 비용이 드는 집의 연결을 제거해 하나의 마을로 만드는 것이 최소의 유지비용이 될 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 1..

어려웠다. 분명히 규칙이 있는데 그 규칙을 찾기를 성공하지 못하고 검색을 해보았다. 그리고 투에 모스 수열이 있다는 것을 알게 되었다. 투에-모스 수열 - 위키백과, 우리 모두의 백과사전 이 그래픽은 투에 모스 수열의 반복적이고 상보적인 생성을 나타낸다. 수학에서, 투에-모스 수열(영어: Thue-Morse sequence), 또는 프로헷-투에-모스 수열(영어: Prouhet-Thue-Morse sequence)은 0에서 시작해 ko.wikipedia.org 아래는 투에모스의 점화식이다. 이 점화식을 따라 코드를 작성하였다. 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 package algo; import java.io.Buffer..

5원과 2원이 있기 때문에 거스름돈을 최소로 주기 위해 5원을 최대로 사용했다. 2원을 위해 5원을 최대로 사용할 경우 남은 거스름돈이 짝수가 되도록 하였으며, 나머지 거스름돈에서 2원으로 거스름돈을 주지 못할 경우는 2로 나누었을 때 나머지 값이 존재하는 상황이므로 -1을 출력하고, 그렇지 않은 경우는 거스름돈의 최소값을 출력한다. 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 package algo; import java.io.BufferedReader; import java.io.InputStreamReader; public class B_14916_거스름돈 { public static void main(String[] a..

플로이드-와샬 알고리즘을 이용해야한다. 플로이드 와샬 알고리즘은 O(n^3)의 시간복잡도를 가지며, 모든 정점의 이동거리를 구할 수 있다. 총 n개의 정점이 있다면 1개의 노드가 n-1의 노드까지의 연결 거리를 모두 알 수 있다. 우선 플로이드-와샬 알고리즘을 통해 서로의 연결 상태(간선의 개수)를 알 수 있고, 간선의 개수만큼의 시간이 걸린다. 현재 문제에서는 왕복의 거리이므로 간선의 수 한개당 2의 시간이 걸린다고 생각하고 시간 배열을 채웠다. 그 후, 치킨집을 조합으로 하여 모든 경우의 수를 통해 최소의 거리시간을 구하였다. 우선 2개의 치킨집을 조합으로 구한 후 모든 정점에서 2개의 치킨집 중 가장 가까운 치킨집을 구하여 그 시간을 모든 총 시간을 나타내는 시간에 더해주었고, 이렇게 모든 경우를 ..