안녕하세요! 이번 블로그 포스트에서는 C++을 사용한 알고리즘 문제를 풀어보며, 불우이웃 돕기라는 주제로 사회에 기여할 수 있는 방법을 알아보겠습니다. 알고리즘 문제는 우리에게 문제 해결 능력을 기르는 데 중요한 역할을 하며, 실제 취업 면접에서도 자주 등장하는 주제입니다.
문제 설명
많은 사람들이 어려움을 겪고 있는 사회적인 문제에서, 해마다 크리스마스를 맞이하여 자선 기부를 진행합니다. 각 기부자는 자신이 원하는 금액을 기부할 수 있고, 이 기부자들의 기부액을 통해 특정한 수의 불우이웃들을 도울 수 있도록 하려고 합니다. 하지만 각 불우이웃은 기부 받을 수 있는 최대 금액이 정해져 있습니다.
문제 정의
주어진 기부자들의 기부액과 불우이웃이 받을 수 있는 최대 금액의 배열이 있을 때, 모든 불우이웃들이 받을 수 있는 최대 기부 총액을 구하시오.
입력 형식
- 첫 번째 줄: 기부자의 수
N(1 ≤ N ≤ 1000) - 두 번째 줄: 각 기부자의 기부액을 나타내는
N개의 정수A1, A2, ..., AN(1 ≤Ai≤ 10000) - 세 번째 줄: 불우이웃의 수
M(1 ≤ M ≤ 1000) - 네 번째 줄: 각 불우이웃이 받을 수 있는 최대 금액을 나타내는
M개의 정수B1, B2, ..., BM(1 ≤Bj≤ 10000)
출력 형식
모든 불우이웃들이 받을 수 있는 최대 기부 총액을 출력하시오.
예제 입력
5 1500 2000 3000 4000 5000 3 2000 3000 10000
예제 출력
10000
문제 해결 접근 방법
이 문제를 해결하기 위한 접근 방법은 다음과 같습니다:
- 자선 기부자들의 기부액과 각 불우이웃이 받을 수 있는 최대 금액을 정렬합니다.
- 각 기부자가 최대로 기부할 수 있는 금액을 한 사람씩 확인하면서 각 불우이웃의 최대 금액을 초과하지 않는 범위 내에서 할당합니다.
- 각 기부의 결과를 누적하여 총 기부액을 계산합니다.
C++ 코드 구현
아래는 위의 접근 방법에 대한 C++ 코드입니다:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N;
cout << "기부자 수 입력: ";
cin >> N;
vector<int> donations(N);
cout << "기부액 입력: ";
for (int i = 0; i < N; i++) {
cin >> donations[i];
}
int M;
cout << "불우이웃 수 입력: ";
cin >> M;
vector<int> beneficiaries(M);
cout << "불우이웃 최대 받을 금액 입력: ";
for (int i = 0; i < M; i++) {
cin >> beneficiaries[i];
}
// 기부자와 불우이웃의 배열 정렬
sort(donations.rbegin(), donations.rend());
sort(beneficiaries.rbegin(), beneficiaries.rend());
int totalDonated = 0;
int donationIndex = 0;
int beneficiaryIndex = 0;
// 기부자와 불우이웃 매칭
while (donationIndex < N && beneficiaryIndex < M) {
if (donations[donationIndex] <= beneficiaries[beneficiaryIndex]) {
totalDonated += donations[donationIndex];
donationIndex++;
} else {
totalDonated += beneficiaries[beneficiaryIndex];
beneficiaryIndex++;
}
}
cout << "최대 기부 총액: " << totalDonated << endl;
return 0;
}
코드 설명
위 코드는 다음과 같은 방식으로 동작합니다:
- 기부자 수와 불우이웃 수를 입력받고, 각각의 기부액과 최대 수혜 금액을 입력받습니다.
- 각 배열을 내림차순으로 정렬합니다. 이렇게 하면 높은 기부부터 낮은 기부로 비교할 수 있어 최적의 배분이 가능해집니다.
- 각 기부자가 최대 금액에 도달하거나 불우이웃의 최대 수혜 금액을 초과하지 않도록 작동하여 가능하면 많은 기부가 이루어지도록 합니다.
- 총 기부액을 계산하여 출력합니다.
성과 검증 및 테스트
작성한 코드는 다양한 입력 예제를 통해 검증되어야 합니다. 일반적인 사례 외에도 극단적인 사례(예: 모든 기부자가 동일한 금액 기부 등)도 고려하여 테스트를 진행해야 합니다.
테스트 케이스 예시
입력: 3 3000 3000 3000 4 1500 3000 2000 1000 출력: 9000
위 코드에서 기부자는 3000, 3000, 3000을 기부하고, 불우이웃은 각각 1500, 3000, 2000, 1000을 받을 수 있습니다. 이 경우 가능한 최대 기부 금액은 9000입니다.
마치며
이번 포스트에서는 C++을 사용하여 기부자와 불우이웃을 매칭하는 알고리즘 문제를 통해 논리적인 사고를 기르는 방법을 살펴보았습니다. 코딩테스트에서 자주 사용되는 문제 해결 방법이자 실질적으로 사회적 기여를 할 수 있는 문제를 학습하여 여러분의 프로그래밍 능력을 발전시킬 수 있기를 바랍니다. 코딩 테스트 준비에 많은 도움이 되기를 기원합니다!