파이썬 알고리즘 인터뷰 그리디 알고리즘 간단 정리

그리디 알고리즘

• 그리디 알고리즘 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘 눈 앞의 이익만을 좇는 알고리즘 최적화 문제를 대상으로 하며 최적해를 찾을 수 있으면 그것을 목표로 삼고, 찾기 어려운 경우에는 주어진 시간 내에 그런대로 괜찮을 해를 찾는 것을 목표로 삼음 우선순위 큐 자체가 그때그때 최소, 최대 값 추출하기 때문에 그리디에 어울리는 대표적인 자료구조 그리디 문제 대부분은 우선순위 큐 활용해 풀이
  • 잘 작동하는 문제 탐욕 선택 속성과 최적 부분 구조를 동시에 갖고 있음
    • 탐욕 선택 속성 앞의 선택이 이후 선택에 영향을 주지 않는 것을 말함 선택을 다시 고려하지 않음
    • 최적 부분 구조 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우 DP 와 비교되지만 서로 풀 수 있는 문제의 성격이 다르며 알고리즘의 접근 방식 또한 다름
  • 사용 예
    • 배낭 문제 짐을 쪼갤 수 있냐 없냐에 따라 그리디/DP 로 해결 단가가 높은 짐부터 차례대로 채워나가는 방식으로 해결
    • 동전 바꾸기 문제 이전 액면의 배수 이상/이하 면 그리디/DP 큰 동전 부터 차례대로 채워나가는 방식으로 해결
    • 가장 큰 합 노드를 계속 더해가다가 마지막에 가장 큰 합이 되는 경로 찾기 문제 간선으로 연결된 2가지 선택지 중 더 큰 수를 더해나가도 트리가 정렬되어 있지 않기 때문에 불가능
  • DP 와의 차이 DP 가 하위 문제에 대한 최적의 솔루션을 찾은 다음 이 결과들을 결합한 정보에 입각해 전역 최적 솔루션 선택 그리디는 각 단계마다 로컬 최적해를 찾는 문제로 접근해 문제를 더 작게 줄여나는 형태 서로 반대방향