그리디 알고리즘

그리디 알고리즘이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지는 알고리즘 설계 기법이다. 그리디 알고리즘은 매 선택이 그 순간에 대해서는 최적이지만, 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 

사용되는 알고리즘문제에는 거스름돈 문제, minimum spanning tree, 다익스트라 알고리즘, 허프만 코딩 등이 있습니다.

그리디 알고리즘 중 가장 많이 사용되는 거스름돈 문제에서 동전 단위가 달라져 버리면, 최적의 조건을 구하기 어려워지는데, 이럴 때는 다이나믹 알고리즘을 사용해야 합니다. 그리디 알고리즘을 풀기 위해서는 '정렬' 이 필수입니다. 매 순간 최적(최저) 조건을 만족하기 위해서는 정렬이 당연히 필수겠죠? 

그리디 알고리즘을 풀기 위하여 백준 2875번 문제를 풀어보았는데, 여기서는 정렬이 사용되지 않았다. 내가 구현한 알고리즘을 간략하게 설명하자면, 최대로 팀을 많이 구성해야 하기 때문에 주어진 남, 녀 조건에서 구성할 수 있는 1) 팀의 최대를 구한 후, 2) 남은 사람을 인턴에 배정하고 3) 부족할 때마다 팀을 하나씩 해체해서 인턴 요원으로 보충하는 형식의 알고리즘을 구현하였다. 

위키피디아에서 나온대로 정렬이 들어가진 않았지만, 이 문제에서의 정렬은 남, 녀의 조합을 맞추어서 팀의 최대를 구하는게 정렬이아닐까 싶다. 즉, '정렬'의 단어는 그리디 알고리즘에서 그때 그때 달라지는게 아닌가 싶다. 그리디 알고리즘은 현재에서 최적의 답을 선택하는 것이기 때문에 항상 답을 도출하는게 아니어서 이미 잘 알려진 그리디 알고리즘 문제가 아니라면, 숙고해서 사용해야 하는 알고리즘인 것 같다.

코드

import java.util.Scanner;
public class Main {
    static int count=0;
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        int women = scan.nextInt();
        int men = scan.nextInt();
        int internStudent = scan.nextInt();

        int team =0;
        boolean flag = true;


        while(flag){

            flag = false;
            if(women>=2){
                women-=2;
            }else{
                break;
            }
            if(men>=1){
                men-=1;
            }else{
                break;
            }
            team++;
            flag = true;
        }

        int leftWomen = women;
        int leftMen = men;

        while(true) {

            int temp = leftWomen + leftMen;
            if (temp < internStudent) {
                team -= 1;
                leftWomen += 2;
                leftMen += 1;

            }else{
                break;
            }
        }
        System.out.println(team);
    }

}