[코드 인터뷰 대비 시리즈 #7] 그리디(Greedy) 알고리즘 문제 접근 패턴 정리

여러분, 그리디(Greedy) 알고리즘은 많은 인터뷰 문제에서 자주 활용되는 패턴 중 하나입니다. 그리디 알고리즘은 매 순간 지역적으로 최선(최적)이라고 생각되는 선택을 함으로써 전체 문제의 최적해에 도달하려는 전략입니다. 물론 그리디 접근이 항상 전역 최적해를 보장하지는 않지만, 특정 조건(그리디 선택 정당성)이 성립하면 복잡한 문제도 단순하고 효율적으로 해결할 수 있어요. 이번 글에서는 그리디 알고리즘 문제에 직면했을 때 어떤 식으로 접근하고, 정당성을 어떻게 입증하며, 코너 케이스나 최적화 포인트, 면접에서의 커뮤니케이션 방법까지 단계별로 매우 구체적으로 다루어보겠습니다.

그리디 문제에서 중요한 것은 "그리디 선택(Locally Optimal Choice)을 정당화할 수 있는가?" 입니다. 이를 위해 문제 구조를 분석하고, 그리디 접근이 유효한 이유를 명확히 설명할 수 있어야 합니다. 또한 일부 문제는 정렬, 우선순위 큐, 스택/큐와 결합해 그리디 로직을 구현하고, std::expected나 std::format을 통해 에러나 로깅을 처리하며, coroutine이나 Ranges를 통해 비동기적 혹은 파이프라인 형태로 문제를 확장할 수도 있습니다.

1. 그리디 알고리즘 접근 시 첫 단계: 정당성 검토와 패턴 인식

그리디 접근을 시도하기 전에, 문제를 이렇게 분석해보세요.

1. 문제를 순간순간의 최적 선택으로 해결 가능한가?
   즉, "이 순간 이 선택이 전역 최적해로 가는 길인지 어떻게 알지?"를 생각해야 합니다.
2. 정렬 혹은 우선순위 큐로 후보를 관리할 수 있는가?
   많은 그리디 문제에서 정렬 후 앞에서부터 순서대로 선택하거나, 우선순위 큐를 통해 항상 현재 가능한 가장 최적 후보를 선택하는 형태가 등장합니다.
3. 증명 혹은 반례 사고하기:
   면접에서 "왜 그리디가 최적해를 보장하나요?"라는 질문에 대비해, “그리디 선택을 다른 최적해와 비교했을 때 뒤바꿔도 성립한다”는 식의 교환 논증, 혹은 그래프나 interval 문제에서 정렬 기준에 따른 최적성 증명을 간단히 설명할 수 있어야 합니다.

2. 대표적인 그리디 문제 패턴

패턴 1: 활동 선택(Activity Selection), 회의실 배정(Interval Scheduling)

• 문제: 주어진 인터벌(시작 시간, 끝 시간) 집합에서 겹치지 않게 최대 개수의 활동(회의)을 선택.
• 아이디어: 끝나는 시간이 가장 빠른 활동부터 선택하면 최적해를 보장.
• 단계별 사고 과정:
  1. 활동을 종료 시간 기준으로 정렬.
  2. 가장 먼저 끝나는 활동을 선택, 그 이후 시작시간이 이 활동 끝나는 시간보다 크거나 같은 다음 활동을 선택.
  3. 이 방식으로 O(N log N) 정렬 후 O(N) 순회.
• 정당성: 끝나는 시간이 빠른 활동을 먼저 선택하면 남은 시간에 더 많은 활동을 배치 가능.
• 코너 케이스: 활동이 없는 경우 0 반환, 모든 활동이 서로 겹칠 경우 1개만 선택.
• 면접에서: “정렬 후 항상 가장 빨리 끝나는 활동을 고르면 최적. O(N log N) 정렬 + O(N) 선택. std::expected로 활동 리스트 비어있으면 에러, std::format으로 선택 과정 로깅 가능.”

Baekjoon "회의실 배정" 문제나 LeetCode "Meeting Rooms" 류 문제로 연습해보세요.

패턴 2: 그리디로 최솟값/최대값 달성하기(예: 화폐 거스름돈 문제)

• 문제: 동전 단위가 {1,5,10,50,100,...} 식으로 주어질 때 거스름돈을 최소 개수 동전으로 지급.
• 아이디어: 가장 큰 단위 동전부터 최대 개수로 사용, 남은 금액에 대해 반복.
• 단계별 사고 과정:
  1. 동전 단위를 정렬 혹은 이미 정렬되어 있다 가정.
  2. 가장 큰 단위 동전부터 사용할 수 있는 만큼 사용.
  3. 남은 금액에 대해 다음으로 큰 단위 동전 적용.
• 정당성: 여기서 주어진 동전 단위 조건(예: 한국 화폐 단위)에서는 그리디로 최소 개수 보장. 하지만 일반적인 동전 단위에서는 그리디가 최적 보장 안 됨.
• 코너 케이스: 금액이 0이면 0개 동전 사용. 동전 세트가 없는 경우 에러 반환(‘no solution’).
• 면접에서: “조건 하에 그리디가 최적임을 알고, O(N) 또는 O(N log N) (정렬 시)로 해결. std::expected로 비정상 입력(금액<0) 시 에러 반환 가능.”

Programmers 화폐 문제나 Codeforces 거스름돈 문제로 연습.

패턴 3: 스케줄링, 우선순위 큐 활용 그리디

• 예: 일정(작업)을 끝내기 위해 마감(deadline)이 있는 작업들을 최소 지연으로 처리하거나 최대 보상을 얻는 문제.
• 아이디어: 우선순위 큐를 활용해 가장 보상이 큰 작업부터 마감 전에 처리, 또는 마감 순으로 정렬 후 가능한 한 뒤로 배치하는 식.
• 단계별 사고 과정:
  1. 작업을 마감 시간 기준 정렬.
  2. 각 작업을 순회하며 우선순위 큐에 작업 보상을 삽입.
  3. 마감 시간을 초과하는 경우 우선순위 큐에서 가장 보상 작은 작업 제거.
  4. 결과적으로 우선순위 큐에 남은 작업들이 최대 보상 조합.
• 정당성: 항상 마감 시간을 고려해 그 시점까지 할 수 있는 작업 중 보상이 큰 것 위주로 남기는 그리디 전략.
• 코너 케이스: 작업이 하나도 없으면 0, 모든 작업 마감 불가능이면 가능한 것만 수행.
• 면접에서: “정렬+우선순위 큐로 O(N log N)에 최대 보상 작업 세트 선택 가능”이라 설명.

Codeforces 우선순위 큐 활용 스케줄링 문제나 Baekjoon 유사 문제로 연습.

패턴 4: 정렬+이진 탐색 결합한 그리디

• 예: 투 포인터나 이진 탐색과 결합해 그리디로 선택.
• 예를 들어, 두 그룹의 사람들을 매칭하는 문제에서 한 그룹을 정렬, 다른 그룹을 순회하며 이진 탐색으로 가능한 가장 작은 자원 소비로 매칭.
• 이 경우 그리디로 "가장 작은 비용으로 현재 요청 처리"를 반복.
• 면접 시: “정렬+이진 탐색으로 각 단계 최소 비용 선택, O(N log N) 정렬 + O(M log N) 탐색” 등 복잡도 제시.

3. 정당성 증명(증명 아이디어) 언급

면접관이 “왜 그리디로 최적해 보장?” 질문하면 교환 논증, 반례 없음을 언급하세요.

예: 활동 선택 문제에서, 만약 정답이 A라고 하자. A는 어떤 활동을 가장 빨리 끝나는 활동이 아닌 다른 활동으로 시작했다고 가정. 그 활동보다 일찍 끝나는 활동으로 바꿔도 전체 활동 수 감소 없이 해법 유지 가능. 이런 식으로 최적해를 변형해 그리디 해법으로 변환할 수 있음을 설명하면 됩니다.

코너 케이스: 정당성 없는 문제(예: 거스름돈 동전 단위가 비표준이면 그리디 안 먹힐 수 있음). 이때 그리디가 안 된다고 인식하고 다른 기법(DP) 시도.

4. 복잡도 분석과 최적화

그리디 문제는 대체로 정렬 O(N log N) 후 O(N) 또는 O(N log N)으로 처리하는 경우가 많습니다. 우선순위 큐 사용 시 삽입/삭제 O(log N)로 연산 횟수만큼 곱해 O(N log N).

메모리 측면: 대부분 그리디는 추가적으로 정렬 외에 O(N) 정도 메모리로 끝나는 경우가 많습니다. DP처럼 대규모 테이블 필요 없는 경우가 많아, 면접에서 “메모리 O(N) 또는 O(1)이미스” 언급이 쉽습니다.

코너 케이스를 통한 최적화: 일부 문제에서 n이 매우 크면 정렬 O(N log N)도 부담스러울 수 있다. 이 경우 희소 데이터 구조나 다른 아이디어 제안 가능. 면접에서 이런 생각을 언급하면 고급스러운 인상을 줄 수 있습니다.

5. 조건부 처리, 비동기 처리, 로깅, 에러 처리, Ranges 활용

그리디 문제에서도 다양한 확장 아이디어가 가능합니다.

• 조건부 처리:
  문제 규모(n)나 값 범위에 따라 정렬 없이 해결 가능하면 그렇게 한다든가, 특정 조건에서 그리디 대신 DP 시도. 면접에서 “n이 작을 땐 브루트포스도 OK, n이 크면 그리디 필요” 같은 말로 문제 규모 따른 접근 방식 선택 가능성 시사.
• 비동기 처리 (Coroutine):
  대규모 입력을 스트리밍 받으면서 실시간으로 그리디 의사결정을 해야 한다면 coroutine으로 incoming 데이터 처리와 로직 분리. 면접에선 “스트리밍 데이터 대비해서 coroutine으로 부분 정렬한 후 우선순위 큐에 삽입해 항상 최적 후보를 유지” 같은 상상력 발휘 가능.
• 로깅(std::format):
  그리디 선택 과정(예: 각 단계에서 어떤 활동 선택했는지, 어떤 간선 선택했는지)을 std::format으로 로깅하면 디버깅 도움. 면접에서 디버깅 전략 언급하면 코드 품질 강조.
• 에러 처리(std::expected):
  그리디 접근이 불가능한 상황(예: 입력 부적합)에서 std::expected 반환해 명시적으로 에러 처리 가능.
  예: “동전 단위가 비표준이라 그리디 최적성 보장 안 됨”을 에러로 반환 가능.
• Ranges 활용:
  정렬된 시퀀스에 std::views::filter, std::views::transform을 결합해 그리디 로직 전처리나 후처리에 응용할 수도 있음. 면접 중 “C++20 Ranges로 정렬된 데이터에 파이프라인 적용” 언급하면 모던 C++ 능력 어필.

6. 예제 문제를 통한 실전 연습

• 활동 선택(Activity Selection) 문제:
  Baekjoon "회의실 배정" 문제나 LeetCode "Meeting Rooms II" 문제로 연습. 정렬 후 끝나는 시간 빠른 활동부터 선택. 정당성: 교환 논증.
• 거스름돈(Coin Change) 문제(특수 케이스):
  Programmers 동전 문제나 Baekjoon 단위가 표준화폐일 때 그리디로 최소 동전 수 해결. 정당성: 표준 화폐단위에서는 큰 단위 먼저 사용하는 것이 항상 최적.
• 우선순위 큐 스케줄링 문제:
  Codeforces나 LeetCode에서 작업 마감 문제. 정렬+우선순위 큐로 O(N log N) 해결. 정당성: 마감 전 가능한 가장 가치 높은 작업 유지.
• 정렬+이진 탐색으로 최적 해결 문제:
  Baekjoon에서 정렬 후 이진 탐색을 이용해 특정 조건 충족 원소 찾기. 그리디로 "항상 최소 비용 선택"을 반복하는 문제에서 이진 탐색으로 후보를 효율적으로 찾을 수 있음.

각 문제에서 복잡도, 정당성, 코너 케이스, 면접 중 의사소통 전략을 연습해보세요. "O(N log N) 정렬 후 한 번 순회"라는 말은 그리디 문제에서 자주 등장하는 상용구(samrt phrase)가 될 겁니다.

7. 면접장에서의 사고 과정 표현 예시

"회의실 배정" 문제를 면접에서 설명한다고 생각해보겠습니다.

1. 접근 아이디어 언급:
   “이 문제는 겹치지 않고 최대 회의를 선택하는 문제인데, 끝나는 시간이 가장 빠른 회의부터 선택하면 남은 시간에 더 많은 회의 배치 가능합니다. 즉, 그리디하게 끝나는 시간 기준 정렬 후 순회.”
2. 단계별 구현 로직 설명:
   • 회의들을 종료 시간 기준으로 정렬(O(N log N)).
   • 현재 선택한 회의의 끝나는 시간을 endTime라 하고, 다음 회의를 순회하며 시작 시간이 endTime 이상이면 회의 선택, endTime 업데이트.
   • O(N log N) 정렬 + O(N) 순회.
3. 정당성 언급:
   “가장 빨리 끝나는 회의를 먼저 선택해도 최적해를 방해하지 않아요. 더 늦게 끝나는 회의 대신 빨리 끝나는 회의를 선택해도 전체 회의 수를 줄이지 않고 최적해를 유지할 수 있으므로 그리디 정당성 확보.”
4. 코너 케이스:
   “회의가 하나도 없으면 0 반환, 모든 회의가 시간 완전히 겹친다면 결국 1개만 선택 가능.”
5. 추가 기능 아이디어:
   “입력이 비정상(예: 종료시간<시작시간)일 때 std::expected로 에러 반환 가능. 디버깅 위해 std::format으로 정렬 후 회의 목록과 선택 과정을 로깅할 수도 있습니다.”

이렇게 하면 면접관은 여러분이 그리디 방식으로 문제를 해결하는 전 과정을 논리적으로 사고하고, 오작동 시나리오까지 고려하며, 디버깅과 확장 가능성까지 생각하는 아주 완성도 높은 후보자로 판단할 것입니다.

마무리

이번 글에서 그리디 알고리즘 문제를 접근하는 전반적인 패턴을 매우 구체적으로 다뤘습니다. 그리디 문제를 만났을 때 먼저 정당성을 고민하고, 정렬이나 우선순위 큐, 이진 탐색과 결합해 O(N log N) 이하로 최적화할 수 있는지 생각해보세요. 또한, 코너 케이스(입력 없음, 음수, 비표준 화폐 단위), 복잡도 분석, 메모리 관리, 그리고 면접 중 의사소통 방식을 단계적으로 준비한다면, 어떤 그리디 문제라도 당황하지 않고 풀 수 있습니다.

여러분이 이 글을 통해 그리디 패턴을 확실히 이해하고, 실전 인터뷰에서 논리적이고 자신감 있게 그리디 접근을 제안하고 구현해나가길 기대합니다.