초급 4회차 그리디 알고리즘

그리디 알고리즘의 개념

부분적인 최적 전략을 반복적으로 취하는 알고리즘이다.

당장 눈앞에 놓인 것들 중 제일 이득인 선택지를 골라잡아가며 해결하는 방식도 그리디 알고리즘 중 하나이다.

 

어떤 문제가 그리디인가?

각각의 부분 문제의 최적해들이 전체 문제의 최적해의 일부인 문제.

 

그리디 문제를 풀 때 고려해야 하는 것

• 전체 문제를 어떻게 쪼개어 부분 문제들로 나눌 것인가?
• 각 부분 문제의 최적해를 구할 방법, 즉 부분 문제의 최적 전략은 무엇인가?
• 그 최적 전략 실행의 제약사항은 없는가? 있다면 어떻게 충족시킬 것인가?
• 부분 문제들에 대해 특정 순서로 최적 전략을 반복하면 정말로 전체 문제의 최적해가 나오는가?

 

일반적으로, 아무리 어려운 그리디 문제라도 대부분 위와 같은 사고의 과정이 어려울 뿐

복잡한 자료구조나 수학 공식 때문에 어려운 경우는 드물다고 한다.

어떻게 문제를 쪼개고, 어떻게 각각의 최적해를 구할 것인가?

이런 사고를 해내는 것이 매우 중요!