인프런 커뮤니티 질문&답변
작성한 질문수
이분탐색(결정알고리즘) & 그리디 알고리즘 카테고리 타이타닉문제 질문있습니다
해결된 질문
작성
·
148
0
그리디 알고리즘에 대해 궁금한데요
문제를 간소화해서 설명하겠습니다.
무게제한:140
승객무게: 100 90 80 70 60 50 40 30 20 10이 있다고 가정. (sort되있음)
강사님이 설명하신게 최대값과 최소값 즉, 100과 10을 짝지어서 제거한다고했는데
최선의 결과는 100과 40을 짝지어서 보내는거잖아요?
그래서 찾아보니 그리디 알고리즘은 최선의 결과가 나오지는 않는다고 하더군요.
여기서 헷갈리는게 그럼 그리디 알고리즘은 코딩문제에는 적합하지 않나요?
문제에는 항상 답이 있고 이 답을 찾아야 하는데 최선의 결과를 도출하지 못하는 그리디 알고리즘은 적합하지 않을 수도 있다는 생각이 들어서 질문합니다.
답변 1
1
안녕하세요^^
그리디가 모든 문제에 정확한 답을 내는 것은 아니지만 문제에 따라 그리디가 정확한 답을 내는 문제들이 있습니다. 이 문제도 그리디로 정확한 답을 내는 문제입니다. 그런 문제를 알아본다는게 쉬운일이 아닙니다만, 많은 문제를 풀다보면 이 문제가 그리디로 되는지 아니면 다이나믹으로 해야만 되는지 판별할 수 있게 됩니다.
위에 예를 들면서 100과 40이 100과 10을 짝지은 것보다 더 좋으니 그리디로 풀 수 없는 문제가 아닌가 하는 의문이 드신것 같은데,
위와 같은 의문이 합리적인 의문이 되려면 100과 10을 태워 보내는 것보다 100과 40을 태워 보냈을 때 최종적으로는 보트개수가 적게 사용된다는 것을 예를 들어서 보여주어야 합니다.
그래야 100과 40을 짝지은게 100과 10을 짝지은 것보다 더 최선의 방법이라고 말 할 수 있는 것입니다.
100과 10을 짝짓는 방법은 현재 남아 있는 사람 중 가장 무거운 사람 한 명을 보트에 태울 때 이 가장 무거운 사람과 누구를 짝지어야 보트에 2명을 태울 수 있을까? 라는 고민에서 최적이 가장 가벼운 사람이 최선이다 라는 방법입니다.
사실 그리디 해법이 증명하기가 힘듭니다. 그냥 그렇게 풀어보고 반례가 없는지 체크해본 다음에 대략 없겠다 싶으면 채점기에 넣어보는 겁니다. 사실 부끄럽지만 저도 그렇게 하고 있는 수준입니다.
감사합니다 강사님 :)