[C++ Algorithm] Ch5. 그리디 알고리즘

5.1 들어가며

그리디 알고리즘

미래를 내다 보지 않고 당장 눈 앞에 보이는 최적의 선택을 하는 방식

• Greedy Algorithm -> 탐욕스러운 알고리즘

5.2 기본적인 그리디 알고리즘

최단 작업 우선 스케줄링

일 처리 시간이 가장 적게 걸리는 작업을 우선적으로 배치

• 예) 은행에서 하나의 창구에서 여러 손님을 받을 때, 일 처리 시간이 적게 걸리는 손님부터 처리 -> 평균 대기 시간의 감소

5.3 배낭 문제

일반 배낭 문제

물건들의 집합 O = { O1, O2, … On }가 있고, 각각의 가격은 Vn, 무게는 Wn이다. 최대 무게를 T까지 견딜 수 있는 가방이 하나 주어진다. 물건들을 가방에 담아야 하는데, 물건들의 무게의 총 합이 T를 넘지 않고 가방에 넣은 물건들의 합이 최대가 되도록 물건을 담아야 한다. 어떻게 물건을 선택할 것인가?

[Solution]

• NP-완전 문제
• 다항 시간 솔루션은 주어져 있지 않음
• 최선의 물건 조합을 찾으려면 모든 가능한 물건 조합 목록을 만들고 그 중 가격이 최대인 조합을 찾아야 함

분할 가능 배낭 문제

일반 배낭 문제에서 주어진 물건을 원하는 형태로 얼마든지 분할할 수 있고, 각 물건의 일부분만 배낭에 넣을 수 있음

[Solution]

• 단위 무게당 가격(가격/무게)을 구하고 가격이 가장 높은 물건 순서대로 선택