[코드잇-알고리즘2 : 알고리즘 패러다임] 4. Greedy Algorithm

본 게시물은 코드잇의(codeit) 알고리즘 시리즈 강의 세번째 주제인 'Greedy Algorithm'을 듣고 정리한 게시물임을 알려드립니다.

- 강의 url : https://www.codeit.kr/topics/algorithmic-paradigms/lessons/1169

Memoization vs. Tabulation - 알고리즘 패러다임 | 코드잇

---

1.  Greedy Algorithm 소개

Greedy Algorithm이란?

- 미래를 내다보지 않고, 당장 눈 앞에 보이는 최적의 선택을 하는 방식. 목표를 달성하기 위해 매 순간마다 탐욕적인 선택을 하는 것.

Greedy Algorithm의 장단점

- 장점 : 간단하고 빠르다.
- 단점 : 최적의 답이 보장되지 않는다.

예를들어, 등산을 하는데 현재 우리의 위치는 A이다. 가장  높은 곳까지 올라가고 싶은데 그리디 알고리즘 방식으로 한다면 현재 지점에서 가장 좋아 보이는 방향으로 간다. A지점에서 당장은 왼쪽보다 오른쪽의 경사가 더 가파르기 때문에 오른쪽으로 가지만, 사실 제일 높은 곳은 B 방향임.

When to use?

1) 문제를 해결하는 다른 알고리즘들이 너무 느려서 사용할 수 없는 수준일 때 그나마의 대안으로 그리디 알고리즘 사용
2) 애초부터 완벽한 답까지는 바라지도 않고 그냥 적당한 답만 있어도 충분할 때가 있는데, 이런 경우에는 그냥 그리디 알고리즘을 사용하면 된다.

 

물론 제일 좋은 상황은 그리디 알고리즘을 이용해서 완벽한 답을 구하는 것. 

그리디 알고리즘이 최적의 답을 보장해 주는 문제들도 간혹 있는데, 이런 경우에는 그리디 알고리즘으로 효율적이면서도 정확한 솔루션을 얻어낼 수 있는 것 

2.  언제 Greedy Algorithm을 사용할까?

그리디 알고리즘이 최적의 답을 구해주는 문제들의 두 가지 조건

 

1) 최적부분구조(Optimal Substructure)

- 어떤 문제의 최적 부분 구조가 있다는 것은 부분 문제들의 최적의 답을 이용해서 기존 문제를 풀 수 있다는 것

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

- 각 단계에서의 탐욕스러운 선택이 최종 답을 구하기 위한 최적의 선택을 하는 것이라면 이 문제는 '탐욕적 선택 속성'을 갖고 있다는 것이다.

위 두 가지 조건을 둘 다 갖춘 문제라면 이 문제는 그리디 알고리즘을 사용해서 최적의 답을 구할 수 있음

예시) 동전을 최대한 적게 사용해서 돈을 거슬러주는 알고리즘 구현하기 : 1,700원 거슬러주기

그리디 알고리즘으로 풀면 최적의 답을 구할 수 있을지 조건 파악하기

1) 최적 부분 구조

- 처음에 500원을 줄 수도 있고, 100원을 줄 수도 있고, 10원을 줄 수도 있음. 만약 첫 동전으로 500원을 거슬러 준다면 1,200원이 남는다. 이제 동전을 최대한 적게 사용해서 1,200원을 거슬러주는 부분 문제를 풀어야 한다. 만약 첫 동전으로 100원을 거슬러 준다면 동전을 최대한 적게 사용해서 1,600원에 거슬러주는 부분 문제를 풀어야 한다.

- 이러한 식으로 위 네 가지 경우를 비교하면 기존 문제의 최적의 답을 구할 수 있음. 즉, 이 문제는 최적 부분 구조가 있는 것

 

2) 탐욕적 선택 속성

매 순간마다 최대한 큰 동전을 고를 수 있음. 예를 들어서 660원을 거슬러준다고 가정해본다. 처음에 선택할 수 있는 가장 큰 동전은 500원이다. 그럼 160원이 남는데, 이제 줄 수 있는 가장 큰 동전은 100원이다. 이런식으로 마지막 10원까지 거슬러줄 수가 있는데, 매 순간마다 가능한 큰 동전을 선택하는 게 가장 좋은 선택이라는 것을 증명할 수 있으면 이 문제에는 탐욕적 선택 속성이 있는 것.

 

(증명)

- 우선 500원짜리 하나는 100원짜리 다섯 개랑 똑같음. 100원짜리 다섯 개를 줄 바에야 500원짜리 하나를 주는 게 나음.

- 마찬가지로 100원짜리 하나는 50원짜리 두개랑 똑같은데 50원 짜리 두 개를 줄바에 100원짜리 하나를 주는 게 나음.

- 그리고 50원짜리 하나는 10원짜리 다섯 개랑 똑같은데 10원짜리 다섯 개를 줄바에 50원짜리 하나를 주는 게 나음.

- 그러니까 가능한 가장 큰 동전으로 거슬러주는 게 무조건 좋다고 확인할 수 있음. 그럼 이 문제는 탐욕적 선택 속성이 있는 것

- 결과적으로 이 문제는 최적 부분 구조와 탐욕적 선택 속성이 둘 다 있음. 따라서 이 문제를 그리디 알고리즘으로 풀면 최적의 답이 보장됨.

3.  Greedy Algorithm 개념 확인