그리디 알고리즘 개념 총 정리

🔸그리디 알고리즘

Greedy는 탐욕스럽다는 뜻으로 매 순간 최선의 선택을 수행함으로써 문제를 해결하는 방식입니다.

따라서 몇몇 예외를 제외하면 문제 유형이나 테크닉한 기술 없이도 풀 수 있는 문제입니다.

하지만, 문제를 접했을 때 해결할 수 있는 최소한의 아이디어는 떠올릴 수 있어야 해결이 가능하므로 문제풀이를 통해 감을 익힐 필요가 있는 유형이라고 볼 수 있습니다.

단, 다익스트라 알고리즘, 정렬 알고리즘과 함께 출제되는 경우 미리 숙지가 필요한 경우도 있습니다.

📌 정리

그리디 알고리즘을 해결하기 위해서는 다음 능력을 키울 필요가 있습니다.

• 매 번 최선의 선택만 수행해도 문제를 해결할 수 있는지를 파악해야 합니다.
• 문제를 해결하기 위한 최소한의 아이디어를 떠올릴 수 있어야 합니다.
• 명확한 문제 유형이 파악되지 않을 때, 그리디 알고리즘을 의심해보아야 합니다.

여기서 매 번 최선의 선택을 수행할 시, 어떤 기준이 최선인지를 세울 수 있어야 합니다.

따라서 정렬 알고리즘과 함께 출제되는 경향이 있습니다.

결국 문제 해결을 위한 꾸준한 노력이 필요한 유형이라고 생각됩니다.

반면 정렬, 최단 경로 문제는 해결을 위한 알고리즘을 미리 숙지하고 있어야 풀이가 가능합니다.

📌 거스름돈 예시

대표적인 그리디 알고리즘 예시인 거스름돈 예시입니다.

N원의 거스름돈을 돌려줄 때 500원, 100원, 50원, 10원 동전이 무수히 많을 때, 최소한의 동전 개수 조합을 구하는 문제에 해당합니다.

그리디 알고리즘이라 가정했을 시 문제를 접근하는 사고 방법은 다음과 같습니다.

1. 만약 가장 작은 동전(10원)으로만 거슬러주면 어떻게 될까?
2. 그 다음 큰 동전으로 거슬러주면?
3. → 가장 큰 동전으로 거슬러주어야 최소 동전 개수를 만족한다.

단, 3번의 결론을 내린 뒤 항상 최적의 해를 보장할 수 있는지를 검토한 후에야 정답을 맞출 수 있습니다.

왜냐하면 예외가 존재할 수 있기 때문입니다.

500원, 400원, 50원, 10원의 경우 500원이 400원의 배수가 아니므로 800원이 주어지면 최적의 해는 400원 x 2입니다.

이 글은 '이것이 코딩테스트다 - 나동빈 저'서적을 참고하여 정리하였습니다.