그리디(Greedy) 알고리즘 (탐욕 알고리즘)

그리디(Greedy) 알고리즘 (탐욕 알고리즘)

참고 사이트 :

1. https://www.geeksforgeeks.org/greedy-algorithms/

2. https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

---

그리디 알고리즘

• 매 순간마다 최적의 값을 찾음
• 매 순간의 최적값을 모두 더한것이 전체의 최적값이길 바람
• 결과값이 항상 최적값이라고 보장할 수 없음
• 탐욕스러운 선택 조건, 최적 부분 구조 조건이 만족해야만 최적해를 구할 수 있음
  탐욕스러운 선택 조건 : 앞서 선택한 것이 이후의 선택에 영향을 미치지 않음
  최적 부분 구조 조건 : 문제에 대한 최적해가 부분 문제에 대해서도 최적해가 됨
• 조건이 만족하지 않으면 최적해를 구할 수 없지만, 근사 알고리즘으로 사용가능하며(근사값) 계산속도가 빨라 실용적으로 사용 가능
• 그리디가 적용된 알고리즘 종류
  1) 크루스칼 알고리즘
  2) 프림 알고리즘
  3) 다익스트라 알고리즘
  4) 허프만 코딩 등...

 

 

예시) 활동 선택 문제

시작 및 종료 시간이 주어지며, 한 사람이 한 번에 하나의 활동만 수행할 수 있다고 가정했을 때 한 사람이 할 수 있는 최대 활동의 개수 구하기 시작시간 : [1, 3, 5, 7, 9, 13] 종료시간 : [4, 5, 7, 9, 12, 15] 최대 활동 개수 : 5개 [1~4, 5~7, 7~9, 9~12, 13~15]

활동 선택 문제 풀이

package Greedy;

public class ActivitySelectionProblem {
    public static void main(String[] args) {
        int[] start = {1, 3, 5, 7, 9, 13};
        int[] finish = {4, 5, 7, 9, 12, 15};
        // 활동 개수
        int n = start.length;
        int i=0;
        int count=0;

        // 다음 활동 시작 시간이 이전 활동의 끝나는 시간보다 클 경우를 구해야 하므로 j=1
        for(int j=1; j<n; j++){
            if (start[j] >= finish[i]){
                System.out.println(String.format("%d~%d", start[i], finish[i]));
                i = j;
                count++;
            }
        }
        // 마지막 시간은 반복문에서 제외됨
        if (start[i] >= finish[i-1]){
            System.out.println(String.format("%d~%d", start[i], finish[i]));
            count+=1;
        }

        System.out.println("최대 활동 개수 : " + count);
    }
}

 

작성예정...