코테 이론 - 01. Greedy

Greedy 그리디

현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘

 

1. 특징

    - 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

    - 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형이다.

      (반대로, 정렬, 최단경로 알고리즘은 알고 있어야 풀 수 있는 문제 유형이다.)

    - 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.

    - 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로',

       '가장 작은 순서대로'와 같은 기준을 제시해준다. 그래서 정렬 알고리즘과 같이 잘 나온다.

    - '최적의 해'를 찾을 수 없을 가능성이 다분하다.

    - 그리디로 생각해보다가 해결법을 알 수 없다면, 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 고민해보자

 

2. 대표 문제

https://www.acmicpc.net/workbook/view/4380

문제집: 코딩 테스트 완전 정복 - Greedy(그리디), 탐욕 필수 문제 (park780172)