그리디 알고리즘?
그리디 알고리즘은 현재 주어진 상황에서 할 수 있는 최선의 선택하는 알고리즘이다.
물론 현재 상황의 최적의 해가 전체 문제의 최적의 해가 되는 것은 보장할 수 없다.
그러므로, 그리디 알고리즘은 한정된 문제에서만 사용할 수 있다.
각 선택에서 전의 선택이 후의 선택에 영향을 미치지 않는 경우에 사용하는 것이 좋다.
그리디 알고리즘 문제
- Fractional Knapsack Problem(각 물건을 쪼갤 수 있는 경우)
ex) 배낭에 담을 수 있는 최대 무게는 정해져 있고, 가치와 무게가 각각 다른 물건들을 배낭에 담을 때, 가치의 총 합이 최대가 되도록 하기- Interval Scheduling Problem
ex) 정해진 시간동안 한 강의실에서 최대한 많은 강의 배정하기- Interval Partitioning
ex) 강의실을 최소한으로 사용하여 모든 강의 배정하기- 허프만 인코딩 - 가변길이 인코딩
1. Fractional Knapsack Problem
가치와 무겍가 다른 N개의 물건이 있고, 최대 M무게까지 담을 수 있는 배낭 한개가 있다. 이때, 가치의 합이 가장 크게 물건을 담는 알고리즘 (물건을 쪼갤 수 있다.)
1-알고리즘
- 무게당 값어치가 큰 물건 순으로 정렬한다.
- 가방에 정렬된 순서대로 담다가, 더이상 들어가지 않고, 가방에 무게가 남았을 때에는 다음에 넣을 물건에 (가방에 남은 무게 수 / 물건의 무게)를 곱해 쪼개어 가방에 넣어준다.
**Knapsack Problem은 쪼갤 수 없는 경우(0-1 Knapsack Problem) 다이나믹 프로그래밍을 이용해야 한다.
2. Interval Scheduling Problem
어떤 일들을 수행시간이 겹치지 않게 배정하여 정해진 시간동안 최대한 많은 일을 하도록 스케쥴링 하는 알고리즘
2-알고리즘
현재 작업 set에서 가장 끝나는 시간이 빠른 작업을 먼저 고른다.
1. 모든 작업들을 완료시간이 빠른 순서로 정렬한다.
2. 정렬된 순서로 작업을 선택한다.
3. 이전에 선택한 작업 다음에 선택할 작업의 수행시간이 겹치는지 확인하고 겹치지 않으면 추가한다. -> 이 과정 반복
3. Interval Partitioning
강의의 시간과 강의실이 겹치지 않도록 하여 최소한의 강의실에 모든 강의를 배정하는 알고리즘
3-알고리즘
- 강의를 시작시간이 빠른 순서대로 정렬한다.
- Prioirty Queue를 이용하여 이전 수업이 가장 빨리 끝나는 강의실에 다음 강의를 배치한다. 만약 해당 강의실에 강의가 들어갈 수 없다면, 강의실을 하나 더 만든다.
4. Huffman Incoding
문자열을 이진 데이터로 인코딩하는 효율적인 방법. 가변길이 인코딩
4- 알고리즘
- 문자열의 각 문자가 몇번씩 나오는지 count하여 저장한다.
- 우선순위 큐에 최소 힙으로 문자와 그 문자가 몇번 나왔는지 저장한다.
- 우선순위 큐에서 두번 pop 하여 두 문자의 count의 합을 루트로 하는 허프만 트리를 만든다. -> 이 과정 반복
- 허프만 트리에서 왼쪽 가지는 0, 오른쪽 가지는 1을 적용해 리프노드(원래 문자)까지 나오는 0과1로 이루어진 이진 데이터를 저장한다. (인코딩)
허프만 인코딩 보러가기 -> 허프만 인코딩
Record What I Learned