[AlgorithmTheory] 탐욕(Greedy) 알고리즘

본 포스트는 저의 재학습을 위해 작성한 포스트로 이번엔 탐욕(Greedy) 알고리즘이란 무엇이며, 코딩 테스트에서는 어떤 유형으로 문제가 출제되는지 한 번 정리해 보도록 하겠습니다.

1. 탐욕(Greedy) 알고리즘의 본질

탐욕 알고리즘이란?

탐욕(Greedy) 알고리즘은 이름에서 알 수 있듯이, 어떤한 문제가 주어졌을 때 “현재 상황에서 당장 눈앞에 보이는 가장 최선의 선택”만을 쫓아 해답을 도출하는 기법입니다.

탐욕 알고리즘은 한 번 내린 결정을 번복하지 않으며(No Backtracking), 각 단계에서의 최선의 선택이 모여 결국 전체 문제의 최적해(정답)가 될 것이라고 가정합니다.

동적 계획법(DP)과의 결정적 차이점

알고리즘을 공부할 때 가장 헷걸리는 것이 “이 문제는 그리디로 풀어야 하나, DP로 풀어야 하나?입니다. 두 알고리즘 모두 “최적해”를 구하는 데 사용되지만, 문제에 접근하는 철학 자체가 다릅니다.

구분	탐욕 알고리즘	DP
선택 기준	현재 단계에서 가장 좋은 것만 선택	모든 가능한 경우의 수를 고려하여 선택
과거의 결정	한 번 선택하면 절대 돌아보거나 수정하지 않음	과거에 구해둔 작은 문제의 답을 기억하고 재사용함
속도와 메모리	연산 속도가 매우 빠르고 메모리를 적게 차지함	모든 경우를 계산해야 하므로 상대적으로 느리고 메모리를 많이 씀
최적해 보장	항상 전체의 최적해를 보장하지는 않음	언제나 전체의 최적해를 완벽하게 보장함

요약하자면, DP가 “숲 전체를 스캔하여 가장 완벽한 길을 찾는 레이더”라면 그리디는 “내 눈앞에 보이는 가장 큰 나무만 계속해서 베어 나가는 도끼”라고 할 수 있습니다.

2. 탐욕 알고리즘의 수학적 정당성

그리디 알고리즘을 코딩 테스트에 적용하기 전에는 반드시 “눈앞의 이익만 쫓았을 때, 나중에 치명적인 손해를 보지 않는가?”를 검토해야 합니다. 무작정 그리디를 적용했다가는 오답의 늪에 빠지기 쉽습니다.

그리디 알고리즘이 항상 최적해를 도출하기 위해서는 다음 두 가지 수학적 조건이 완벽하게 성립해야 하며, 이를 알고리즘의 정당성(Justification)이라고 부릅니다.

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

   • “앞의 선택이 이후의 선택에 영향을 주지 않는다”
   • 각 단계에서 만들어낸 지역적 최적의 선택이 모여, 최종적으로 전역적 최적해(Global Optimum)를 구성할 수 있어야 합니다. 즉, 지금 가장 좋아 보이는 것을 선택해도 나중에 후회하고 되돌오갈 필요가 없어야 합니다.

2. 최적 부분 구조 (Optimal Substructure)

   • “전체 문제의 최적해는 부분 문제들의 최적해로 이루어진다”
   • 거대한 무제를 작게 쪼갰을 때, 그 하위 문제들에서 구한 최적의 답을 그대로 결합하면 결국 전체 문제의 답이 되는 구조를 말합니다.

코딩 테스트 시험장에서 위의 두 조건을 수학적으로 완벽하게 증명하기란 불가능에 가깝습니다. 실전에서는 “내가 지금 가장 큰 것(또는 작은 것)을 먼저 고른다고 해서, 무조건 정답이 될까? 반례는 없을까?”를 의심하는 것이 핵심입니다.

가장 유명한 예시인 “거스름돈 문제”를 통해 그리디의 함정을 살펴보겠습니다.

• 성공하는 경우: 동전이 서로 배수 관계일 때

  • 동전 단위: [500원, 100원, 50원, 10원]
  • 목표: 800원 거슬러 주기
  • 그리디 접근: 무조건 큰 동전부터 쓴다! ➔ 500원(1개) + 100원(3개) = 총 4개 최적해 성공!
  • 이유: 큰 동전이 항상 작은 동전들의 배수 형태이므로, 작은 동전 여러 개를 쓰는 것보다 큰 동전 하나를 쓰는 것이 무조건 이득임이 보장됩니다.

• 실패하는 경우(함정): 동전이 서로 무작위일 때

  • 동전 단위: [500원, 400원, 100원]
  • 목표: 800원 거슬러 주기
  • 그리디 접근: 무조건 큰 동전부터 쓴다! ➔ 500원(1개) + 100원(3개) = 총 4개 최적해 실패
  • 진짜 정답: 400원(2개) = 총 2개
  • 이유: 500원이 400원의 배수가 아니기 때문에, 가장 큰 동전을 먼저 골라버리면 오히려 동전 개수가 늘어나는 치명적인 손해가 발생합니다. 이 경우에는 그리디가 아닌 DP로 모든 경우의 수를 계산해야만 풀 수 있습니다.

