YJ_Scribbles

★ 크러스컬(Kruskal) 알고리즘 - 가중치가 가장 작은 선분이 사이클을 만들지 않을 때에만 ‘욕심내어’ 그 선분을 추가시킨다. - 가장 작은 엣지부터 사이클이 생기지 않도록 추가해나간다 ㅇ 알고리즘 ★ 프림 (Prim) 알고리즘 - 임의의 점 하나를 선택한 후, (n-1)개의 선분을 하나씩 추가시켜 트리를 만든다. ㅇ수행과정 1) a에서 시작 2) a와 연결된 에지 중 가장 작은 값을 갖는 a-d를 선택 3) Dist[] 배열을 업데이트 4) 다음 작은 값인 a-b를 선택 5) Dist[] 배열을 업데이트(a, b, d가 선택됨) 6) 과정을 버텍스 갯수만큼 반복 -> 선택된 버텍스는 다시 선택되지 않으므로 사이클이 생기지 않는다 ㅇ 알고리즘 ★ 프림 (Prim) 알고리즘 코딩하기 1. "콘솔앱(C..

★ 그리디 알고리즘 - 최적화 문제를 해결하는 알고리즘 - 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불림 ㅇ 최적화 (optimization) 문제 - 가능한 해들 중에서 가장 좋은 (최대 또는 최소) 해를 찾는 문제 ㅇ 특징 - 데이터 간의 관계를 고려하지 않고 수행 과정에서 ‘욕심내어’ 최소값 또는 최대값을 가진 데이터를 선택 (‘근시안적’인 선택) - 일단 한 번 선택하면, 이를 절대로 번복하지 않음 -> 매우 단순하며, 또한 제한적인 문제들만 해결 가능 ★ 예시1. 동전 거스름돈 문제 - 남은 액수를 초과하지 않는 조건하에 ‘욕심내어’ 가장 큰 액면의 동전을 취하는 것 ㅇ 알고리즘 -> CoinChange 알고리즘은 항상 최적의 답을 주지 못함 (따라서 실제로는 거스름돈에 대한 그리디 ..