[알고리즘 마스터] 8. 그리디 알고리즘 (Greedy)

안녕하세요. 개발감자 박그냥입니다!🥔

오늘은 알고리즘 중 그리디 알고리즘에 대해서 정리해보도록 하겠습니다.

하루코딩 님의 알고리즘 코딩테스트 핵심이론 강의와 [이것이 코딩 테스트다 with Python] 12강 그리디 알고리즘 개요를 참고하여 작성되었습니다.

 

 

1. 그리디 알고리즘

• 기능 : 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘
• 특징 : 동적계획법보다 구현이 쉽고, 시간복잡도가 우수하다. 하지만, 최적의 해는 보장하지 않는다
• 시간 복잡도 : 우수한 편

코딩테스트에서 대부분의 그리디 문제는
탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제됩니다.

 

2. 그리디 알고리즘 원리

 

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

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

3) 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는 검사한다. 해결할 수 있다면 그만하고 해결할 수 없다면 1번으로 다시 돌아간다.

 

3. 그리디 알고리즘 활용

그리디 알고리즘을 활용한 문제로 가장 유명한 예시로는 거스름돈을 구하는 문제가 있습니다. 이는 제가 포스팅한 동전 개수의 최솟값 구하기 문제풀이를 확인해보시면 좋을 것 같습니다!

---

그럼 더 유익한 포스팅으로 돌아올게요! 개발감자였습니다 :)