3. 코딩 테스트에서의 그리디 ‘접근 시그널’

코딩 테스트 시험장에서 문제를 마주했을 때, “이건 그리디 알고리즘으로 풀어야겠다!”라고 눈치챌 수 있는 강력한 시그널(힌트)들이 있습니다. 다음 세 가지 조건 중 하나라도 해당한다면 우선적으로 그리디 알고리즘을 의심해 봐야 합니다.

1. 문제에 “가장 큰”, “가장 작은” 등의 극단적 키워드가 있을 때

   • 문제 지문에서 “가장 큰 순서대로”, “가장 작은 것을 골라”, “최소한의”, “최대한 많은”과 같은 키워드가 노골적으로 등장한다면 아주 강력한 시그널입니다.
   • 이런 문제들은 대부분 데이터를 정렬한 뒤, 양극단에 있는 값부터 차례대로 뽑아 쓰는 방식으로 해결됩니다. 즉 정렬과 그리디는 뗄래야 뗄 수 없는 단짝입니다.

2. 입력값 N의 범위가 비정상적으로 클 때 (예: 10만 이상)

   • 주어진 데이터의 개수 N이 100,000을 넘어가거나 1,000,000 수준이라면, 이 문제는 절대 이중 반복문을 사용하는 $O(N^2)$의 완전 탐색이나 2차원 DP로 풀 수 없습니다. (시간 초과 발생)
   • 입력값이 이렇게 거대하다면, $O(N \log N)$의 시간 복잡도를 가지는 정렬을 한 번 수행한 뒤, $O(N)$으로 배열을 한 번만 순회하며 탐욕적 선택을 하는 ‘그리디 알고리즘’이 출제자의 의도일 확률이 99%입니다.

3. 이전의 선택이 이후의 선택에 영향을 주지 않을 것 같은데?

   • 앞서 언급한 ‘탐욕적 선택 속성’을 직관적으로 느끼는 단계입니다. “내가 지금 제일 큰 걸 가져가도, 남은 애들끼리 최선을 다하는 데 아무런 방해가 되질 않네?”라는 확신이 들면 그리디입니다.

4. 대표적인 그리디 문제 유형 및 접근 패턴

그리디 알고리즘은 DP처럼 정형화된 점화식이 존재하지 않습니다. 대신, 실전에서 자주 출제되는 “접근 패턴”을 눈에 익혀두는 것이 유일하고도 가장 확실한 공부법입니다.

1. 스케줄링 (활동 선택 문제)

   • 대표 문제: 회의실 배정 (한 개의 회의실에서 가장 많은 회의를 진행하기)
   • 접근 패턴: “종료 시간이 빠른 순서대로 정렬하라”
     • 회의가 아무리 일찍 시작해도 늦게 끝나면 뒤에 올 수많은 회의를 다 날려버립니다. 따라서 “회의 시간이 짧은 것”이나 “일찍 시작하는 것”이 아니라, “무조건 일찍 끝나느 회의”부터 욱여넣는 것이 최적해를 보장합니다.

2. 투 포인터를 활용한 매칭

   • 대표 문제: 구명 보트(몸무게 제한이 있는 보트에 최소한의 보트로 사람 다 태우기)
   • 접근 패턴: “가장 무거운 사람과 가장 가벼운 사람을 짝지어라”
     • 배열을 정렬한 뒤, 양 끝에 포인터(가리키는 손가락)을 둡니다. 가장 무거운 사람을 태울 때, 자리가 남는다면 가장 가벼운 사람을 같이 태워 보내는 방식으로 양끝에서 중앙으로 좁혀오며 짝을 짓습니다.

3. 우선순위 큐 활용

   • 대표 문제: 카드 정렬하기 (여러 묶음의 카드를 두 개씩 합쳐서 하나로 만들 때, 비교 횟수의 최솟값 구하기)
   • 접근 패턴: “매 순간 가장 작은 덩어리 두개를 뭉쳐라”
     • 단순히 한 번 정렬하고 끝나는 것이 아니라, 합쳐진 덩어리가 다시 데이터에 추가되어 상황이 계속 변합니다. 이때 매번 다시 정렬하면 시간 초과가 발생하므로, 항상 최솟값을 $O(\log N)$만에 뽑아주는 우선순위 큐(Min Heap) 자료구조를 결합하여 탐욕적 선택을 반복해야 합니다.

4. 큰 단위부터 덜어내기 / 가장 큰 연산 적용하기

   • 대표 문제: 거스름돈, 1이 될 때까지 (N에서 1을 빼거나 K로 나누거나)
   • 접근 패턴: “숫자를 가장 빠르게 줄이는 연산을 최우선으로 하라”
     • 목표 수치를 0이나 1로 만들어야 할 때, “1을 빼는 것”보다 “나누는 것”이, “100원을 주는 것”보다 “500원을 주는 것”이 숫자를 훨씬 빠르게 줄입니다. 가능한 한 가장 “영향력이 큰 연산”을 먼저 수행하는 패턴입니다.