그리디 방법
226
작성한 질문수 3
강사님!!
그리디방법은 가장 좋은 방법으로 문제를 풀어나가는 것이잖아요?? 근데 제가 선택한 방법이 가장 좋은지 아닌지는 어떻게 판별할 수있나요?
저는 아래와같이 코드를 썼는데, 어떤 코드가 더 좋다고 말할 수 있는지 그 기준을 모르겠습니다!!!
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)답변 1
0
안녕하세요^^
일단 채점을 해보세요. 0점 나오는 코드입니다.
그리디는 매 단계마다 그 시점에서 가장 좋은 선택을 하면서 문제를 해결하는 방법입니다. 그런데 현재 단계에서의 최선의 선택이 그 다음 단계에서는 더 나쁜 결과를 초래하기도 하죠. 그래서 그리디는 증명이 힘든 알고리즘입니다.
그리디를 이론적으로 증명하기란 정말 어렵습니다. 실전에서는 내가 생각한 그리디방법이 반례가 없는지 반례를 만들어 가면서 확인해 보는게 현실적인 방법입니다. 위에 코드도 스스로 반례를 만들어 확인해 보세요.
일단 그리디가 되는 방법을 찾았다면 그걸로 대단한 것입니다. 한 문제에 그리디 방법이 여러개인 경우는 별로 없습니다. 여러개라고해도 효율성의 차이는 없습니다.
기존에 윈도우 10으로 잘 써왔는데 윈도우 11로 바꾸고 나서 채점이 안됩니다.
0
76
2
스택에서 ')'을 만나는 경우
0
78
3
문제가 어디있나요?
0
64
2
변수 or 함수명
0
61
1
침몰하는 타이타닉 문제 질문입니다
0
55
1
AA.py 책점 에러
0
57
1
오늘 구매했는데 파이썬 자료구조 궁금한거 있으면 답변이 잘 될까요.
0
111
2
5.동전분배하기 문제 밑에코드도 정답이될까요?
0
110
1
아나그램 비교 코드
0
116
2
AA.PY파일 복사 후 채점 진행할때 오류 발생합니다.
0
160
2
문제 링크가있나여?
0
147
2
채점기 Time Limit Exceeded 오류 문의
1
162
2
동적계획법은 사용하는 문제
0
126
2
제 코드 좀 봐주세요
0
147
1
예외가 존재할 가능성?
0
97
1
3번이 안풀립니다
0
93
0
5번 틀림
0
113
0
오류원인?
0
98
0
리스트 선언
0
106
1
침몰하는 타이타닉(그리디) 문제 질문
0
109
1
알고리즘
0
68
1
코딩테스트
0
92
1
DFS 순서 질문드립니다.
0
122
2
left, right를 사용한 풀이법에 대한 질문입니다
0
91
1