[Algorithm] Greedy(그리디) 개념 정리
수업시간에 교수님께서 그리디 알고리즘을 소개하실 때 단어 뜻 그대로 '탐욕' 알고리즘이라고 설명하셨던게 기억난다. 실제로 이 알고리즘은 가장 좋아보이는, 당장 좋은 것을 먼저 고르는 알고리즘이다. 대표적으로 동전 개수 구하기, 회의실 배정 등의 문제들이 있다. 무조건적으로 그리디가 최적해를 보장하지는 않기 때문에 (오히려 그리디로 최적의 해를 찾기 어렵다고 한다.) 그리디를 사용할 때는 문제 유형을 보고 판단하도록 하자. 동전문제는 그리디의 대표적인 문제인데, 이때 그리디 알고리즘으로 최적해가 보장되는 경우는 아래의 조건을 만족한 경우이다. - 동전의 액면이 모두 바로 아래 액면의 배수가 된다. 백준에 올라와있는 동전 문제는 주어진 동전들이 배수의 관계이므로 그리디 알고리즘을 사용하여 풀 수 있었다. h..
TIL
2022. 3. 1. 18:53