[JAVA] 완전탐색 Vs 그리디 알고리즘 이해하기

알고리즘 문제풀이 과정에 있어서 완전탐색, 그리디 알고리즘에 대한 기본 이해가 잘 갖춰져 있어야 접근방식을 효율적으로 설계하고 풀어갈 수 있다. 

 

기초가 탄탄해야 하는 만큼 다시 한번 더 내용을 정리하고 넘어가보고자 한다.

 

완전 탐색

: 가능한 모든 경우의 수를 전부 확인하여 문제를 해결하는 방법

완전 탐색은 모든 문제 해결의 기본이 되는 좋은 시작점!
하지만 문제의 복잡도나 처리해야할 데이터의 양이 늘어날수록 실행시간이 기하급수적으로 증가하게 되는 부분이 발생하게 됨

문제의 크기와 상황을 고려하여 전략적으로 사용해야 함

 

그리디 알고리즘

: 현재 상황에서 가장 좋아 보이는 선택을 하는 방법

 

그리디 알고리즘을 사용하기 위해서는 두가지 필수 조건이 있고 만족해야만 사용이 가능함

1. 탐욕 선택 속성

2. 최적 부분 구조

 

두 진행방식에 따라 특징을 표로 정리하자면 아래와 같다.

항목	완전 탐색	그리디 알고리즘
접근 방식	모든 경우의 수를 탐색	각 단계에서 최적 선택
최적해 보장	항상 보장	특정 조건에서만 보장
상대적 시간복잡도	높음	낮음
적용 범위	문제의 제한 시간 초과가 나지 않는 모든 문제	탐욕 선택 속성과 최적 부분 구조의 조건을 만족하는 문제

 

언제 어떤 알고리즘을 사용하면 될까?

완벽한 공식은 없지만 다양한 문제를 풀어보면서 상황에 맞는 알고리즘을 선택할 수 있음 

 

완전 탐색을 사용하는 경우

• 문제의 입력 크기가 작을 때
• 정확한 최적해가 필요할 때
• 다른 알고리즘을 적용하기 어려운 경우

 

그리디 알고리즘을 사용하는 경우

• 문제의 크기가 클 때
• 실행 시간이 중요한 경우
• 부분적인 최적해가 전체 최적해로 이어지는 문제일 때

 

직전 포스팅에서 다뤘던 동전 거스름돈 문제에 대해 두가지 알고리즘 풀이방식을 적용하여 비교해보겠다. 

 

문제 요구사항

철수는 물건을 구매하고 거스름돈을 받아야 합니다. 
가게에는 500원, 100원, 50원, 10원짜리 동전이 무한히 있다고 가정할 때, 
특정 금액을 거슬러주기 위한 최소한의 동전 개수를 구하는 프로그램을 작성해보세요.
 
//입력
- 첫째 줄에 거슬러 주어야 할 금액 N이 주어집니다. (0 ≤ N ≤ 10,000)
- 사용할 수 있는 동전의 종류: 500원, 100원, 50원, 10원
 
//출력
- 거스름돈 N원을 만들기 위한 최소 동전 개수를 출력합니다.

 

그리디 알고리즘 풀이

접근방법: 
- 가장 큰 단위의 동전부터 최대한 거스름돈 주기(그리디)

1. 초기화 단계
   1.1. 동전을 큰 단위부터 작은 단위 순으로 정렬
   1.2. 거스름돈 금액을 저장할 변수 준비
   1.3. 사용된 동전 개수를 저장할 변수 초기화

2. 거스름돈 계산 단계
   2.1. 가장 큰 단위의 동전부터 순차적으로 진행
   2.2. 현재 동전으로 거스름돈을 최대한 많이 거슬러줌
   2.3. 남은 거스름돈에 대해 다음으로 큰 동전으로 반복

3. 결과 반환 단계
   3.1. 남은 금액이 0이면 사용된 총 동전 개수 반환
   3.2. 남은 금액이 0이 아니면, -1 반환
   
시간복잡도: O(K) - K은 동전의 종류 수

 

완전 탐색 풀이

기본 도식화

입력 금액 (N원)
     ↓
각 동전별 최대 사용 가능 개수 계산
     ↓
4중 반복문 활용
     ↓
500원 동전: 0개부터 최대 개수까지
     ↓
100원 동전: 0개부터 최대 개수까지
     ↓
 50원 동전: 0개부터 최대 개수까지
     ↓  
 10원 동전: 0개부터 최대 개수까지
     ↓
각 동전 조합의 합이 목표 금액과 일치하는지 확인
     ↓
일치하는 경우 중 최소 동전 개수 선택

 

세부 구현

1. 초기화 단계
   1.1. 각 동전 별로 사용 가능한 최대 개수 계산
        - 목표 금액 / 동전 금액 = 최대 사용 가능 개수
        예) 500원짜리는 최대 몇개, 100원짜리는 최대 몇개...
   1.2. 최소 동전 개수를 저장할 변수를 최댓값으로 초기화

