그리드 알고리즘 (Greedy Algorithm)

1. 그리드 알고리즘이란?

매 순간 "가장 좋아 보이는 선택", 즉 "최적의 선택"을 하는 방식의 알고리즘이다.

각 단계에서 가장 최적이라고 생각되는 선택을 하는 전략이며,

 

"이때 중요한 점은 현재의 선택이 전체 결과에도 최적이 된다고 가정하는 것이다. "

 

전체를 고려하기보다,

매 순간의 최선의 선택을 통해 결과를 만들어낸다.

 

---

 

2. 특징

1.  현재 선택 중심 

• 미래의 상황을 고려하지 않는다.
• 지금 가장 좋은 선택에 집중한다.

2.  빠른 수행 속도

• 복잡한 탐색 없이 진행되기 때문에, 일반적으로는 시간 복잡도가 낮다.

3.  단순한 구조

• 구현이 직관적이고 간단한 경우가 많아.

 

---

 

3. 전제조건

단순히 모든 문제에서 사용할 수 있는 방법은 아니며,

아래의 두 가지 조건을 만족해야 한다.

• 탐욕적 선택 속성 ( Greedy Choice Property)
• 최적 부분 구조 (Optimal Substructure)

 

아래의 예시를 살펴보자.

 

1.  탐욕적 선택 속성 ( Greedy Choice Property)

현재의 선택이 이후의 선택에 영향을 주지 않아야 한다.

예시) 거스름돈 문제

 

동전 종류 : 500원, 100원, 50원, 10원

거스름 돈: 800원

 

500원을 먼저 선택해도 이후 100원, 50원, 10원 선택에는 영향이 없다.

가장 큰 동전을 먼저 선택해도 최적의 해가 깨지지 않는다.

이로 인하여 큰 것부터 선택이라는 전략이 항상 유지된다.

 

------------------------------------------------------------------------------------------

(반례)

동전 종류 : 500원, 400원, 100원

거스름돈 : 800원

 

500원을 먼저 선택할 경우 500 + 100 + 100 + 100 = 총 4개의 동전을 거슬러줘야 한다.

하지만 최적의 해는 400 + 400 = 2개의 동전을 거슬러 주는 것이다.

처음 선택이 이후 결과에 영향을 주게 된다.

 

2. 최적 부분 구조 (Optimal Substructure)

부분 문제의 최적해가 전체 문제의 최적해로 이어져야 한다.

예) 거스름돈 문제

 

동전 종류 : 500원, 100원, 50원, 10원

거스름 돈 : 1260원

 

이 문제에서 큰 것부터 해결하게 되면 500원 2개를 사용해서 1000원을 만들고

남은 260원의 문제만 최적으로 잘 해결하게 된다면 전체도 최적이 된다.

즉 큰 문제는 작은 문제들의 최적 해 조합이다.

 

------------------------------------------------------------------------------------------

 

(반례)

동전 종류 : 500원 , 400원, 100원

금액 : 800원

 

이 문제에서 큰 것부터 해결했을 때 500원을 활용하면 남은 300원을 해결해야 한다.

300원의 최적의 해는 3일 것이다. 

즉 부분 문제인 300원의 최적의 해를 해결 한다고 해서 전체의 최적해로 이어지지 못한다는 것을 알 수 있다.

 

---

4. 한계

그리디 알고리즘은 빠르고 효율적이지만, 항상 정답을 보장하지 않는다.

그러한 이유는 다음과 같다

• 현재의 최선이 전체의 최선이 아닐 수 있다.
• 한 번 선택하면 되돌릴 수 없다.
• 전체 최적을 고려하지 않는다.

즉 문제의 구조를 잘 분석하지 않는다면 잘못된 접근이 될 수 있다.

 

 

---

 

 

5. 언제 사용해야할까?

그리디 알고리즘은 일반적으로 아래의 상황에서 사용된다.

 

1.  선택의 기준이 명확할 때

어떤 선택이 더 좋은 선택인지 기준이 분명 해야한다.

매 순간 이걸 선택하면 된다는 확실한 기준이 있어야 한다

거스름돈 문제에서는 최소 동전 개수를 사용하는 것을 위해서라면 가장 큰 동전 부터 먼저 사용하는 것이 유리할 것이다.

즉 여기에서의 명확한 기준은 큰 것에서부터 선택이라는 기준이 명확히 존재한다.

 

2.  정렬 후 규칙적으로 선택 할 수 있을 때

데이터를 정렬하게 되면 일정한 규칙으로 선택이 가능해야 한다.

회의실 배정 문제를 예시로 보면, 회의가 가장 빨리 끝나는 시간 기준으로 정렬해서, 가장 빨리 끝나는 회의부터 선택한다.

이후부터는 겹치지 않는 회의를 계속 선택하면 된다.

 

3.  각 단계의 선택이 독립적일 때

각 선택이 서로 영향을 주지 않아야 한다.

 

---

 

6. 정리

그리디 알고리즘은 복잡한 문제를 단순한 선택의 반복으로 해결하는 방법이다.

빠르고 구현이 쉽다는 장점은 있지만, 항상 정답을 보장하지는 않기 때문에, 문제의 성질을 정확히 파악하는 것이 중요하다.

 

7. 한 줄 요약

->>> "그리디 알고리즘은 매 순간 최선 선택을 통해 문제를 해결하는 전력"