greedy 탐욕법

greedy algorithm이란

현재 상황에서 가장 좋은 것을 고르는 알고리즘

 

탐욕법 사례

휴가전에 많은 일이 있다면 HOW?

1. 한가지 일을 잠시 하다가 다른 일을 한다.

    그 일을 잠시 하다가 또 다른 일을 한다. 

2. 일들을 쉬운 것부터 어려운 것으로 정렬

    쉬운 일부터 시작하여 순서대로 진행

3. 우선순위에 따라 정렬하여

    우선 순위 높은 일부터 수행한다.

 

탐욕법은 3번째 방식을 택하는 것이다.

 

greedy

가장 직관적, 지금 당장 가장 좋은 방법

많은 경우 최적해를 찾지 못한다.

 

greedy 알고리즘을 활용하는 경우

a. greedy를 사용해도 항상 최적해를 구할 수 있는 문제에 적용한다.

수행 시간이 다른 알고리즘에 비해 빠르다.

 

b. 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 너무 어려운 경우

최적해 대신 근사해로 대체

 

-greedy를 활용한 최단 경로를 찾는 방법

 

다익스트라 알고리즘

탐욕법 활용

음수 값을 가지지 않은 그래프에서 최단 경로 탐색

구글 웹사이트 지도서비스, 네비게이션, 네트워크 등

 

아직 방문하지 않은 정점들 중에서 가장 거리가 짧은 정점을 방문(탐욕법) -- 현재 상태에서 가장 좋은 선택

나머지 점들의 거리를 계산, 거리를 계산하여 갱신한다

 

녹색: 이미 갔던 곳

빨간색: 현재 위치

빨간색 부터 시작 --> 가장 짧은 곳으로 이동한다 -->  1번으로 이동

2로 다시 이동(가장 인접했던 곳중에 빨랐음) 

이제 5와 11로 이동 가능

5로 이동

이동할 때마다 최소 거리로 갱신한다,.

 

현재에서 가까운 곳으로 계속 이동하면서 주변의 값들을 갱신해나감