시작 하기전에 용어에 대해 적어보도록 하겠습니다.
▶노드, 정점 : A,B,C,D라고 적혀있는 부분을 노드 혹은 정점이라고 합니다.
▶간선 : 노드 끼리 연결하는 선을 간선이라고 합니다.
▶거리 : 위의 그림은 간선에 대한 가중치 혹은 값이 적혀있지 않는데, 이값이 적혀있다면 거리라고 합니다.
간선과 거리를 같이 사용할 때도 있습니다.
▶신장트리(spanning tree) :
★모든 노드를 포함하고,
★모든 노드가 서로 연결이 되어있고
★싸이클이 발생하지 않은 트리
위 사진은 모든 노드가 포함 및 연결이 되어있고 사이클이 발생하지 않았으므로 신장트리 입니다.
이와 같은 경우는 A, B, D에서 사이클을 형성했기 때문에 신장트리가 아닙니다.
대신에 간선을 하나 지움으로써 3가지의 신장트리를 만들 수 있습니다.
▶최소 신장 트리(minimum spanning tree) : 간선에 가중치가 부여되었을때, 가중치의 합이 최소인 트리를
최소 신장트리라고 합니다.
위 사진의 경우가 최소 신장 트리 입니다.(초록색 선으로만 연결을 한다면)
출처 : 프로그래머스 섬 연결하기
문제주소 : https://programmers.co.kr/learn/courses/30/lessons/42861
코딩테스트 연습 - 섬 연결하기 | 프로그래머스
4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4
programmers.co.kr
문제풀이 : https://mungto.tistory.com/47
섬 연결하기 C++(그리디,탐욕법)[프로그래머스]
※ 저의 풀이가 무조건적인 정답은 아닙니다. 다른 코드가 좀더 효율적이고 좋을 수 있습니다. 다른사람들의 풀이는 언제나 참고만 하시기 바랍니다. 문제 주소입니다. https://programmers.co.kr/learn/courses/3..
mungto.tistory.com
최소 신장 트리를 만족시키는 알고리즘은 크루스칼 알고리즘과 프림알고리즘이 대표적입니다.
▶크루스칼 알고리즘 : 노드에 연결된 거리가 최소인 간선을 고르게 되는데,
이때 선택한 간선이 신장트리의 조건을 만족하는지 체크를 하며 진행합니다.
모든 노드가 연결될때까지 위 사항을 반복합니다.
구현의 자세한 내용은 아래 블로그(나동빈님 블로그)에서 확인하시면 됩니다.
https://blog.naver.com/ndb796/221230994142
blog.naver.com
▶프림 알고리즘 : 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식
1. 임의 정점을 하나 선택해서 시작
2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택한다.
3. 모든정점이 선택될 때 까지 1,2 과정을 반복한다.
서로소인 2개의 집합을 유지한다.
1. MST를 만들기 위해 선택된 정점
2. 아직 선택하지 않은 정점
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
https://ko.wikipedia.org/wiki/%ED%94%84%EB%A6%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
프림 알고리즘 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 프림 알고리즘(Prim's algorithm)은 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소
ko.wikipedia.org
참고한 곳(사이트, 책)
쉽게 배우는 알고리즘
『쉽게 배우는 알고리즘』은 알고리즘을 가장 이해하기 쉬...
www.kyobobook.co.kr
'이론공부 > 알고리즘' 카테고리의 다른 글
| Hash 충돌 회피 방법은 무엇이 있을까? (2) | 2021.10.28 |
|---|---|
| BFS(Breadth First Search, 너비우선탐색) (0) | 2020.04.13 |
| 보이어-무어 알고리즘(문자열 검색, Python) (1) | 2020.02.19 |
댓글