그리디 알고리즘은 그 순간에 최선의 선택을 항상 하는 것을 의미한다.
- 목표는 지역적인 최적의 선택이 전체 최적의 선택으로 이어지는 것
- 항상 최적의 답을 도출하는 것은 아니다.
Activity Selection 스케쥴링문제
- Activity : a1, a2, … , an → [starttime i, finish time i) 반열림 구간
- 목표 : 중복되지 않게 최대한 가능한 활동들의 집합(순서)을 구해라!
- 완료될 수 있는 활동들의 최대 수는 몇일까?
-
Optimal Substructure of AS Problem
- Sij 라는 집합을 정의 : 중복되지않게**(전꺼의 finish time이 뒤에꺼의 start time보다 작음)**
- finish time을 단순하게 증가하는 순서로 정렬 (f0가 가장 낮음)
- i < j 인 조건도 도출해냄
- Sik / Skj 하위문제들로 나눠서 풀어보자
-
Sij의 최적의 답에 ak가 포함이 되어있다면, 그 말은 즉슨 Sik와 Skj도 최적의 답이 되어야한다.
- Sij의 최적의 답을 Aij라고 하면
-
c[i, j] : Sij에서 중복되지 않게 최대한 배정할 수 있는 활동들 집합의 크기
- max함수를 이용해서 구현할 수 있
- 선택의 기준
- 가장 빨리 끝나는 활동 선택, 활동이 끝난 시점에서 선택할 수 없는 활동 제거 → 반복
- 실제 예시 (초기 상태에서 i = 1이라 a3보다 먼저 스케쥴링 된 거 같음)
- 최종 결과 (빨간색이 선택됨, 살색이 제거된 애들)
-
Resurive 재귀적 방법 pseudocode
- 반복문 방법 pseudocode
- 둘다 Θ(n) but sorting이 O(nlogn)
Greedy choice 특징
- 지역적 최적의 선택이 궁극적으로 전체의 최적의 답을 도출해낸다.
- 동적프로그래밍과의 공통점과 차이점
- 동적프로그래밍
- 각 단계에서 선택을 한다.
- 선택이 하위 문제에 대한 최적의 답을 아는 것에 달려있다.
- 하위 문제를 먼저 해결한다.
- bottom up 방식
- 그리디 알고리즘
- 각 단계에서 선택을 한다.
- 하위 문제를 해결하기 전에 선택한다.
- top down 방식
- 동적프로그래밍
Knapsack 문제 (배낭 문제, 배낭에 어떤 물건을 담을까?)
- 0-1 knapsack 문제 : 그리디알고리즘으로는 해결할 수 없다 → 이유는 뒤에서
- 총 무게가 w이하가 되도록 물건을 가져가는 것
- 물건을 가져가든지 말든지 둘 중 하나의 선택지 → 물건의 일부분만 가져갈수없다.
- Fractional knapsack 문제 : 그리디로 해결 가능
- 0-1 문제와 기본적인 것은 같고, 물건을 비율적으로 가져갈 수 있다.
- 비율배낭문제를 해결하기 위해서는 새로운 변수 도입이 필요함
- rank = value / weight
- rank가 높은 순서대로 가져감
- 둘의 차이를 예시로!
- W가 50이라고 할 때 0-1 배낭 문제는 2,3번의 아이템을 가져갈 것이다. → v = 220
- 비율배낭 문제는 1,2번을 택하고 3번을 비율적으로 택할 것이다. → v = 160 + 80 = 240
동적프로그래밍으로 이 문제를 테이블화 시켜보자
- P(i,w) = 1번째부터 i번째까지 아이템중에서 얻었을 때, 이득의 maximum(선택후배낭무게 = w)
- 두가지로 나뉠 것이다. i번째 아이템을 선택하느냐 아니냐
- 그래서 이 두가지 경우 중 max값을 저장하는 것이다.
- P(3,4)를 해석해보자. 현재 배낭의 무게가 4고 1~3번째 아이템 중에 3번아이템을 고름 + 3번아이템의 value = 20 , weight = 3 → 20 + P(2,1) / 고르지 않았을때 P(2,4) 둘 중 큰 값이 됨 → 30
- 실제 계산
- 골랐어 → 좌상단으로 / 안골랐어 → 위로
- 위로 올라가도 값의 변화가 없을 때 안고른 것이다!
- 화살표가 없다면 갈 수 있는 길이 아니다!
- item 4 → item 3 no! → item2 → item1 (최적의 답)
- 골랐어 → 좌상단으로 / 안골랐어 → 위로
-
Pseudocode
