그리디 탐욕 알고리즘: 이해하기 쉽게 풀어보는 기초 개념

자세한 내용은 영상으로 확인하세요! :)

오늘은 알고리즘 중 하나인 그리디 알고리즘에 대해 알아보는 시간을 가져보겠습니다. 그리디 알고리즘이란 무엇인지, 어떻게 하면 잘 풀 수 있는지, 그리고 초급 문제들까지 정리해 보겠습니다.

그리디 알고리즘의 정의

그리디 알고리즘은 이름 그대로 '탐욕'을 의미합니다. 이 알고리즘은 미래를 고려하지 않고 현재 시점에서 가장 좋은 선택을 하는 방식입니다. 즉, 현재 내가 내린 선택이 나중에 어떤 결과를 가져올지는 고려하지 않고, 무조건 지금 가장 저렴한 선택, 가장 빠른 선택 혹은 가장 가치 있는 선택을 내리는 것입니다. 그래서 그리디라는 이름이 붙여졌습니다.

예를 들어, 동전 교환 문제를 생각해 봅시다. n개의 동전과 전체 금액 k가 주어졌을 때, k를 만들기 위해 필요한 최소한의 동전 개수를 구하는 문제입니다. 여기서 핵심은 최소한의 동전 개수를 찾는 것입니다. 금액이 큰 동전부터 가능한 많이 사용하고, 남은 금액을 다음 큰 동전으로 채우는 방식으로 문제를 해결할 수 있습니다.

그리디 알고리즘의 특징

그리디 알고리즘은 항상 최적의 해를 보장하지는 않습니다. 예를 들어, 마시멜로 이야기를 떠올려 보세요. 지금 당장 마시멜로 하나를 먹는 것이 최선의 선택일 수 있지만, 10분 후에 두 개를 받을 수 있다면 기다리는 것이 더 나은 선택이 될 수 있습니다. 이처럼 그리디 알고리즘은 항상 최적의 해를 보장하지 않기 때문에 근사 알고리즘이라고도 불립니다.

그리디 알고리즘을 사용할 수 있는 첫 번째 조건은 현재의 선택이 미래의 선택에 영향을 주지 않는 경우입니다. 예를 들어, 서울에서 대전, 대전에서 부산으로 가는 최소 비용을 계산하는 문제에서, 서울에서 대전까지 가는 경로가 대전에서 부산까지의 경로에 영향을 미치지 않는다면 그리디 알고리즘을 사용할 수 있습니다.

두 번째 조건은 문제의 일부분에 대한 최적의 해가 전체 최적화를 이루는 경우입니다. 서울에서 부산까지의 최소 거리를 구하는 문제를 예로 들면, 서울에서 대전까지의 최소 거리와 대전에서 부산까지의 최소 거리를 더하면 전체 최적화가 됩니다.

그리디 알고리즘의 전략

그리디 알고리즘을 효과적으로 사용하기 위해서는 정렬이 핵심입니다. 예를 들어, 회의실 배정 문제를 생각해 봅시다. 여러 개의 회의 요청이 주어졌을 때, 겹치지 않게 최대한 많은 회의를 진행하려면 종료 시간을 기준으로 정렬하는 것이 좋습니다. 이렇게 하면 가장 빨리 끝나는 회의부터 진행하여 최대한 많은 회의를 진행할 수 있습니다.

그리디 알고리즘의 활용

그리디 알고리즘은 코딩 테스트에서 자주 사용됩니다. 그 이유는 속도 때문입니다. 다이나믹 프로그래밍보다 빠르기 때문에, 최적화가 보장되는 경우에 그리디 알고리즘을 사용하면 더 빠르게 문제를 해결할 수 있습니다. 현실 세계에서도 완벽한 정답이 아닌 근사치만 나와도 만족스러운 경우에 성능을 개선하기 위해 사용됩니다. 예를 들어, 내비게이션 시스템에서 최단 시간을 찾기보다는 적당한 해답을 빠르게 제공하는 것이 사용자 만족도를 높이는 방법입니다.

추천 문제

브론즈부터 골드까지 각 등급별로 5개의 문제를 추천해 드립니다. 직접 풀어본 문제들 중에서 선별한 것이니, 문제를 풀다가 이해가 잘 되지 않는 부분이 있으면 댓글로 남겨주세요. 정답과 간단한 풀이를 블로그를 통해 정리해 드리겠습니다.

오늘은 여기까지 그리디 알고리즘에 대해 알아보았습니다. 여러분의 코딩 공부에 도움이 되었기를 바랍니다. 그리디 알고리즘 공부, 화이팅 하세요!