자바 코딩테스트 강좌 – 그리디 알고리즘
그리디 알고리즘(Greedy Algorithm)은 우리가 알고 있는 최적화 문제에 대해 가장 최적의 선택을 차례차례로 선택해 나가는 방식입니다. 이 과정에서 매 단계마다의 최적 선택이 전체 문제에 대한 최적 해를 보장하지는 않지만, 많은 경우에 유용하게 사용됩니다. 이번 글에서는 그리디 알고리즘을 활용한 문제를 풀어보겠습니다.
문제: 동전 변경
문제 설명: 주어진 금액을 만들기 위해 필요한 최소 동전 개수를 구하는 프로그램을 작성하세요. 동전의 종류는 [500원, 100원, 50원, 10원] 대가 주어집니다.
예를 들어, 770원을 만들기 위해 필요한 최소 동전 개수를 구하세요.
입력
- 정수 N (0 < N ≤ 10,000,000): 만들고자 하는 금액
출력
- 정수 K: 필요한 최소 동전 개수
입력 예시
770
출력 예시
6
문제 접근 방법
문제를 해결하기 위해서는 주어진 동전의 종류를 고려하여 그리디 알고리즘을 적용합니다. 그리디 알고리즘의 핵심은 매 단계에서 가장 큰 가치를 가진 동전을 사용하는 것입니다. 주어진 동전의 종류가 정렬된 경우, 가장 큰 동전부터 사용하여 잔여 금액을 계속 줄여 나갈 수 있습니다.
코드 구현
이제 자바를 사용하여 문제를 해결하는 코드를 구현해 보겠습니다. 다음은 동전 변경 문제를 해결하는 자바 코드입니다.
import java.util.Scanner;
public class CoinChange {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 주어진 금액을 입력받음
int N = scanner.nextInt();
// 사용할 동전의 종류
int[] coins = {500, 100, 50, 10};
int count = 0; // 동전 개수를 세기 위한 변수
for (int coin : coins) {
count += N / coin; // 현재 동전으로 만들 수 있는 개수 추가
N %= coin; // 잔여 금액 업데이트
}
System.out.println(count); // 최종 동전 개수 출력
scanner.close();
}
}
코드 설명
위의 코드에서는 다음과 같은 과정으로 최적의 해를 구합니다:
- 사용자 입력: Scanner 클래스를 사용하여 사용자가 만들고자 하는 금액을 입력받습니다.
- 패턴 설정: 사용할 동전의 배열을 정의합니다. 동전의 값은 내림차순으로 정리되어 있습니다.
- 동전 개수 계산: 각 동전에 대해 반복하여 가장 큰 동전부터 사용합니다. 현재 동전으로 몇 개를 사용할 수 있는지 계산하고, 잔여 금액을 업데이트합니다.
- 결과 출력: 최종적으로 필요한 동전의 개수를 출력합니다.
시간 복잡도
이 문제의 시간 복잡도는 O(1)입니다. 동전의 종류는 고정되어 있고, 입력된 금액에 관계 없이 상수 시간 내에 결과를 계산할 수 있습니다.
결론
그리디 알고리즘은 매 단계에서의 가장 최적의 선택을 통해 문제를 해결하는 방법입니다. 동전 변경 문제를 통해 그리디 알고리즘의 기본 원리를 이해하고, 이를 자바로 구현하는 방법에 대해 학습했습니다. 이 알고리즘은 다양한 최적화 문제에도 적용될 수 있으며, 알고리즘적 사고를 기르는 데 도움이 됩니다.
더 알아보기
그리디 알고리즘을 더욱 깊이 이해하기 위해, 다른 유형의 문제를 시도해 보시는 것을 추천합니다. 예를 들어, 혹은 최소 스패닝 트리(MST), 활동 선택 문제 등에서 그리디 알고리즘을 적용해 볼 수 있습니다.
부록
그리디 알고리즘은 다양한 문제를 해결하는 데 유용하게 사용될 수 있으며, 언젠가는 보다 복잡한 최적화 문제에 도전하게 될 것입니다. 실제 코딩 테스트에서는 문제를 정확히 읽고 그리디 알고리즘이 적합한지 판단하는 것이 중요합니다. 문제를 해결하는 데 필요한 수학적 사고와 자료 구조에 대한 이해를 함께 키워나가면 좋습니다.