[Java] 그리디 알고리즘 (Greedy Algorithm) , 탐욕 알고리즘

그리디 알고리즘

Greedy(탐욕) 알고리즘은 매 번의 선택에서 가장 좋아보이는 선택을 하여 적절한 답을 찾아간다

예를 들어

 

다음과 같이 서울에서 부산을 가는 경로가 있다고 해보자.

서울-대전을 가는 경로중 가장 빠른 경로인 80분 걸리는 경로를 선택하고

대전-부산을 가는 경로중 가장 빠른 150분 걸리는 경로를 선택하여

총 230분이 걸리는 경로가 가장 빠른 경로일것이다.

이렇게 각 단계별로 최선의 선택지를 선택하는것이 그리디 알고리즘이다.

 

하지만 그리디 알고리즘은 항상 최적의 해를 도출해내는것이 아니다.

조건이 필요하다.

 

아래의 예시를 보자.

똑같이 부산을 목표로 가장 짧은 소요시간을 구해보자.

서울에서 원주로 가는 경로가 생긴 예시이다.

 

서울-대전 , 서울-원주를 보니 가장 적은 소요시간인 80분을 선택하고

다시 대전-부산에서 150분을 선택한 총 소요시간 230분은

 

서울-원주 (130분) 원주-부산(90)분 => 총 소요시간 220분 보다 더 빠르게 도착한다.

 

이런식으로 그리디 알고리즘은 '최적해에 근사하는 방법'인 것일뿐 항상 최적해를 만족하는것이 아니다.

최적해를 만족하려면 여러 조건이 필요하다.

1) 이전의 탐욕 선택이 이후의 선택에 영향을 주지않아야한다. (각 선택이 독립적이여서 다른 선택에 영향을 주면 안됨)

2) 전체 최적해가 부분 문제에 대해서도 최적해를 만족한다는것 

 

 

첫번째 사진 예시에서

1,2 만족

서울-대전 ,  대전-부산은 각각 독립적이기 때문에 서울-대전에서 어떤 경로를 골랐냐에 따라 

대전-부산에서 경로 선택에 영향이 없다. 그냥 각각 제일 소요시간이 적은것을 선택하면 됬기때문이다.

 

두번째 사진 예시에서

첫번째 사진예시에서는 서울-대전 어떤것을 골라도 , 대전-부산 경로를 선택할 기회가 주어졌다.

하지만 두번째 사진예시에서는 서울-대전 또는 서울-원주를 선택하게 되는데 

대전을 선택하게되면 대전-부산 경로에서 선택할 수 있고, 서울-원주를 선택하게 되면 원주-부산만 선택할 수 있게 된다.

즉 첫번째 선택이 두번째 선택에 대한 영향을 주기 때문에 , 첫번째선택과 두번째선택은 독립적이 아니라 서로 연관이 있게 된다는것이다. -> 독립적이지않아 그리디 알고리즘을 사용해서 최적해를 구할 수 없다.

 

그리디 알고리즘은

동적계획법과 달리 최적해를 100% 보장해주지못하지만 각 순간별 최적 선택을 하기 때문에 근사해를 구하는 속도가 매우 빠르다는점이 장점이다.

 

 

 

 

 

출처,참고,더 자세한정보

https://st-lab.tistory.com/143