목록탐욕법 (1)

문홍의 공부장

[Java] 프로그래머스 Lv1. 체육복 풀이 (탐욕법 알고리즘 Greedy Algorithm)

그리디 알고리즘 그리디 알고리즘(탐욕 알고리즘)은. 다음 단계를 생각하지 않고, 각 단계에서 가장 좋다고 생각하는 것을 선택하는 기법이다. 간단하게 아래 예시를 살펴보자. (출처: https://gomguard.tistory.com/119) 각 단계에서의 값을 더해 최대값을 구하는 문제에서, 최적해는 초록 라인을 따라가서 얻는 107이지만, 그리디 알고리즘을 이용할 경우 7보다 큰 13을 선택하고, 5와 11 중 11을 선택하여 최종적으로 24라는 값을 얻게 된다. 즉, 그리디 알고리즘이 최적해를 보장해주지는 않는다. 반드시 최적 해를 보장하지는 않지만, 그리디 알고리즘이 유효하게 먹히는 문제들이 몇몇 있다. 문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 ..
알고리즘/프로그래머스 2020. 1. 26. 19:38
이전 Prev 1 Next 다음