그리디 알고리즘 질문

[c언어 최대 ..(211.183)]

문제가 그리디 같을 때, 시도하고봄 아니면 나름대로 증명을 거친다음에 시도함?

감으로 푸는 건 되도 이게 맞다는 걸 증명하는 게 어려워

[익명(58.124)]

머리 좀만 좋으면 그리디라는게 딱 느낌 옴 그럼 생각할 필요없이 그리디로 풀면 됨

[c언어 최대 난제(211.183)]

그 느낌을 증명해낼 수 있느냔 말이지

[익명(58.124)]

너무 당연한거라 증명이 필요없는데.. 문제 풀고 증명해보던가

[c언어 최대 난제(211.183)]

흔한 예로 거스름돈 최소갯수로 걸러주는 문제에선 큰 단위를 우선으로 선택하면 되잖아. 이건 딱 느낌이오고 당연한 것 같지만 400원짜리 동전이 추가 되면 그리디로는 못풀잖아. 증명하지 못하면 불확실하다 생각함

[익명(58.124)]

특수 조건이 추가되거나 하면 그리디 문제가 아니라는게 느껴지지 않겠누..

[c언어 최대 난제(211.183)]

그리디라는 걸 모른 단 가정하에 특수 조건 추가 유무로 어케 변별함