탐욕(그리디) 알고리즘 greedy algorithm

안녕하세요 뚜디 입니다 :)

---

1. 탐욕법 이란? (그리디 알고리즘 이란?)

2. 그리디 알고리즘의 조건

---

1-1. 탐욕법 이란? (그리디 알고리즘 이란?)

1. 탐욕법(그리디 알고리즘)이란 현재 상황에서 가장 좋은 것(최선의 선택)을 고르는 알고리즘입니다.
2. 그리디 알고리즘은 동적 프로그래밍을 간단한 문제 해결에 사용하면 지나치게 많은 일을 한다는것을 착안하여 고안된 알고리즘입니다.

※ 동적 계획법

[C++] 동적 계획법 Dynamic Programming(DP) 사용법 (tistory.com)

[C++] 동적 계획법 Dynamic Programming(DP) 사용법

 

1-2. 현재 상황에서 가장 좋은 것(최선의 선택) 이란?

위 그림에 적힌 숫자는 최소한으로 도달할 수 있는 거리의 시간입니다. 우리는 가장 빠른 시간안에 1단계, 2단계, 3단계의 거리를 도달해야할때, 시간을 최소화 하려면 어떻게 해야할까요?

그리디 알고리즘은 단순히 현재 상황에서의 최선의 선택을 하는 알고리즘으로 그리디 알고리즘을 적용하면 10분, 20분, 15분이 선택되어 총 45분이 소요된다.

그렇지만 실제로 전체상황에서 문제를 보게되면 10분, 30분, 1분이 선택된 41분이 최소로 소요되는 시간이 된다.

이렇게만 본다면, 그리디 알고리즘은 크게 도움되지않는 알고리즘같은 느낌이 들지만, 그리디 알고리즘은 단순한만큼 실행 시간이 빠르다. 따라서, 그리다 알고리즘을 사용하는 문제는 간단한 문제일 가능성이 매우 크다.

 

2. 그리디 알고리즘 조건

그리디 알고리즘을 사용하기 위해 필요한 조건은 2가지가 있습니다.

[1. 탐욕스러운 선택 조건]
- 탐욕적인 선택은 항상 안전하다는 것이 보장되어야한다. 여기서 "안전하다"라는 것은 이 선택으로 인해 전체 문제의 최적해를 반드시 도출할 수 있어야 한다는 것

: 위에서는 그리디 알고리즘을 사용해 결과 도출 시 최적해가 무조건 나오지 않는다고 하지 않았나요??
 -> 그리디 알고리즘을 사용하면 무조건 최적해가 나오는 것은 아님, 하지만 그리디 알고리즘을 사용해 푸는 문제가 나왔을 경우 이 조건이 만족되는가를 생각해 충족되면 그리디 알고리즘을 사용
즉, 그리디 알고리즘을 사용하면 최적해가 나올 수 있는 문제여야함.

[2. 최적 부분 구조 조건]
- 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적의 해결 방법이다라는 조건
-> 전체 문제의 안에 여러 단계가 존재하고, 여러 단계 내의 하나 하나의 단계에 대해 최적해가 도출되어야 함.