그리디 알고리즘
어떤 선택을 할 지 고려할 때 부분 문제들의 결과를 고려할 필요 없이 현재 고려 중인 무넺에서 최적으로 보이는 선택을 하면 된다
DP
단계마다 선택을 해야하고 이 선택은 부분 문제의 해에 의존하게 됨
결과적으로 DP 문제를 풀 경우에는 일반적으로 상향시 접근, 더 작은 부분 문제에서 더 큰 문제로 풀어나가는 방법으로 풀었
하지만 그리디 알고리즘에서는 현재 가장 좋아보이는 선택을 한 후에 그에따라 생기는 부분 문제를 푼다
그리디 알고리즘에 의해 선택을 하는 것은 지금까지 선택한 것에 의존하지만 미래의 선택이나 부분 문제의 해에는 의존할 수 없음 또한 언제나 주어진 문제를 더 작은 문제로 만드는 그리디 선택을 계속하는 하향식 방법으로 진행
예시 그리디 방법으로 해결할 수 있는 문제와 없는 문제의 차이 있는 문제 예시 : 분할 가능 배낭 문제 없는 문제 예시 : 0-1 배낭 문제(knapsack problem = 백준 중량제한) 분할 가능 배낭 문제 = 가방에 금가루, 은가루 등 가루를 넣는다는 개념 0-1 배낭 문제 = 가방에 일정한 무게가 정해진 금괴, 은괴 등을 넣는다는 개념 분할 가능 배낭 문제는 무게당 가치를 계산하여 가장 높은 것부터 순서대로 넣고 남은 남은 공간 또한 가루이기 때문에 전부 다 넣지 않고 일부만 넣어도 가능함 --> 따라서 그리디로 풀수 있음 0-1 배낭 문제는 정해진 무게와 크기가 있기 때문에 만일 금괴가 무게가 10이고 가치가 10이고 은괴가 가치가 6이고 무게가 6 일때 가방에 들어갈 수 있는 무게는 12라고 가정하자 이때 금괴를 넣게되면 남은 무게인 2를 채울 수 있는 방법이 없다 하지만 은괴 두개를 넣게 되면 가치가 12로 최대를 채울수 있게된다 즉 그리디으로는 10의 금을 채우고 남은 2를 은으로 채우면되지만 0-1 배낭문제에서는 채우는 부분이 불가능하기때문에 그리디를 사용할 수 없다는 말이 된다
https://shin8037.tistory.com/