-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
그리디 방법
21.02.04 22:28 작성 조회수 138
0
강사님!!
그리디방법은 가장 좋은 방법으로 문제를 풀어나가는 것이잖아요?? 근데 제가 선택한 방법이 가장 좋은지 아닌지는 어떻게 판별할 수있나요?
저는 아래와같이 코드를 썼는데, 어떤 코드가 더 좋다고 말할 수 있는지 그 기준을 모르겠습니다!!!
people, limit_kg=map(int, input().split())
weight=list(map(int, input().split()))
cnt=0
sum=0
weight.sort()
for i in weight:
if sum+i>limit_kg:
cnt+=1
sum=i
else:
sum+=i
print(cnt)
답변을 작성해보세요.
0
김태원
지식공유자2021.02.05
안녕하세요^^
일단 채점을 해보세요. 0점 나오는 코드입니다.
그리디는 매 단계마다 그 시점에서 가장 좋은 선택을 하면서 문제를 해결하는 방법입니다. 그런데 현재 단계에서의 최선의 선택이 그 다음 단계에서는 더 나쁜 결과를 초래하기도 하죠. 그래서 그리디는 증명이 힘든 알고리즘입니다.
그리디를 이론적으로 증명하기란 정말 어렵습니다. 실전에서는 내가 생각한 그리디방법이 반례가 없는지 반례를 만들어 가면서 확인해 보는게 현실적인 방법입니다. 위에 코드도 스스로 반례를 만들어 확인해 보세요.
일단 그리디가 되는 방법을 찾았다면 그걸로 대단한 것입니다. 한 문제에 그리디 방법이 여러개인 경우는 별로 없습니다. 여러개라고해도 효율성의 차이는 없습니다.
답변 1