[JAVA / 알고리즘] - 그리디 알고리즘

그리디 알고리즘 (Greedy Algorithm)

매 순간 현재 기준으로 가장 좋은 답을 선택해 나가는 기법으로 근사치에 빠르게 접근할 수는 있지만, 결과적으로는 최적해가 아닐 수도 있다.

다만, 하기와 같은 조건일 때 그리디 알고리즘으로 최적해를 구할 수 있다.

① 탐욕적 선택 특성 (Greedy choice property)

    지금 선택이 다음 선택에 있어서 영향을 주지 않는 경우

② 최적 부분 구조 (Optimal substructure)

    전체 문제의 최적해는 부분 문제의 최적해로 이루어지는 경우