인프런 커뮤니티 질문&답변

안녕하세요, 인프런 AI 인턴입니다. Dompoo님.

그리디 알고리즘은 모든 경우에 항상 올바른 해답을 보장하지는 않습니다. 당신이 제시한 예시는 그리디 알고리즘이 실패할 수 있는 경우 중 하나입니다. 그리디 알고리즘은 즉각적으로 최선으로 보이는 선택을 하고, 이러한 방식이 전반적으로 최적의 해를 보장할 수 있는 문제에 적합합니다. 하지만, 그것이 항상 전체 최적 해를 제공하는 것은 아닙니다.

씨름 선수 문제에 대한 해결 방법으로는 보통 두 가지 접근법을 생각할 수 있습니다. 하나는 말씀하신 sort한 후 ‘키의 내림차순’과 ‘몸무게의 오름차순’으로 가장 긴 기저열을 찾는 과정이고, 이는 보통 최적 해법으로 간주됩니다.

해당 문제의 그리디 알고리즘 접근 방식은 보통 다음과 같이 이루어집니다:
1. 모든 지원자를 키 기준으로 내림차순 정렬합니다.
2. 이후 몸무게를 기준으로 선택하며, 이전까지 선택한 선수들보다 몸무게가 더 나가는 경우 선발합니다.

당신이 말씀하신 “최장으로 길어질 수 있는 무게 오름차순 순열”은 다이나믹 프로그래밍이나 특수한 탐색 기법에서 유리한 경우가 많습니다. 이 경우엔 그리디보다는 Dynamic Programming을 이용한 해법이 더 적합할 수도 있습니다.

기존의 문제를 해결할 수 있는 유사한 예제 보기는 아래의 링크에서 확인하실 수 있습니다:

• 씨름 선수 문제에서 그리디 알고리즘의 한계
  

위 링크에서는 그리디로 푸는 과정에서의 이슈와 더 나은 접근법에 대한 토론이 이루어지고 있습니다. 도움이 되실 겁니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.