[일반] 그리디 문제들 많이 풀어본는거 말고

[익명(121.174)]

직관적으로 이렇게하면 되겠다할때 사고하는 방식이 있음??

있다면 누가 빌드좀 가르켜줘라 ㅜㅜ

직관력 너무어렵다

[익명(223.39)]

능지는 타고나야된다

[Gravekper(gravekper)]

문제 보고 일단 완전탐색 되나 해보고, 안되면 DP 되나 생각해보고, 안되면 그럴듯한 그리디 대충 두가지쯤 만들어보고 괜찮아보이면 증명 시도해보고 안되면 한두가지 반례로 나올것같은 패턴 만들어보고 이런식으로 계속 연습하는 거지

[익명(121.174)]

그리디 증명이 어려운게.. 반례없으면 난 그리디라 생각하는데 증명은 어떤식으로하는거 ?? 무슨 허수아비기법이엿나 그거임?

[conankun(conankuns)]

반례 없다고 바로 그리디로 짜는거 위험함. 반례를 생각 못하는 경우가 많거든. Greedy choice proprerty (최적값은 항상 그리디하게 선택한 녀석을 포함한다를 증명하는건데 보통 귀류법을 이용해 그리디 하게 선택한 녀석이 없으면 모순 or 그리디 한 녀석이 안들어 있는 최적해가 있을 때 이를 조금 변형하면 그리디 한 녀석이 들어 있는 최적해로 만들 수 있음을 증명하는 방식) 이랑 optimal substructure (이건 Dp 에서도 증명하는 방식이니 패스; 보통 자동으로 성립함) 를 증명하면 됨.

[익명(118.41)]

그리디나 디피는 능지!