[Java] Greedy algorithm

1. Greedy algorithm

 

• 문제 상황
  : 최적해를 구하기 위해서 사용되는 근사적인 방법. (보통 최대 또는 최소를 구한다.)
• 원리
  : 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
• 한계
  : 각 선택 시점에서 이루어지는 결정은 지역적으로 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었을 때, 그것이 반드시 최적이라고 보장할 수 없다.
  : 대부분의 그리디 알고리즘은 몇몇 단순하고 제한된 문제에 적용된다.
• 필수 조건
  : 원문제의 최적해 = 탐욕적 선택 속성 + 최적 부분 구조
  : 탐욕적 선택이 최적해로 이어진다는 것을 증명해야 한다. (탐욕적 선택 속성)
  : 하나의 선택을 풀면 하나의 하위 문제가 남는다. (최적 부분 구조)

 

---

2. knapsack

 

12865번: 평범한 배낭

• 문제 상황
  : 주어진 조건을 만족하는 최적화된 부분집합을 구하는 문제.

 

---

가. 종류

 

• 0-1 knapsack
  • 물건을 쪼갤 수 없는 경우
  • 완전탐색, DP
• Fractional Knapsack
  • 물건을 부분적으로 담는 것이 허용되는 문제
  • 그리디, 완전탐색, DP

 

---

3. Activity-Selection Problem

 

1931번: 회의실 배정

• 활동 선택 문제
• 문제 상황
  : 시작시간과 종료시간을 가진 활동들 있을 때 서로 겹치지 않는 선에서 최대한 많은 활동을 수행하는 방법.
  : 양립 가능한 활동들의 크기가 최대가 되는 부분집합을 선택하는 문제
• 원리
  : 종료 시간 순으로 활동들을 정렬한다. ← O(NlogN)

 

---

가. 문제

 

• 회의실 선택

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

    static class Meeting implements Comparable<Meeting> {
        int start, end;

        Meeting (int start, int end){
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Meeting o) {
            return this.end != o.end ? this.end - o.end : this.start - o.start;
        }

        @Override
        public String toString() {
            return "start : " + this.start + " end : " + this.end;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        Meeting[] meetings = new Meeting[N];

        for(int i=0; i<N; i++) {
            meetings[i] = new Meeting(sc.nextInt(), sc.nextInt());
        }

        Arrays.sort(meetings);

        List<Meeting> list = new ArrayList<>();
        list.add(meetings[0]);
        for(int j=1; j<N; j++) {
            if(list.get(list.size()-1).end <= meetings[j].start) {
                list.add(meetings[j]);
            }
        }

        System.out.println(list.size());
        //for(Meeting meeting : list) {
        //    System.out.println(meeting);
        //}
        sc.close();
    }

}

 

---

4. 동전 자판기

 

JUNGOL

• 문제 상황
  : 주어진 조건을 만족하는 최적화된 부분집합을 구하는 문제.

 

---

5. 그 외

 

알고리즘	문제 상황	원리
슬라이딩 윈도우	주어진 자료구조의 일정 구간을 순차적으로 이동하면서 연산을 수행할 때.	윈도우를 한 칸씩 이동시키면서 새로운 요소를 추가하고, 이전 요소를 제거하여 부분 문제를 해결한다.
Prim	N 개의 노드에 대한 최소 신장 트리(MST)를 찾는다.	서브트리를 확장하면서 MST를 찾는다.
Kruskal	N 개의 노드에 대한 최소 신장 트리(MST)를 찾는다.	싸이클이 없는 서브 그래프를 확장하면서 MST를 찾는다.
Dijkstra	주어진 정점에서 다른 정점들에 대한 최단 경로를 찾는다.	주어진 정점에서 가장 가까운 정점을 찾고, 그 다음을 정점을 반복해서 찾는다.

 

추후에 하나씩 따로 다룰 예정.

 

---