이지코딩

가장 간단한 브루트포스 문제. import kotlin.math.max fun main(){ val (n, m) = readln().split(" ").map { it.toInt() } val arr = readln().split(" ").map { it.toInt() } val sol: Solver = Solver() println(sol.solver(n, m, arr)) } class Solver{ fun solver(n: Int, m: Int, arr: List): Int{ var result = 0 for(i in 0 until n){ for(j in i+1 until n){ for(k in j+1 until n){ val sum = arr[i] + arr[j] + arr[k] if(sum

간선의 cost 합을 최소화 하고, 각 집 사이에 경로가 항상 존재해야 한다는 조건이므로 MST를 사용하는 문제이다. https://00rigin.tistory.com/59 MST (Minimum Spanning Tree) 최소 신장 트리 MST 즉 최소신장트리 (최소 스패닝 트리)는 간선에 weight가 있는 그래프를 tree로 만들어 문제를 해결할때 유용하게 사용할 수 있다. 그래프를 최소 비용 간선을 가진 tree로 만드는 방법을 MST 라고 00rigin.tistory.com 단, 조건은 마을을 2개로 만들면서, 도로의 유지비를 최소화 해야하는 것이다. 따라서, MST로 마을을 재구성 한 후에, 가장 도로 유지비가 비싼 집 하나를 정하고, 그 집을 2번째 마을로 설정한다. 이렇게 할 경우, 두개의..

그래프로 표현했을 때 간선이 음수의 값을 가지고, 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..

평범함 다익스트라 문제와 다르게 두 정점을 반드시 통과해야 하고, 양방향 그래프인 조건을 모두 충족해야 한다. 단방향 그래프를 표현할 때에는 (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 ..

합이 최소가 되는 순서는 가장 작은 것 끼리 더하는 방법이다. 따라서 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에 위치하도록 항..

최단 거리를 구하는 문제는 높은 확률로 BFS를 사용하면 된다. 위 그래프에서 1번 도시가 시작점이라고 가정하면, 0계층은 도시1, 1계층은 도시 2,3, 2계층은 도시 4인 트리로 볼 수 있다. 최단거리가 지정되어있으므로, 우리는 K-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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 #incl..

괄호 문제를 풀었다면 바로 스택을 사용하는 문제라는걸 알 수 있다. 어떤 것을 감싸고 있는 집합을 찾아야 하는 경우 스택이 가장 유용하다. 이 문제도 A쌍이 (), B 쌍이 [] 라고 생각하면 편하다. 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 #include #include #include #include #include #include #include #include using namespace std; int main(){ int T; int ans = 0; cin>>T; for(int t = 0; t>tem; s.push(..