글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘
(코딩 테스트에서의 정의를 의미하는듯? -> 항상 글로벌 최적을 찾기는 어려울 듯)
그리디 알고리즘
드물게 최적해를 보장하는 경우도 있음
보통 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼음
최적해를 찾을 수 있는 두 가지 조건
탐욕 선택 속성 (Greedy Choice Property) - 앞의 선택이 이후 선택에 영향을 주지 않음 - 즉, 문제 해결 과정 중 substructure마다 독립적인 문제 해결
최적 부분 구조 (Optimal Substructure) - 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우 - 즉, substructure에서 구한 optimum이 global optimum으로 진행되는 것을 의미
다이나믹 프로그래밍과 비교
서로 풀 수 있는 문제의 성격과 알고리즘 접근 방식 모두 다름
다이나믹 프로그래밍은 substructure에서 찾은 optimum을 모두 종합하여 global optimum을 찾음
그리디 알고리즘은 substructure마다 optimum을 찾아 문제의 크기를 줄여나감
배낭 문제
정의 - 배낭에 담을 수 있는 무게의 최대값이 주어짐 - 각 짐의 가치와 무게가 주어짐 - 제한된 무게에 맞게 짐을 담아 가치의 최대값 도출하는 문제
종류 - 짐을 분할할 수 있는 분할 가능 배낭 문제(Fractional Knapsack Problem) - 짐을 분할할 수 없는 0-1 배낭 문제
그리디 알고리즘 - 분할 가능 배낭 문제만 풀이 가능 (0-1 배낭 문제는 다이나믹 프로그래밍) - 1kg당 가치를 계산하여, 가치가 큰 짐부터 담는 방식
동전 바꾸기 문제
정의 - 여러 종류의 동전(10원/50원/100원 등)을 최소로 사용하여 정해진 금액 만들기
조건 - 동전의 액면이 10원, 50원, 100원처럼 "이전 액면의 배수 이상"일 경우 그리디 알고리즘 적용 가능 - 각 액면이 2배 이상인 경우, 2개 이상 사용될 동전을 1개로 줄일 수 있기 때문에 그리디 알고리즘이 적용 가능함(최적 부분 구조) - 80원이 추가될 경우, 다이나믹 프로그래밍 사용 - ex) 160원을 구하는 방식에서 80원이 2개로 최소
가장 큰 합
정의 - 그리디 알고리즘이 사용될 수 없는 사례 - 정렬되지 않은 이진트리에 대해 누적합의 최대가 되도록 child를 선택하는 문제
그리디 알고리즘 - 더 작은 child의 subtree에 더 큰 수가 존재할 경우 - ex) 7 - 3 - 12- 99 -8 - 5 - 6 - 3과 12중 12를 선택하여, 99에 도달하지 않음 - substructure의 optimum이 global optimum으로 이어지지 않으므로, 최적 부분 구조를 만족하지 않음
