C++ 코딩테스트 강좌, 그리디 알고리즘

1. 그리디 알고리즘이란?

그리디 알고리즘(Greedy Algorithm)은 문제를 해결하는 과정에서 매 단계에서 최적이라고 생각되는 선택을 하는 방식입니다. 일반적으로 그리디 알고리즘은 문제를 단계적으로 해결하며, 각 단계에서의 최적 선택이 전체 문제에 대한 최적해를 만들어낼 것이라고 가정합니다. 단, 이러한 그리디 선택이 항상 최적해를 보장하지는 않습니다.

2. 그리디 알고리즘의 특징

근시안적 접근: 현재 문제에서 최적의 해를 선택하므로 최종 결과가 최적일 것이라는 보장이 없다.
문제에 따라 적합: 모든 문제에서 그리디 알고리즘이 최적의 해를 제공하지는 않지만, 효율적으로 해결할 수 있는 문제도 많다.
구조적 특징: 최적 부분 구조와 탐욕적 선택 성질을 가진 문제에서 효과적이다.

3. 문제 설명

이번 강좌에서는 오는 코딩테스트에서 자주 출제되는 “거스름돈” 문제를 다룰 것입니다. 이 문제는 다음과 같이 정의됩니다:

거스름돈을 최소한의 동전 개수로 주는 프로그램을 작성하시오. 단, 동전은 500원, 100원, 50원, 10원으로 주어진다. 주어진 금액이 N 원일 때 최소 동전 개수로 거슬러 주는 알고리즘을 구현하시오.

4. 문제 분석

거스름돈을 최소 동전 개수로 주기 위해서는 가장 큰 동전부터 사용하여 잔돈을 줄여나가는 방식이 효과적입니다. 이렇게 하면 남은 금액이 줄어들수록 최적의 해를 보장할 수 있습니다. 그리디 알고리즘의 선택 속성을 활용하여, 다음과 같은 단계를 거쳐 solution을 도출할 수 있습니다:

4.1. 필요한 동전

500원
100원
50원
10원

4.2. 동전 사용 과정

가장 큰 동전부터 가능한 최대한 사용합니다. 예를 들어, 1260원을 거슬러 줄 경우, 사용되는 동전의 개수는 다음과 같습니다:

500원 → 2개 (1000원)
100원 → 2개 (200원)
50원 → 1개 (50원)
10원 → 1개 (10원)

최종적으로, 1260원을 거슬러 주기 위해 사용된 동전의 총 개수는 6개입니다.

5. 구현

이제 이 과정을 C++로 구현해보겠습니다. 다음은 상기 내용을 바탕으로 한 C++ 코드입니다:

#include <iostream>

using namespace std;

int main() {
    int change = 1260; // 거슬러 줄 금액
    int coinTypes[] = {500, 100, 50, 10}; // 사용 가능한 동전들
    int coinCount = 0; // 사용된 동전 개수

    for(int i = 0; i < 4; i++) {
        coinCount += change / coinTypes[i]; // 현재 동전으로 나눔
        change %= coinTypes[i]; // 나머지 금액 업데이트
    }

    cout << "최소 동전 개수: " << coinCount << endl;
    return 0;
}

6. 코드 설명

위의 코드는 거슬러 줄 금액이 1260원일 때 최소 동전 개수를 계산하는 프로그램입니다.

change: 거슬러줘야 할 금액을 저장합니다.
coinTypes: 사용 가능한 동전의 종류를 배열로 저장합니다.
coinCount: 사용된 동전의 총 개수를 저장합니다.
for 루프를 사용하여 각 동전의 종류에 대해 몇 개를 사용하는지 계산합니다.
나머지 금액을 업데이트하여 다음 동전으로 넘어갑니다.

7. 동작 결과

위 코드를 실행하면, 콘솔에 다음과 같은 결과가 출력됩니다:

최소 동전 개수: 6

8. 복습

이번 강좌에서는 그리디 알고리즘을 활용하여 거스름돈 문제를 해결하는 방법을 배웠습니다. 그리디 알고리즘의 핵심은 매 단계에서 최적이라고 판단되는 선택을 하는 것입니다. 이 알고리즘은 다양한 문제를 해결하는 데 있어 매우 유용하게 쓰일 수 있습니다.

9. 연습 문제

아래와 같은 다른 과제를 통해 그리디 알고리즘을 더욱 연습할 수 있습니다:

주어진 금액에서 사용할 수 있는 동전의 종류를 입력받아 최소 동전 개수를 구하시오.
개별 동전의 가치를 임의로 조정할 수 있는 프로그램 작성.
성능 향상을 위한 개선된 알고리즘을 연구하고 적용해보시오.

10. 마무리

그리디 알고리즘은 많은 문제에 대한 해결책을 제공할 수 있는 강력한 도구입니다. 이번 강좌에서 제시한 문제를 통해 알고리즘에 대한 개념 이해는 물론 코드 구현 연습도 할 수 있었기를 바랍니다. 앞으로도 다양한 알고리즘에 대해 계속해서 학습하여, 더 나은 프로그래머로 성장해 나가기를 바랍니다.