[이코테] 3. 그리디 알고리즘이란?

그리디(Greedy) 알고리즘

그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미.

일반적인 그리디 알고리즘은, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함.
- 나중에 배우게될 크루스칼 알고리즘이나 다익스트라 알고리즘과 같이 잘 알려진 알고리즘을 제외하고,
  일반적으로 그리디 알고리즘이 출제가 되면
  해당 문제를 풀기위한 최소한의 아이디어를 적절히 떠올려야 풀 수 있게 출제됨
그리디 해법은 정당성 분석이 매우 중요.
- 주어진 상황에서 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토하는 과정이 필요.

[문제 상황]

맨 위 노드부터 시작해서 거쳐가는 노드의 합을 최대로 만들고자 함. 최적의 해는 무엇인가?

위 그림 처럼, 그리디 알고리즘은 해당 순간에 가장 좋아보이는 선택을 한다.

시작 노드에서 다음 노드로 갈 때, 7, 10, 8 중에 10이 가장 좋아보이므로 10을 선택한다.

그리고 4, 3중에 4가 가장 좋아보이므로 4를 선택한다. (총합 : 5 + 10 + 4 = 19)

하지만, 최적의 해는 아래 그림과 같다.

총합 : 5 + 7 + 9 = 21

실 생활에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많음.

프로그램 개발 시에 그리디 알고리즘은 최적의 해에 가까운 값을 얻거나 최적의 해를 보장할 때 사용함.

하지만, 코딩 테스트에서 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황이며,

이를 '추론' 할 수 있어야 풀리도록 출제됨.

아래 그리디 유형 대표 문제들은 각각 포스팅 하도록 하겠다.

시리즈 목차