이지코딩

그래프로 표현했을 때 간선이 음수의 값을 가지고, cycle을 찾아내야 하므로 벨만-포드 알고리즘을 사용해야 한다. https://00rigin.tistory.com/57 벨만포드 알고리즘 다익스트라 알고리즘은 O(NlongN) 안에 한 노드에서 다른 모든 노드에 대한 최단 거리를 찾을 수 있다. 벨만-포드 알고리즘의 경우 O(N^2)으로 최단 거리를 찾는다. 벨만-포드 알고리즘이 존재하는 00rigin.tistory.com 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..

다익스트라 알고리즘은 O(NlongN) 안에 한 노드에서 다른 모든 노드에 대한 최단 거리를 찾을 수 있다. 벨만-포드 알고리즘의 경우 O(N^2)으로 최단 거리를 찾는다. 벨만-포드 알고리즘이 존재하는 이유는 "음수"값을 가지는 간선이 존재할때 최단 거리를 찾기 위함이다. 음수 간선이 존재할 경우 circuit이 생길 수도 있는데, circuit을 돌 수록 음수 간선에 의해 최단 거리가 계속 줄어들 수도 있다. 하지만, 상식적으로 생각해 본다면, 같은 길을 반복해서 지나가는건 최단 거리가 아니다. 벨만-포드는 이 두가지 경우를 상정할 때 최단 거리를 구할 수 있는 알고리즘이다. 벨만-포드의 특징은 - 음수간선이 존재 - Cycle을 돌면 안됨 -> cycle을 돌 경우 탐색 중지 라고 할 수 있다. 다..

평범함 다익스트라 문제와 다르게 두 정점을 반드시 통과해야 하고, 양방향 그래프인 조건을 모두 충족해야 한다. 단방향 그래프를 표현할 때에는 (start, end, cost)를 v[start]({end, cost})에만 추가하면 되지만, 양방향 그래프를 표현해야 하므로 v[end]({start,cost}) 또한 추가해주어야 한다. 다음은 두 정점을 반드시 통과해야 하는 조건이다. 반드시 통과해야 하는 두 정점을 p1, p2라고 할 경우 1. p1-p2 사이의 최단 거리 2. min( (start-p1 최단 거리)+(end-p2 최단 거리) , (start-p2 최단 거리)+(end-p1 최단 거리)) 를 구한 후 더해주면 된다. start-p1-p2-p1-end 로 가는 방식이 최단 거리일 수도 있지만,..

다익스트라 알고리즘을 사용하는 문제이다. 이상하게도... 빠른 입출력을 사용하지 않으면 런타임 에러가 뜬다...ㅠ 다익스트라 알고리즘은 아래 글을 보면 된다. https://00rigin.tistory.com/54 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘은 최단거리 (shortest path) 탐색 알고리즘의 일종으로, DP에 기반한 알고리즘이다. 한 node에서 다른 모든 node 까지의 최단거리를 탐색할 수 있다. 각 노드간 간선이 존재하고, 00rigin.tistory.com 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 ..

다익스트라 알고리즘은 최단거리 (shortest path) 탐색 알고리즘의 일종으로, DP에 기반한 알고리즘이다. 한 node에서 다른 모든 node 까지의 최단거리를 탐색할 수 있다. 각 노드간 간선이 존재하고, 각 간선의 거리가 주어질 때 최단 거리를 구할 수 있다. 다음과 같은 그래프가 있다고 가정한다. Node 1에서 각 노드까지의 거리를 표로 정리하면 다음과 같다. 노드 1 2 3 4 5 6 거리 0 2 5 1 INF INF 노드 1에서 5,6까지는 바로 갈 수 없으므로 무한으로 가정한다. 이때 1에서 가장 가까운 노드는 4이다. 따라서 node 4를 거칠 경우 1에 대한 최단 거리를 먼저 구한다. 4를 거쳐 갈 수 있는 노드는 3,5 인데, 1-4-3으로 3까지 갈 경우 거리는 1+3 = 4이..

문제를 이해한 후 input/ output을 보면 먼저 짝수일 경우에만 답이 존재한 다는 것을 알 수 있다. 또한 gcd 이므로 일정한 규칙에 영향을 받아 갯수가 정해질텐데.... 라는 생각으로 정답을 소인수 분해 해보면 규칙을 찾을 수 있다. input이 2 일 경우 정답 : 1^2 input이 4 일 경우 정답 : 1^2 * 2^2 input이 6일경우 정답 : 1^2 * 2^2 * 3^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 ..

참... 문제가... 이해하기 어려워서 한참 걸렸다... 010 이 있으면, "01","10"은 남여 수가 같으므로 패스, "010"은 남자가 적으므로 문제에 위반 된다. 이 경우 0110으로 만들어주어야 한다. 처음엔 브루트 포스를 써야 하나 했지만 그럴 경우 무조건 runtime에 잡힌다. 따라서 규칙을 좀 찾아보면, 1. 00 이 나올 경우 사이에 11을 넣어주어야 한다. 2. 010 이 나올 경우 사이에 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 27 28 29 30 31 32 33 34 35 36 37 38 39 ..

합이 최소가 되는 순서는 가장 작은 것 끼리 더하는 방법이다. 따라서 40, 30, 30, 50이 있다면, 가장 작은 30과 30을 먼저 더해야 한다. 이 이후에 가장 작은 것 끼리 더하는 것을 반복하면 되기 때문에 30+30을 다시 배열에 넣고 작은 것 끼리 더하는 것을 반복하면 된다. 즉 40, 30, 30, 50 -> 30+30 = 60 40, 60, 50 -> 40 + 50 = 90 60, 90 -> 60+90 = 150 이고, 따라서 정답은 60 + 90 + 150 = 300 이다. 한 배열에서 가장 작은 값을 정렬을 따로 하지 않고 추출할 수 있는 방법중 가장 쉬운 것은 우선순위 큐를 사용하는 것이다. 우선순위 큐를 사용할 경우 내부적으로 힙을 사용하여 max 값이 가장 top에 위치하도록 항..