C++: 그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘(Greedy Algorithm)

• 탐욕적 알고리즘
• 현재 가장 최선의 선택지만 고르는 알고리즘으로, 이 선택이 전체에서도 좋은 선택지임이 보장되어야 한다.
  • 비교
    • 완전탐색 - 모두 확인
    • 백트래킹 - 막다른길은 건너뜀
    • 그리디 - 순간마다 최선만 보고 직진

      통하기 위한 조건

  • 배수 관계
    • 모든 선택지가 서로 배수관계가 아니면, 최적의 해가 안나올 수 있다!
      • ex) 동전선택문제 - 500원동전과 400원 동전, 배수관계 아니여서 최적 해 안나옴.
  • 두가지 속성
    • 탐욕적 선택 속성
      • 지금의 선택이 전체에도 최선
      • ex) 앞에서 선택한 가장 큰 동전들이 전체에 있어서도 좋은 선택
    • 최적 부분 구조
      • 부분문제의 최적인 답이 전체 답의 일부
      • ex) 앞서 선택한 500원 동전의 갯수가 전체 정답에 포함
    • 이 2 조건 있을때만 사용 가능

      활용

• 스케쥴링 - SJF(Shorter Job First)
• 압축 - 허프만 인코딩
• 네크워크 라우팅 - 전체 네트워크 파악 없이 지금 빠른 경로만 선택
• 게임개발
  • AI - 매턴 가장 유리한 행동
    • 자원 관리 게임
    • 전투 AI
    • A* 휴리스틱
    • 매치메이킹
    • 복잡한건 힘들지만 않지만 빠른결정에선 가성비 최강
  • 웹 서버
    • CDN - 가장 가까운 서버 선택
    • 로드 밸런서 - 가장 여유로운 서버 선택
    • LRU 캐시 - 오래 안쓴건 버리기
    • 광고 입찰 - 광고 노출 순서
  • 일반CS
    • 허프만 인코딩 - 많은 빈도의 값에 짧은 이진코드 우선부여
    • 크루스칼 / 프림 - 최소신장 트리
• 조건만 맞으면 효율과 최적해를 모두 보장하는 알고리즘으로 전반에 사용