재훈맨

Java/Spring Boot 백엔드 개발자

3 분 소요

흔히 탐욕 알고리즘이라고도 불리는 그리디 알고리즘은, 문제 해결을 위해 각 단계에서 최적의 선택을 하는 알고리즘 설계 방법이다.

최적의 선택을 하는 알고리즘 중 동적 계획법 보다 구현이 쉽고, 시간 복잡도가 우수하다는 장점이 있지만,항상 최적의 해를 보장하지 못한다는 단점도 있다.

그렇기 때문에 논리 유무를 충분히 확인한 후 사용해도 되는지 판단해야한다.

보통 최단 경로, 최소 신장 트리(Minimum Spanning Tree) 등에 활용할 수 있다.

핵심 이론 / 수행 과정

  1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
  2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
  3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지를 검사한다. 전체 문제를 해결하지 못한다면 위의 과정을 반복한다.

그리디 알고리즘의 개념을 익히는데 자주 등장하는 “동전 개수 구하기” 의 문제를 풀며 개념을 익혀보자.

https://www.acmicpc.net/problem/11047

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  
  
public class Main {  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
  
        StringTokenizer st = new StringTokenizer(br.readLine());  
  
        // 동전 개수  
        int N = Integer.parseInt(st.nextToken());  
  
        // 목표 값  
        int K = Integer.parseInt(st.nextToken());  
  
        // 동전 배열  
        int[] A = new int[N];  
  
        // 동전 값 저장하기
        for(int i = 0; i<N; i++){  
            st = new StringTokenizer(br.readLine());  
  
            A[i] = Integer.parseInt(st.nextToken());  
        }  
  
        // 사용한 동전 개수  
        int count = 0;  
  
        // 오름차순이기에 뒤에서 부터 순회하며 기준에 맞는 큰 값을 찾는다.  
        for(int i = N -1; i>=0 ; i--){  
            //현재 동전  
            int coin = A[i];  
  
            // 동전의 값이 K와 같거나 작다면 적합한 동전  
            if(coin <= K){  
                count += K / coin; // 해당 동전을 사용하는 만큼 count를 더해준다.  
  
                K = K % coin; // 동전을 사용하고 나머지 금액을 넣어준다.  
            }  
        }   
        System.out.println(count);  
    }  
}

그리드의 내용이 길지 않으니 핵심 알고리즘을 활용하는 문제를 하나 더 풀어보자.

https://www.acmicpc.net/problem/1541

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        int answer = 0;

        Scanner sc = new Scanner(System.in);

        // 가장 작은 값을 구하기 위해서는 -를 기준으로 나눠서 다음 -까지의 값들을 더해준다.(일종의 괄호)
        String[] given_split = sc.nextLine().split("-");
        
        for(int i = 0; i < given_split.length; i++){
            // 구분된 값들을 모두 더한다.
            int tmp = mySum(given_split[i]);

            // 첫 번쨰 값이라면 값을 뺴는 기준값이 된다.
            if(i == 0){
                answer += tmp;
            }else{
                answer -= tmp;
            }
        }

        System.out.println(answer);
    }

    static private int mySum(String plus) {
        int sum = 0;

        // "+" 를 기준으로 자른다.
        // split은 regex로 인식하기에 "+"만 작성하면 인식되지 않는다.
        String[] plus_split = plus.split("[+]");

        // 모든 값들을 괄호와 같은 개념으로 더한다.
        for(int i = 0; i < plus_split.length; i++){
            sum += Integer.parseInt(plus_split[i]);
        }
        return sum;
    }
}


Ref.

Do it! 알고리즘 코딩 테스트 - 자바 편, 이지스퍼블리싱/김종관 저

참고