1. 그리디

그리디(탐욕 알고리즘)

개요

최적해를 고르는 근사적인 방법 이며, 지금 당장 좋은것만 고르는 알고리즘이다.
해당종류의 알고리즘은 응용이 많아 단순히 암기로 풀이하기 어렵다. 따라서 많은 문제를 풀어보는 것이 좋으며, 특히 다른 알고리즘과 접합하여 문제가 나오면 난이도가 높아진다. 특히 정렬 알고리즘과 접합하는 경우가 많은 것 같다.

또한 알고리즘 구현 과정에서 문제풀이에 아이디어를 제시하고 아이디어가 정당한가 검증할 수 있어야 한다.

마지막으로 최적해를 고르는 것이지 항상 그것이 최적인 방법은 아니다.
즉, 그리디를 이용해 문제를 풀이 할 수 있으려면 다음의 두가지 조건을 만족해야 한다.

• 탐욕스러운 선택 조건 (Greedy Choice Property)
  • 앞의 선택이 이후에 영향을 주지 않는다.
• 최적 부문 구조 조건 (Optimal Substructure)
  • 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

매트로이드 구조를 띄고 있으면 그리디가 성립하지만, 모든 그리디 문제가 매트로이드의 성질을 띄고 있지는 않는다.

과정

1. 선택 절차 : 가장 가치가 높은 것을 먼저 선택한다
2. 적절성 검사 : 1번 과정이 문제의 조건에 부합하는지 검사한다. (최적부문 구조 조건)
3. 해답 검사 : 최종 결과가 문제에 부합하는지 검사한다.

그리디 응용

• 최소 신장 트리 (MST)
• 거스름돈 문제 (단, 동전들이 배수관계가 성립시)
• 다익스트라 알고리즘
• 허프만 코드
• 크루스컬 알고리즘 (Disjoint Set)

문제

캠핑

[BOJ-4796] 문제[BOJ-4796] 풀이

동전 0

[BOJ-11047] 문제 [BOJ-11047] 풀이

과제

[BOJ-13904] 문제 [BOJ-13904] 풀이

멀티탭 스케줄링

[BOJ-1700] 문제 [BOJ-1700]풀이