그리디(Greedy) 알고리즘

covenant.tistory.com/131

그리디 알고리즘(Greedy Algorithm) 및 백준 문제 추천

위 포스팅을 보고 개념정리 함.

 

 

간단히 말해 알고리즘 이름 그대로 탐욕적으로 현재의 상황에서 최적의 경우를 찾는 것이다.

예를 들어  A, B, C, D, E가 있다고 치고 각각을 잇는 다리의 길이가 존재한다고 할때,

 A에서 E로 가는 최적의 경로를 그리디 알고리즘으로 구하게 되면..

 

1. A와 연결된 지점중 가장 짧은 거리의 지점을 찾아간다. 만약 그게 C라면..
2. C와 연결된 지점중 가장 짧은 거리의 지점을 찾아간다. 만약 그게 D라면..
3. D와 연결된 지점중 가장 짧으 거리의 지점을 찾아간다. 만약 그게 B라면...

                        (반복)

 

따라서, 항상 최적의 해를 주는 것은 아니다.

 

 

 

위 포스팅에서 받은 백준 문제 추천이다. 이걸 풀어보도록 하자...