[알고리즘] 탐욕법 (Greedy Algorithm)

Greedy Algorithm은 최적해를 구하는 상황에서 사용하는 방법이다.

- 여러 경우 중 최적의 경우의 수를 선택하여 문제를 해결해 나간다.

- 즉, 데이터 간의 관계를 고려하지 않고 수행 과정에서 'greedy(욕심내어)' 데이터를 선택한다.

- 이러한 선택을 '근시안적' 선택이라고도 한다.

 

- Greedy Algorithm은 방법이 통하는 몇몇의 문제에서는 최적해를 빠르게 산출해낼 수 있다.

- 방법이 통하는 문제들은 다음의 특징을 가진다

  1. 한번의 선택이 다른 선택에 전혀 무관한 값이다.

  2. 매 순간의 최적해가 문제에 대한 최적해이다.

 

- 순간순간마다 최적의 결정을 함을 통해 전체 문제해결에 대해서 가장 최적의 결과를 얻는 것이 보장되어 있지 않다.

- 어느정도 적합한 수준의 해답을 알려주는 알고리즘이다.

- 계산속도가 정확한 알고리즘에 비해서 실행속도가 빠른 경우가 많아 실용적인 사용이 가능하다.

 

 

 

 Greedy Algorithm을 통해 해결한 문제

[백준 13904] 과제

[BAEKJOON 13904번] (C++) 과제

[백준 4796] 캠핑

[BAEKJOON 4796번] (C++) 캠핑

[백준 1449] 수리공 항승

[BAEKJOON 1449번] (C++) 수리공 항승