이것이 취업을 위한 코딩 테스트다를 참고하여 작성하였습니다.

1️⃣ 그리디 알고리즘이란?

그리디 알고리즘은 탐욕 알고리즘이라고도 불리는 알고리즘으로, 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

그리디 알고리즘은 기준에 따라 가장 좋은 것을 선택하는 알고리즘이므로 문제에서 가장 큰 순서대로, 가장 작은 순서대로 와 같은 기준을 알게 모르게 제시해준다.

2️⃣ 그리디 알고리즘 문제를 해결하는 방법

대부분의 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

1. 현재 상태에서의 최적의 해답을 선택한다.
2. 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 1번으로 돌아가 위 과정을 반복한다.

3️⃣ 그리디 알고리즘을 적용하기 위한 조건

그리디 알고리즘이 잘 작동하기 위해서는 아래와 같은 두 조건이 성립하여야 한다.

1. 앞의 선택이 이후의 선택에 영향을 주지 않는다.
2. 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.