🏖️ jcowwk's develop

그리디 알고리즘 - 크루스칼, 프림(최소 신장 트리)그리디 알고리즘의 최소 신장 트리 알고리즘인 크루스칼과 프림 알고리즘에 대해서 공부한 내용 정리 입니다 ! 1. 최소 신장 트리2. 크루스칼 알고리즘3. 프림 알고리즘1. 최소 신장 트리그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분의 가중치 합이 최소인 트리하나의 그래프에서 여러 개의 트리가 나올 수 있다. 2. 크루스칼 알고리즘가중치가 가장 작은 선분이 사이클을 만들지 않을 때만 욕심내어 그 선분을 추가시킨다.n개의 트리들이 점차 합쳐져서 1개의 신장 트리가 된다.  위의 그래프에 크루스칼 알고리즘을 적용해보겠다. 먼저, 선분의 가중치가 작은 순서대로 정렬한다.다음으로 가장 첫 번째 선분을 고른 후, 사이클을 형성하는지 체크하고 추가시..

그리디 알고리즘 - 동전 거스름돈 문제 그리디 알고리즘의 동전 거스름돈 문제에 대해서 공부한 내용 정리 입니다 ! 1. 그리디 알고리즘 2. 동전 거스름돈 문제 1. 그리디 알고리즘 가능한 해들 중에서 가장 좋은 해를 찾는 문제에 사용한다. 부분적인 최적 해를 찾고, 이들을 모아서 문제의 최적 해를 구한다. 한 번의 결정이 이후의 결정에 영향을 주지 않는 경우에 최적이다. 2. 동전 거스름돈 문제 거스름돈 760원이 있을 때, 우리는 500원 동전 1개, 100원 동전 2개, 50원 동전 1개, 10원 동전 1개까지 총 5개의 동전이 필요하다. 동전 거스름돈 문제는 이처럼 거스름돈 액수에 대한 최소 동전의 수를 구하는 문제이다. public static void main(String[] args) { i..