Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 IPO 문제: 우선순위 큐로 최종 자본 극대화하기

문제 상황

한 회사 A가 곧 IPO(기업공개)를 진행하려 한다고 가정해 봅시다. 주식을 좋은 가격에 판매하기 위해 A는 IPO 전에 여러 프로젝트를 수행해 자본을 늘리고 싶어 합니다. 하지만 A의 자원은 제한적이어서, 최대 k개의 서로 다른 프로젝트만 완료할 수 있습니다. 과연 최대 k개의 프로젝트를 마친 뒤 총 자본을 최대화하려면 어떤 프로젝트를 어떤 순서로 선택해야 할까요?

문제 정의

여러 개의 프로젝트가 주어집니다. 각 프로젝트 i마다 순수익 Pi가 있으며, 해당 프로젝트를 시작하려면 최소 자본 Ci가 필요합니다. 처음에 우리가 가진 자본은 W입니다. 프로젝트 하나를 완료할 때마다 그 프로젝트의 순수익을 얻게 되고, 이 수익은 총 자본에 더해집니다.

정리하면, 주어진 프로젝트 목록에서 최대 k개의 서로 다른 프로젝트를 선택해 최종 자본을 최대화하고, 그 최대화된 자본 값을 출력하는 것이 목표입니다.

입력 예시

k = 2, W = 0, 이익 배열 [1,2,4], 자본 배열 [0,1,1]이 주어졌을 때 출력은 5입니다.

처음 자본이 0이므로 인덱스 0의 프로젝트(필요 자본 0)만 시작할 수 있습니다. 이 프로젝트를 완료하면 이익 1을 얻어 자본이 1이 됩니다. 자본 1이 되면 인덱스 1 또는 2의 프로젝트를 시작할 수 있는데, 더 큰 이익을 내는 인덱스 2의 프로젝트를 선택하는 것이 유리합니다. 따라서 최종 답은 0 + 1 + 4 = 5가 됩니다.

풀이 접근 방법

이 문제는 그리디(Greedy) 기법과 우선순위 큐(priority queue)를 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 현재 자본으로 시작할 수 있는 프로젝트 중에서 항상 순수익이 가장 큰 프로젝트를 선택한다.
  • 이를 위해 '필요 자본' 기준의 최소 힙(min-heap)과, '시작 가능한 프로젝트의 이익'을 관리하는 최대 힙(max-heap), 두 개의 우선순위 큐를 사용합니다.

알고리즘 단계

  1. 우선순위 큐 pqCapital(자본 기준 최소 힙)과 pqMain(이익 기준 최대 힙)을 생성합니다.
  2. n := Profits의 크기로 설정합니다.
  3. i를 0부터 n-1까지 반복하면서 { Profits[i], Capital[i] } 쌍을 pqCapital에 삽입합니다.
  4. i를 0부터 k-1까지 반복하면서 다음을 수행합니다.
    • pqCapital이 비어 있지 않고, pqCapital의 top 요소의 자본값(second)이 W 이하인 동안, top 요소를 pqMain으로 옮긴 뒤 pqCapital에서 제거합니다.
    • pqMain이 비어 있다면 더 이상 진행할 수 있는 프로젝트가 없으므로 반복문을 빠져나갑니다.
    • W에 pqMain의 top 요소의 이익값(first)을 더하고, pqMain에서 해당 요소를 제거합니다.
  5. W를 반환합니다.

즉, 매 단계마다 현재 자본으로 실행 가능한 프로젝트들을 최대 힙에 모아 놓고, 그중 이익이 가장 큰 것을 하나씩 실행하는 방식입니다. 이렇게 하면 매번 최선의 선택을 하게 되어 최종 자본이 최대화됩니다.

C++ 구현 예제

아래 구현을 통해 더 잘 이해해 보겠습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
struct Comparator{
   bool operator() (pair <int, int> a, pair <int, int> b){
      return !(a.second < b.second);
   }
};
class Solution {
public:
   int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
   priority_queue < pair <int, int>, vector < pair <int, int> >, Comparator> pqCapital;
   priority_queue < pair <int ,int> > pqMain;
   int n = Profits.size();
   for(int i = 0; i < n; i++){
      pqCapital.push({Profits[i], Capital[i]});
   }
   for(int i = 0; i < k; i++){
      while(!pqCapital.empty() && pqCapital.top().second <= W){
         pqMain.push(pqCapital.top());
         pqCapital.pop();
      }
      if(pqMain.empty()) break;
         W += pqMain.top().first;
         pqMain.pop();
      }
      return W;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,4}, v1 = {0,1,1};
   cout << (ob.findMaximizedCapital(2,0, v, v1));
}

입력

2
0
[1,2,4]
[0,1,1]

출력

5

복잡도 분석

  • 시간 복잡도: 모든 프로젝트를 힙에 삽입하는 데 O(n log n), 각 반복에서 힙 연산이 발생하므로 전체적으로 O((n + k) log n)입니다.
  • 공간 복잡도: 두 개의 우선순위 큐에 프로젝트 정보를 저장하므로 O(n)입니다.

마무리

IPO 문제는 '매 순간 최선의 선택을 한다'는 그리디 전략이 최적해를 보장하는 대표적인 유형입니다. 두 개의 우선순위 큐를 활용해 '지금 시작할 수 있는 프로젝트'와 '그중 가장 수익성 높은 프로젝트'를 효율적으로 관리하는 것이 핵심 포인트입니다. 비슷한 패턴은 작업 스케줄링, 리소스 할당 등 다양한 알고리즘 문제에서도 응용되므로 꼭 익혀 두시기 바랍니다.