말씀하신 것처럼 반례가 없다면 동적 계획법이 필요가 없겠지만, "반례가 없다"는 사실을 보이기 위해서는 증명이 필요합니다. 그리고 증명은 그냥 코딩해서 맞았습니다를 받는 것보다는 어려운 경우가 많습니다. 대표적인 예시로 BOJ 15011 - Irrational Division (BAPC 2017 I번)이 있습니다. 이 문제의 경우 동적 계획법으로도 풀 수 있고, 그리디를 통해 매우 간단한 수식 만으로도 풀 수 있지만 동적 계획법 풀이에 비해 이를 알아채기는 어렵습니다.
정해가 동적 계획법인데 그리디로 도전하면 분명히 어디선가 반례가 나올 것입니다. 안전하게의 문제가 아니라 그리디가 틀렸기 때문입니다.
정해가 그리디인데 동적 계획법으로 접근하는 건 시간 복잡도나 공간 복잡도 상으로 문제가 생길 것입니다. (예시 : N = 10^5인데 DP로는 O(N^2)밖에 안 보일 때)
결국 많이 풀어보고 자신의 직관과 경험을 기르는 수밖에 없습니다. 동적 계획법이나 그리디나 결국은 수식으로 올바름을 증명해야 하기 때문입니다.
2015136077 4년 전 1
어떤 문제가 주어졌고 최솟값을 구하는 문제에서 dp와 그리디 알고리즘 중 어떤것을 접근해야할지 알 수 있는 방법이 있나요.
이 문제의 경우 그리디로 푸는 경우 반례가 생긴다는 거를 그나마 직관적으로 알기때문에 dp로 풀 수 있지만, 그렇지 않다면 그리디를 했을 것 같습니다.
dp는 재귀적으로 배열에 저장하는 방식이기에 브루트포스에 해당하고 그리디는 재귀적으로 찾아가는 방식에서 답이 아닌 경우를 알게 되면 과감하게 경로를 포기하는 알고리즘이라 이해했습니다. 문제는 반례가 없다면 브루트포스의 dp로 풀 필요없이 그리디로 푸는게 맞지않나요?
그렇다면 대부분의 문제는 그리디가 올바른데 반례가 있을까봐 그냥 안전하게 dp로 문제를 푸시는 경우가 대부분의 사람들의 풀이법인지 궁금합니다.
만약 이런 비슷한 문제가 나올때 반례가 존재 = dp, 반례가 없다면 = 그리디로 문제를 접근해야하는게 공식인지 다른분들은 어떻게 그 둘을 구분하시는지 궁금합니다.