그리디(탐욕) 알고리즘

Greedy 알고리즘

• 오직 현재 시점에 가장 좋은 선택을 하는 것

가장 저렴한 선택
가장 빠른 선택
가장 가치있는 선택

👉🏻 현재 내릴 수 있는 최선의 선택에만 집중한다.

백준 11047

그리드 알고리즘의 특징

❗️그리드 알고리즘 자체가 늘 최적의 해를 보장하는 것은 아니다

현재의 최적 해 ≠ 전체의 최적 해

💡 사용 조건 : 최적 해가 보장되는 조건에서만 사용

1. 현재의 선택이 미래의 선택에 영향을 주지 않는다
2. 부분의 최적 해가 전체의 최적 해가 된다
3. 그리디 전략 (핵심은 정렬)

• [1] 서울에서 대전까지 경로를 선택하는 것이 대전에서 부산까지의 경로를 선택하는 것에 영향을 줄까?

  • ❌
  • 탐욕스런 선택 조건 (Greedy Choice Property)

• [2] 서울 → 부산까지 가는 최소 거리 = (서울 → 대전) + (대전 → 부산)

  • 하나의 큰 문제를 여러 개의 작은 문제들로 나눌수 있음
  • 최적 부분 구조 조건 (Optimal Substructure)
    • 그 작은 문제들에 대한 최적의 해가 더해진 것이 곧, 전체 문제의 최적해가 되는 구조

• [3] 어떻게 정렬을 해야 미래의 선택을 고려하지않고 현재만 고려해도 최적 해를 구할 수 있을까?

  • 회의실 배정 (백준 1931 )

    가장 빨리 끝나는 회의부터 먼저 진행해야 가장 많은 회의를 진행할 수 있다

    • 입력받은 정보들을 종료 시간을 기준으로 오름차순 정렬

이 복잡한 걸 왜 쓸까?

• 그리디 알고리즘은 DP(동적 프로그래밍)의 하위 구조에 속하며 DP 보다도 더 빠르다는 특징이 있음
  • 👉🏻 매우빠른 속도
• gps 길 찾기 로직에서 근사치(10분이내)로 찾아진다면 큰 문제없기 때문에 적당한 해답을 빠른 시간에 얻을 수 있다면 사용자 만족도가 올라감

추천 문제

쉬움
세탁소 사장 동혁(백준 2720)
전자레인지(백준 10162)
거스름돈(백준 5585)
캠핑(백준 4796
컵홀더(백준 2810

보통
설탕배달(백준 2839)
ATM(백준 11399)
동전 O(백준 11047)
잃어버린 괄호(백준 1541)
회의실 배정(백준 1931)

어려움
강의실 배정(백준 11000)
카드 정렬하기(백준 1715)
단어 수학(백준 1339)
수 묶기(백준 1744)
보석 도둑(백준 1202)

---

출처

위 내용은 개발자로 취직하기 강의를 참고하여 공부 및 이해를 목적으로 작성하였습니다. 🙏🏻