탐욕 알고리즘(Greedy Algorithm)

Algorithm : 탐욕 알고리즘(Greedy Algorithm)

: 미리 정한 기준에 따라서 매번 가장 좋아보이는 답을 선택하는 알고리즘으로, 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법이다. 각 단계에서 최선의 선택이 전체적으로도 최선이길 바라는 알고리즘

 

탐욕 알고리즘의 예시

활동 선택 문제(Activity Selection problem)

한 사람이 하나의 활동에 대해서만 작업할 수 있을 때 최대한 많은 활동을 할 수 있는 수를 선택하는 문제로 하나의 활동을 선택하면 나머지 겹치지 않는 활동에 대해서 독립적이다.

 

활동 선택 문제 코드

출처 : 1931번: 회의실 배정 (acmicpc.net)

1931번: 회의실 배정

 

import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.Comparator;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
	public static void main(String[] args) throws IOException {
	    
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    
	    int n = Integer.parseInt(br.readLine());
	    int[][] meetingroom = new int[n][2];
        
        StringTokenizer st;
	    
	    for(int i = 0; i < n; i++) {
	        
	        st = new StringTokenizer(br.readLine(), " ");
	        meetingroom[i][0] = Integer.parseInt(st.nextToken());
	        meetingroom[i][1] = Integer.parseInt(st.nextToken());
	        
	    }
	    
	    Arrays.sort(meetingroom, new Comparator<> () {
	    	@Override
	    	public int compare(int[] a1, int[] a2) {
	    		if(a1[1] == a2[1]) { // 끝나는 시간이 같으면
	    			return a1[0] - a2[0]; // 시작이 빠른 순서로
	    		}
	    		return a1[1] - a2[1]; // 그 외에는 끝나는 시간이 빠른 순서대로 정렬
	    	}
	    });
	    
	    int count = 0;
	    int prev_end_time = 0;
	    
	    for (int i = 0; i < n; i++) {
	    	// 이전 회의의 종료 시간이 i번째 회의의 시작 시간보다 빠르면
	    	if(prev_end_time <= meetingroom[i][0]) {
	    		prev_end_time = meetingroom[i][1];
                count++;
                // 이 회의를 넣고, prev_end_time을 i번째 회의의 종료 시간으로 갱신
	    	}
	    	
	    }
	    	
	    System.out.println(count);
	    
	}
}

[백준] 1931번 : 회의실배정 - JAVA [자바]

 

분할 가능 배낭 문제(Fractional Knapsack Problem)

한 가방에 넣을 수 있는 무게의 최대 값이 정해져 있을 때, 일정한 가치와 무게가 있는 물건들을 가치의 합이 최대가 되도록 가방에 넣는 방법을 찾는 문제이다. 물건을 쪼갤 수 있다는 가정 하에서는 무게 대비 가치가 높은 것들을 먼저 넣는 게 좋다.

 

---

 

탐욕 알고리즘 참고 사이트

• 알고리즘 - 배낭문제 (Knapsack Problem)
• [알고리즘] Greedy Algorithm (탐욕 알고리즘) (tistory.com)
• (Algorithm) 탐욕(그리디) 알고리즘(greedy algorithm) - 활동 선택 문제, 분할 가능 배낭 문제 - ZeroCho Blog