계단을 오르듯이

별자리를 최소의 비용으로 만들기 위해 프림 알고리즘을 사용하였다. 우선 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..

yellow를 기준으로 일단 가로 세로의 길이를 구했다. 가로, 세로 모두 yellow를 기준으로 전체 가로, 세로길이는 2씩 커진다. 가로 세로를 구하기 위해서는 약수를 구하는 방식으로 1부터 루트N까지 연산을 통해 반복되지 않게 하였고, 가로의 길이가 항상 크므로 i가 세로가 되도록 하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public int[] solution(int brown, int yellow) { int[] answer = new int[2]; for(int i=1;i

이 문제는 자료구조를 사용하지 않고 2중 for문을 사용해도 통과하는 문제이다. 시간복잡도 상 10,000 * 10,000 이라 빡빡하거나 안될 줄 알았는데 통과가 되는 것 같다. 스택의 자료구조를 사용하였다. 인덱스를 스택에 넣고, 해당 인덱스의 값이 스택의 top()보다 작으면 인덱스의 차로 계산을 하고, 현재 top의 계산이 끝나도 스택에 존재하는 모든 top과의 비교를 통해 주식의 하락세를 확인해야한다. 그리고 무조건 모든 인덱스는 스택에 한번씩은 들어가 다음 연산을 수행한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import java.util.*; class Solution { public int[] solution(int[] prices) ..

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 import java.util.*; class Solution { public int solution(int bridge_length, int weight, int[] truck_weights) { int answer = 0; int possibleWeight = weight; Queue q = new LinkedList(); for(int i=0;i= nowWeight && q.size()

문제를 이해하면 이렇다. 대기 목록에서 하나의 문서를 순서대로 빼어, 그 문서가 최고의 우선순위이면 그대로 프린트를 한다. 그 프린트의 위치가 일치하면 바로 끝. 그렇지 않으면 프린트하는 순서를 알아내기 위해 순서를 나타내는 변수를 올려준다. 만약 최고의 우선순위가 아닐 시 바로 뒤로 줄을 서야하고 그 외에는 변화할게 없다. for-each의 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 import java.util.*; class Solution { public int ..