Greedy Algorithm

🙂 파이썬 알고리즘 인터뷰를 공부하며 적는 공부 흔적입니다.

그리디 알고리즘

• 바로 눈 앞의 이익만을 좇는 알고리즘
• 대부분의 경우에는 뛰어난 결과를 도출하지 못하지만, 드물게 최적해를 보장하는 경우도 있음
• 최적화 문제를 대상으로 한다. (특히 로컬 최적해)
  • 최적해를 찾을 수 있으면 그것을 목표로 삼고, 찾기 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 함.

그리디 = 탐욕 선택 속성 + 최적 부분 구조

• 탐욕 선택 속성 : 앞의 선택이 이후 선택에 영향을 주지 않는 것 (선택을 다시 고려하지 않음)
• 최적 부분 구조 : 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우

→ 이 두 가지 조건을 만족하면 최적해를 찾을 수 있다. (만족하지 않더라도 정답을 근사하게 찾는 용도로 사용 가능)

자주 쓰이는 예시

• 다익스트라 알고리즘
• 허프만 코딩
• ID3 알고리즘 (의사결정 트리) → 다만 이때는 항상 최적해를 찾는 것은 아니고, 근사하게 찾는 용도로 사용되는 예시

그리디 알고리즘은 다이나믹 프로그래밍과 비교되는데, 서로 풀 수 있는 문제의 성격이 서로 다르다.

다이나믹 프로그래밍은 하위 문제에 대한 최적의 솔루션을 찾은 후, 이를 결합한 정보에 입각해서 전역 최적 솔루션 (globally optimum solution)에 대한 선택을 한다.

그리디 알고리즘은 각 단계마다 로컬 최적해를 찾는 문제로 접근해 문제를 더 작게 줄여나가는 형태이다.

⇒ 서로 반대 방향으로 접근하는 방식임