# MST

17개의 포스트
post-thumbnail

[백준]#10021 Watering the Fields

문제Due to a lack of rain, Farmer John wants to build an irrigation system to send water between his N fields (1 <= N <= 2000).Each field i is des

약 19시간 전
·
0개의 댓글

자료구조

Array vs Linked List > #### Array > - 논리적 저장 순서와 물리적 저장 순서가 일치 > - 인덱스로 해당 원소에 접근할 수 있다. > - random access가 가능하다 > - 추가/삭제시, shift 연산이 필요 > #### Li

2020년 11월 13일
·
0개의 댓글
post-thumbnail

[백준]#4386 별자리 만들기

문제도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로

2020년 10월 23일
·
0개의 댓글
post-thumbnail

[백준]#1944 복제 로봇

문제세준이는 어느 날 획기적인 로봇을 한 개 개발하였다. 그 로봇은 복제 장치를 이용하면 자기 자신을 똑같은 로봇으로 원하는 개수만큼 복제시킬 수 있다. 세준이는 어느 날 이 로봇을 테스트하기 위하여 어떤 미로에 이 로봇을 풀어 놓았다. 이 로봇의 임무는 미로에 흩어진

2020년 10월 10일
·
0개의 댓글
post-thumbnail

[프로그래머스]#42861 섬 연결하기

문제n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다.

2020년 9월 15일
·
0개의 댓글
post-thumbnail

[백준]#6497 전력난

문제성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다.그러나 만약 어떤 두

2020년 8월 31일
·
0개의 댓글
post-thumbnail

[백준]#4650 Jungle Roads

문제The Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads between villages some years

2020년 8월 30일
·
0개의 댓글

[백준]#1647 도시 분할 계획

문제동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이

2020년 8월 27일
·
0개의 댓글

[백준]#1922 네트워크 연결

문제도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에

2020년 8월 27일
·
0개의 댓글

[백준]#1197 최소 스패닝 트리

문제그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.입력첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와

2020년 8월 26일
·
0개의 댓글
post-thumbnail

[SWEA]#1251 하나로

문제당신은 인도네시아 내의 N개의 섬들을 연결하는 교통시스템 설계 프로젝트인 ‘하나로’를 진행하게 되었습니다.하나로 프로젝트는 천해의 자연을 가진 인도네시아의 각 섬 간 교통이 원활하지 않아 관광 산업의 발전을 저해하는 요소를 줄이고 부가 가치를 창출하고자 진행하는 프

2020년 8월 26일
·
0개의 댓글
post-thumbnail

최소신장트리

조건 : 그래프 G는 connected graph이다.정의 : 그래프 G의 spanning tree는 다음 성질을 만족하는 G의 부분 그래프이다.G의 모든 정점들이 포함되어야 한다.connected 그래프이어야 한다.사이클을 포함하지 않아야 한다.신장트리는 다음 두 가

2020년 6월 7일
·
1개의 댓글

프로그래머스 - 지형 이동

https://programmers.co.kr/learn/courses/30/lessons/62050접근백준에 있는 삼성기출문제 '다리 만들기2'와 아주 유사한 문제입니다.BFS로 구역을 나누고각 구역을 연결하는 모든 다리를 구합니다.kruskal 알고리즘을

2020년 5월 22일
·
0개의 댓글

[프로그래머스] 섬 연결하기 (Java)

프로그래머스 섬 연결하기모든 간선의 비용이 주어지고 가장 적은 비용으로 모든 정점을 연결하는 문제는 MST의 개념 그 자체를 나타내는 문제다. 이 문제는 크루스칼 알고리즘을 이용하여 풀었다.주어진 모든 간선을 비용을 기준으로 오름차순 정렬한다.하나씩 간선을 꺼내어 싸이

2020년 4월 26일
·
0개의 댓글
post-thumbnail

최소 신장 트리 (MST, 크루스칼, 프림 알고리즘)

원래의 그래프의 모든 노드가 연결 되어있으면서 트리의 속성을 만족하는 그래프 조건본래의 그래프의 모든 노드를 포함모든 노드가 서로 연결 되어있다트리의 속성을 만족 (사이클이 존재하지 않는다)최소 비용 신장 트리를 찾는 알고리즘 가장 적은 비용으로 모든 노드를 연결하기

2020년 4월 18일
·
0개의 댓글

[BOJ 17472] 다리만들기2 (Java)

BOJ 17472 다리만들기2 문제풀이 다시 풀면 쉽게 풀릴줄 알았는데 생각보다 애먹었다. 그래프를 더 많이 공부해야겠다. 섬을 라벨링한다. 각 섬에서 다리를 연결할 수 있는 모든 경우를 리스트에 저장한다. Kruskal 알고리즘을 통해서 모든 섬을 연결하는 다리의

2020년 2월 6일
·
0개의 댓글
post-thumbnail

Algorithm - Arctic

문제 남극에는 n개의 탐사 기지가 있습니다. 남극의 겨울은 혹독하기 때문에, 겨울이 찾아오면 탐사 기지들 간의 왕래가 중단됩니다. 겨울에도 서로 통신하며 연구를 지속하기 위해, n개의 무전기를 구입해 각 탐사 기지에 배치해서 기지 간 연락망을 구축하려고 합니다. 모든 무전기의 통신 반경은 d이며, 두 탐사 기지는 사이의 거리가 d 이하여야만 서로 연락을 할...

2019년 10월 27일
·
0개의 댓글