반응형 MST6 [백준/C++] 전력난 (No. 6497) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 모든 집에서 다른 집으로 이동하기 위해서는 길에 가로등이 켜져있어야 하며, 다른 집을 거쳐서 이동할 수 있다. 이때, 가로등을 최소로 켜두면 얼마만큼의 비용을 절약할 수 있는지 계산하는 문제다. 즉, 모든 집들이 연결되어 있을 경우의 최소 비용을 구해 총 비용에서 빼면 절약한 비용이 나오므로, MST 문제임을 알 수 있다. 제한 사항을 보면 m과 n이 200,000이므로 prim 알고리즘이나 크루스칼 알고리즘을 이용해 문제를 풀면 된다. 나는 모든 간선을 우선순위 큐에 넣어서 최소 비용을 구하는 방법으로 문제.. 2024. 6. 2. [백준/C++] 우주신과의 교감 (No.1774) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 풀었을 때, 단순히 크루스칼 알고리즘으로 풀었다. 외계신들 간의 거리만 계산해 priority_queue에 넣으면 매우 쉽게 풀 수 있기 때문이다. 문제는 크루스칼 알고리즘이나 heap을 이용한 prim알고리즘은 시간복잡도가 O(ElogV)인데, 이 문제에서 E=V^2이기 때문에 O(V^2)의 prim알고리즘을 사용하면 더 빨리 문제를 해결할 수 있다. O(V^2)의 prim알고리즘을 간단히 설명하면 정점은 {현재 방문한 노드}와 {아직 방문하지 않은 노드}의 두 집합으로 나눌 수 있다. 여기서, 현재.. 2024. 6. 1. [백준/C++] 다리 만들기 2 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 보면 섬의 개수도 적고 격자의 크기도 생각보다 작기 때문에 풀이 방법만 잘 생각하면 여유롭게 풀 수 있는 문제다. 먼저 섬과 다른 섬의 연결은 오직 직선으로 만들어진 다리로 연결되어야 하며, 이 때 다리의 길이는 2 이상이어야 한다. 위 조건에 맞게 섬끼리 연결되는 다리의 길이만 계산하면 Prim 알고리즘이나 크루스칼 알고리즘을 이용해 모든 섬이 연결되는데 드는 최소 비용계산할 수 있다. 그렇다면 어떻게 섬끼리 연결되는 다리의 길이를 계산할지 알아보자. 먼저 하나의 섬에는 같은 번호가 오도록 아래 그림과 같.. 2024. 5. 31. [백준/C++] 별자리 만들기 (No. 4386) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 이름만 다르지 사실 이전에 풀었던 최소 스패닝 트리 문제와 다를게 없다." data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 왜냐하면 모든 별을 잇는 최소 비용을 계산하는게 목적인 문제이므로, 각 별 들을 잇는 간선의 비용을 계산해 어떤 별들을 잇는 간선인지 저장하면 MST 문제가 된다. 두 점의 거리를 계산하는 방법은 (x1, y1), (x2, y2) 일 경우 두 점의 거리 s^2 = (x1-x2)^2 + (y1-y2)^2 를 이용해 계산하면 된다. 이제 두 점의 거리를 계산하.. 2024. 5. 30. [프로그래머스/C++] 지형 이동 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때 어떻게 풀지 고민했다. 처음에는 특정 사다리를 놓을 경우 최소값만 구하려고 했는데, 그렇게 풀면 최소값을 구하는 과정에서 A, B, C 지역이 전부 연결되어야하는데 B, C지역끼리만 연결되는 경우가 생기기 때문이였다. 그래서 BFS로 사다리가 없는 지역들을 구분하고, 구분된 지역에서 다른지역으로 갈 때 사다리를 최소로 놓도록 했다. 문제를 풀다보니 모든 지역을 잇기 위해 사다리를 놓는 비용의 합이 최소가 되어야 했기 때문에 이는 MST 문제와 같은 문제라는 것을 알았다. 그래서 가장 비용이 적게 드는 사다리를 놓은 다음에, 사다리를 놓아서 새롭게 갈 수 있는 지역이 생기면 그 지역에서 사.. 2024. 1. 18. [프로그래머스/C++] 섬 연결하기 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] 섬과 섬을 연결하는 다리를 건설해 모든 섬을 이을 때, 최소 비용을 구하는 문제다. 이전에 풀었던 최소 신장 트리 문제와 똑같은 문제다. [SWEA/Python] 5249 - 최소 신장 트리 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] 노드와 간선의 수가 주어지면 이 그래프로 부터 최소 신장트리를 만들고 최소신장트리를 구성하는 간선의 가중치를 모두 더하는 문제다. HTML 삽입 codingjj.tistory.com HTML 삽입 미리보기할 수 없는 소스 [풀이 요약] 섬위 범위가 100이기 때문에, 프림 알고리즘이나 크루스칼 알고리즘에서 사용하는 유니온, 우선순위 큐 등을 사용하지 않고 반복으로도 쉽게 풀릴 것이라 생각했다. [아이디어 정.. 2024. 1. 9. 이전 1 다음 반응형
