[알고리즘] 그리디 알고리즘

1. 개념

현재 상태에서 문제를 해결할 수 있는 가장 좋은 해를 선택해나가면 최적의 답을 구할 수 있게 되는 알고리즘

 

2. 과정

1) 해 선택

현재 상태에서 가장 최선이라고 생각되는 해를 선택한다

2) 적절성 검사

현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다

3) 해 검사

현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다.

 

3. 특징

• 시간 복잡도는 O(n)이다. n개를 쭉 살펴보면서 하나를 해라고 선택한 후, 적절성 검사를 하고, 적절하면 해라고 인식, 적절하지 않으면 해라고 인식하지 않는 과정을 n개 동안 진행한다.
• 앞의 선택(해를 선택하는)이 뒤의 선택에 영향을 미치지 않을 때 사용 가능하다.
• 문제에 대한 최종 해결 방법이 부분 문제에 대한 해결 방법으로 구성되어 있다.

 

4. 관련 문제

백준 11047

GitHub - Lee-Min-Jung/coding_test_practice

백준 1715

GitHub - Lee-Min-Jung/coding_test_practice

백준 1744

GitHub - Lee-Min-Jung/coding_test_practice

백준 1931

GitHub - Lee-Min-Jung/coding_test_practice

백준 1541

GitHub - Lee-Min-Jung/coding_test_practice