본문 바로가기

greedy3

[알고리즘] 9-7 원더랜드 - 프림 알고리즘, 최소 신장 트리, Greedy (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 복습할 때 개인적으로 참고하기위해 풀이 코드를 정리하고 있습니다. 문제 링크 : https://cote.inflearn.com/contest/10/problem/09-07 프림 알고리즘(Prim Algorithm) 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법 동작 과정 시작 정점을 최소 신장 트리 집합에 포함한다. 집합에 포함된 정점과 연결된 정점들 중에 최소 비용으로 연결된 정점을 선택하여 연결하여 집합을 확장한다. (단, 회로를 형성하는 이미 집합에 포함된 정점끼리 연결하는 것은 제외) 2번 과정을 최소 신장 트리가 완성될 때까지 반복한다. 신장 트리 : 그래프의 모든 정점이 연결되어있고, 회로가.. 2021. 6. 30.
[알고리즘] 9-7 원더랜드 - 크루스칼 알고리즘, 최소 신장 트리, Greedy (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 복습할 때 개인적으로 참고하기위해 풀이 코드를 정리하고 있습니다. 문제 링크 : https://cote.inflearn.com/contest/10/problem/09-07 크루스칼 알고리즘(Kruskal Algorithm) 최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 알고리즘 Greedy를 이용하여 가중치 그래프의 모든 정점을 최소 비용을 연결하는 방법을 찾는 것 최소 신장 트리 : 가중치 그래프에서 간선의 가중치 값의 합이 최소가 되고, 회로가 없이 모든 정점이 연결되어있는 트리를 뽑아내는 것 신장 트리 : 그래프의 모든 정점이 연결되어있고, 회로가 없는 그래프 동작 과정 그래프의 간선들을 가중치.. 2021. 6. 30.
[알고리즘] 9-3 결혼식 - Greedy (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 복습할 때 개인적으로 참고하기위해 풀이 코드를 정리하고 있습니다. 문제 링크 : https://cote.inflearn.com/contest/10/problem/09-03 풀이 친구들 5명의 (도착시간, 떠나는시간)이 다음과 같을 때, (14, 18), (12 ,15), (15, 20), (20, 30), (5, 14) 시간의 흐름을 그림으로 나타내면 다음과 같다. class Time implements Comparable{ int time; char status;//S: 도착시간, E: 떠나는 시간 public Time(int time, char status) { this.time = time; this.status = st.. 2021. 6. 26.

티스토리툴바