[알고리즘] 그리디

|  그리디란?

- 그리디 알고리즘은, 매 선택에서 지금 이 순간 가장 최선이라 생각되는 답을 선택해 결과를 도출하는 것을 말한다.

- 여기서 Greedy을 직역하면 '탐욕'을 뜻한다.

 

- 왜 '탐욕'이라는 말을 쓸까?

  그건 지금 이 순간의 부분적인 최적해가 항상 종합적인 최적해는 아닐 수 있음에도,

  욕심쟁이와 같이 지금 보는 이 부분적인 선택이 전체의 최선이라 단정짓기 때문이다.

  rf. 여러 개의 도시가 연결된 도로가 있고, 그 도로 간에 이동 거리가 각각 다른 상황에서

      가장 이동거리가 짧은 거리를 찾아야한다고 할 때, 그리디를 쓰면 가장 짧은 도로들을 선택하는 게 될 수 있다.

- 정확함 보다는 적당히 맞는 답을 찾을 때 좋은 알고리즘이다. 따라서, 그리디 알고리즘을 근사 알고리즘으로도 부른다.

 

- 언제 쓰는 게 좋을까?

   탐욕 선택 속성, 최적 부분 구조 특정을 가진 문제를 해결하는 데에 강점이 있다.

탐욕 선택 속성	지금 선택이 다음 선택에 영향을 주지 않음
최적 부분 구조	전체 문제의 최적해는 부분 문제의 최적해로 이루어짐

   ex. 서울에서 대구를 거쳐 부산까지 가는 최단 경로 : 서울~대구 최단 경로 + 대구 ~ 부산 최단 경로

 

출처:나무위키

- 그럼 그리디로 풀지 못하는 문제들은 뭘로 풀어야 하지? 

  - 그리디로 풀지 못하는 문제들을 나무위키에서는 아래와 같이 두 가지를 소개했다.

  - 두 문제 모두 DP(동적 계획법)으로 풀 수 있는데, 두 가지 모두 차후 풀이 후 정리해보려고 한다.

외판원 문제	https://www.acmicpc.net/problem/2098
배낭 문제	https://www.acmicpc.net/problem/12865

 

- 그리디 알고리즘의 풀이 순서

	순서	예시 (ex. N구의 멀티탭 하나로 여러 제품을 사용할 때)
1	최적해 선택 : 지금 가장 최선이라 생각되는 해를 선택	ex. 이미 N개가 껴있는 상태에서 최소 교체 수 얻기       - 지금 제품이 이미 껴 있으면 무시하고       - 안 껴져 있으면 껴있는 것 중에         내 다음으로 쓸 제품 중이 아닌 것과 교체
2	적절성 검사 : 지금 고른 최적해가 전체 문제의 제약 조건을 벗어나는지 확인	ex. N개만 들어가야 하는 조건 성립하는가
3	해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결하는지 검사	ex. 지금까지 고른 최소값이 전체의 최소가 맞는가

 

|  대표적인 그리디 문제 

Activity Selection Problem	가장 많은 활동을 하려면? https://www.acmicpc.net/problem/12018
거스름돈 문제	가장 적은 동전의 수는? https://www.acmicpc.net/problem/11047

 

|  그리디 문제집

https://www.acmicpc.net/step/33

그리디 알고리즘 단계

 

 

[ 참고 및 출처 ]

부트캠프 강의 후 정리

[Do it 알고리즘 코딩 테스트 - 자바 편]

나무위키