2. 모든 조합 시도 단계 (4중 for문 사용)
   2.1. 500원: 0개부터 최대 개수까지 반복
   2.2. 100원: 0개부터 최대 개수까지 반복
   2.3.  50원: 0개부터 최대 개수까지 반복
   2.4.  10원: 0개부터 최대 개수까지 반복
        각 조합에 대해:
        - 현재 조합으로 만들어지는 총 금액 계산
        - 목표 금액과 일치하는지 확인
        - 일치하면 사용된 동전 개수(현재 4중 for문의 각 인덱스 합)와 
          현재 최소값 비교하여 갱신

3. 결과 반환 단계
   3.1. 찾은 최소 동전 개수 반환
   3.2. 해를 찾지 못한 경우 -1 반환
   
시간복잡도: O(n₁ × n₂ × n₃ × n₄)
- 각 n은 각 동전으로 만들 수 있는 최대 개수입니다.
예를 들어 2000원을 만들 때:
500원: 최대 4개 (n₁ = N//500)
100원: 최대 20개 (n₂ = N//100)
50원: 최대 40개 (n₃ = N//50)
10원: 최대 200개 (n₄ = N//10)
최종 시간 복잡도: O(N^4)

 

작성 코드 비교

그리디 알고리즘 풀이

import java.util.*;

public class Solution {
    public static int coinChange(int[] coins, int target) {
        // 1. 초기화 단계
        // 1.1. 동전을 큰 단위부터 작은 단위 순으로 정렬
        Arrays.sort(coins);

        // 1.2. 거스름돈 금액을 저장할 변수 초기화
        int remainingAmount = target;
        // 1.3. 사용된 동전 개수를 저장할 변수 초기화
        int coinCount = 0;

        // 2. 큰 동전부터 사용하는 단계
        // 2.1. 가장 큰 단위의 동전부터 순차적으로 진행
        for (int i=coins.length-1; i>=0; i--){
            // 2.2. 현재 동전으로 거스름돈을 최대한 많이 거슬러줌
            coinCount += remainingAmount / coins[i];  // 현재 동전으로 거슬러 줄 수 있는 개수
            remainingAmount %= coins[i];              // 남은 금액 계산
            // 2.3. 남은 거스름돈에 대해 다음으로 큰 동전으로 반복
        }

        // 3. 결과 반환 단계
        // 3.1. 사용된 동전 개수 반환
        return coinCount;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] coins = {500, 100, 50, 10};

        // 거스름돈 금액 입력 받기
        int target = scanner.nextInt();

        // 결과 출력
        System.out.println(coinChange(coins, target));
    }
}

 

완전 탐색 풀이

public static int coinChange(int[] coins, int target) {
    // 1. 초기화 단계
    // 1.1. 각 동전 별로 사용 가능한 최대 개수 계산
    //      - 목표 금액 / 동전 금액 = 최대 사용 가능 개수
    int[] maxCounts = new int[coins.length];
    for (int i = 0; i < coins.length; i++) {
        maxCounts[i] = target / coins[i];
    }

    // 1.2. 최소 동전 개수를 저장할 변수를 최댓값으로 초기화
    int minCoins = Integer.MAX_VALUE;

    // 2. 모든 조합 시도 단계 (4중 for문 사용)
    // 2.1. 500원: 0개부터 최대 개수까지 반복
    for (int i = 0; i <= maxCounts[0]; i++) {
        // 2.2. 100원: 0개부터 최대 개수까지 반복
        for (int j = 0; j <= maxCounts[1]; j++) {
            // 2.3. 50원: 0개부터 최대 개수까지 반복
            for (int k = 0; k <= maxCounts[2]; k++) {
                // 2.4. 10원: 0개부터 최대 개수까지 반복
                for (int l = 0; l <= maxCounts[3]; l++) {
                    // 각 조합에 대해:
                    // - 현재 조합으로 만들어지는 총 금액 계산
                    int currentSum = (coins[0] * i) + (coins[1] * j) +
                            (coins[2] * k) + (coins[3] * l);

                    // - 목표 금액과 일치하는지 확인
                    if (currentSum == target) {
                        // - 일치하면 사용된 동전 개수(현재 4중 for문의 각 인덱스 합)와 
                        //   현재 최소값 비교하여 갱신
                        minCoins = Math.min(minCoins, i + j + k + l);
                    }
                }
            }
        }
    }

    // 3. 결과 반환 단계
    // 3.1. 찾은 최소 동전 개수 반환
    // 3.2. 해를 찾지 못한 경우 -1 반환
    return minCoins == Integer.MAX_VALUE ? -1 : minCoins;
}

 

💡이와 같이 동일한 문제를 풀어 나아가는 과정에서도 적합한 알고리즘을 선택하고 적용하여 풀어 나아가는 연습을 꾸준히 해야할 필요가 있다고 느꼈다.

 

다음 포스팅부터는 다양한 알고리즘 문제풀이 플랫폼을 활용하여 실습과제를 진행해 나아가볼 수 있도록 하겠다!