알고리즘
-
[알고리즘] 최소 신장 트리 개념P.study 2020. 6. 17. 03:08
책을 보면서 그리디 알고리즘으로 최적해가 보장되는 예로 최소 신장 트리가 있었다! 당연히 기억 안나니까 한번 공부해 볼까?!! 최소 신장 트리 " 간선들이 가중치를 갖는 그래프에서 가중치의 합이 가장 작은 트리를 말한다. " 최소 신장 트리를 찾는 알고리즘을 공부해보려 한다. 1. 프림 알고리즘 : 시작점을 기준으로 모든 정점을 포함할 때까지 인접한 정점에서 가중치가 가장 작은 간선을 선택하여 하나씩 확장해 나간다. [순서] 1. Start 에서 바라보면 8,9,11 중에서 가장 가중치가 낮은 간선을 택한다. 2. 연결되어 있는 간선들 중에 가중치가 가장 낮은 9를 선택한다. 3. 연결된 간선(1,10,11,12,13) 중 가장 낮은 5를 선택한다. 4. 연결된 간선(11,12,13) 중 가장 낮은 11..
-
[알고리즘] 그리디 알고리즘 개념 & C언어.ATM(11399번)P.study 2020. 6. 10. 23:53
분명 나는 알고리즘을 배웠는데... 왜 다 까먹은 것일까... 그리디 알고리즘.. 뭔가 이름만 들어도 욕심쟁이같은 느낌이 든다 !! 그리디 알고리즘 (Greedy Algorithm) 눈앞의 이익만 우선 추구하는 알고리즘 (Greedy = 탐욕스러운) [개념] 최적해를 구할때 눈 앞에 가장 좋아 보이는 선택을 반복하여 최적해를 찾는 알고리즘. 최적해를 보장하진 않음. (그 상황에서 좋아 보이는 선택을 하기 때문에 대부분 뛰어난 결과를 도출하지 못함.) 극단적으로 문제에 접근함. (무조건 숫자가 높은순으로, 무조건 숫자가 낮은 순으로, 무조건 짧은 순으로 등등..) [예시] Q. 동전 660원의 동전 갯수는? 조건 : 무조건 금액이 높은 동전 순서대로 >>>> 극단적인 조건 500원 > 1개 100원 > 1..