막내의 막무가내 프로그래밍 & 일상

www.acmicpc.net/step/15 최소 신장 트리 단계 신장 트리가 중요한 이유는, 가장 적은 개수의 간선으로 모든 정점을 연결할 수 있기 때문입니다. 이 문제를 통해 확인해 봅시다. www.acmicpc.net 백준 최소신장트리 단계별풀기의 4번째 문제입니다. ㅎㅎ 이전 단계문제들과 거의 비슷합니다. N개의 나의 위치와 우주신들의 좌표가 주어집니다. 그다음 M개의 이어진 좌표들이 주어 집니다. 이 이후에 최소비용으로 모두 연결해서 가장 낮은 비용으로 나와 우주신들이 모두 건너건너 최소신장트리로 연결되게 하면 끝입니다. 기존의 크루스칼 알고리즘을 사용하면 풀립니다. 추가로 Math.round() 를 사용하면 4.00일 경우 0이 잘려서 4.0으로 출력이 되서 이럴때는 String.foramt()..

www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 백준 최소신장트리 단계별 풀기 3번째 문제입니다. 이전 단계 문제와 마찬가지로 크루스칼 알고리즘과 유니온-파인드를 사용합니다. 입력값하고 가중치 넣는 방식만 변형된 문제였습니다. [Java] import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; class Main { private static int[] parent;..

www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 백준 최소신장트리 단계별풀기의 두번째 문제입니다. ㅎㅎ 최소신장트리는 크르수칼 알고리즘을 사용하는 문제입니다. 노드개수를 V, 변의 개수를 E라고 하면 O(ElogV)의 시간복잡도를 가집니다. 저는 풀기전 영상을 통해 개념을 먼저 복습하고 봤습니다. www.youtube.com/watch?v=LQ3JHknGy8c 풀이방법은 다음과 같습니다. 1. 노드의 연결요소들을..

www.ssg.com/item/itemView.ssg?itemId=1000020135611&ckwhere=ssg_gshopsa&EKAMS=google.723.6063.23030.2065157.619259233&trackingDays=1&gclid=CjwKCAiAq8f-BRBtEiwAGr3DgfwfmqqXixtiiD-Sq5V7Qbwar-RbeVqkn0f7ZMDNAMxL0e2RnxE_9hoCPrYQAvD_BwE 백포스쳐 넥헬퍼 바른목 바른자세 목해먹 여기를 눌러 링크를 확인하세요. www.ssg.com (2주 사용후기) 나이가 들고 노트북하는 일이 많아서 그런지 목이 뻐근해지기 시작했습니다 ㅠ 주변 친구들도 몇명은 벌써 거북목 판정을 받아 도수치료만 1회에 12만원 10회 한다고 하는데 저도 그렇게 거북목 ..