본문 바로가기
728x90
반응형

MST3

[Programmers] 섬 연결하기 문제 탐욕법(Greedy) > 섬 연결하기 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 아이디어 이번 문제의 아이디어는 MST입니다. 소주제는 Greedy로 되어있지만 저는 MST에 더 적합한 문제라고 개인적으로 생각합니다. MST기법들인 프림이나 크루스칼 중 아무거나 사용해도 문제없이 풀 수 있을 것으로 보입니다. 저는 크루스칼을 이용하여 구현을 해봤습니다. 구현 코드 (JavaScript) class Node { constructor(a, b, val) { this.a = a; this.b = b; this.val = val; } } function solution(n, costs) { const n.. 2021. 4. 19.
[Algorithm] MST - 크루스칼 알고리즘(Kruskal Algorithm) 개요 ◎ 크루스칼 알고리즘이란? ◎ 그림 예시 ◎ 구현 코드 (Java) ◎ 시간 복잡도 ◎ 특징 안녕하세요. J4J입니다. 이번 포스팅은 크루스칼 알고리즘에 대해 적어보는 시간을 가져보려고 합니다. 크루스칼 알고리즘이란? 크루스칼 알고리즘은 대표적인 MST 구현 알고리즘 중 하나로 정점들 간의 연결된 길(간선)의 가중치를 작은 순서대로 선택하며 MST를 만드는 기법입니다. 예를 들어 A, B, C, D, E 정점이 있다고 가정해보겠습니다. A ↔ C 가중치: 3 A ↔ D 가중치: 5 B ↔ C 가중치: 4 B ↔ D 가중치: 4 C ↔ E 가중치: 2 D ↔ E 가중치: 1 일때 다음과 같은 순서로 가중치를 선택합니다. 1-1. 가중치가 1로 가장 작은 D ↔ E 간선을 임의로 선택합니다. 1-2. .. 2021. 1. 30.
[Algorithm] MST - 프림 알고리즘(Prim Algorithm) 개요 ◎ 프림 알고리즘이란? ◎ 그림 예시 ◎ 구현 코드 - 인접 행렬 (Java) ◎ 시간 복잡도 - 인접 행렬 ◎ 구현 코드 - 힙 (Java) ◎ 시간 복잡도 - 힙 ◎ 특징 안녕하세요. J4J입니다. 이번 포스팅은 프림 알고리즘에 대해 적어보는 시간을 가져보려고 합니다. 프림 알고리즘이란? 프림 알고리즘은 대표적인 MST 구현 알고리즘 중 하나로 정점을 기준으로 갈 수 있는 가중치가 가장 작은 길(간선)을 선택한 뒤 다음 정점을 방문하며 MST를 만드는 기법입니다. 예를 들어 A, B, C, D, E 정점이 있다고 가정해보겠습니다. A ↔ C 가중치: 3 A ↔ D 가중치: 5 B ↔ C 가중치: 4 B ↔ D 가중치: 4 C ↔ E 가중치: 2 D ↔ E 가중치: 1 이고 A 정점에서 출발한다면.. 2021. 1. 27.
728x90
반응형

티스토리툴바