그리디(Greedy) 개념

그리디(Greedy) 알고리즘

Greedy란 '탐욕스러운, 욕심 많은'이라는 뜻을 가지고 있다.

우리는 어떠한 답을 효율적으로 찾으려고 다양한 알고리즘을 공부한다.

그러면 알고리즘에서 '탐욕스럽고 욕심 많은'이라는 뜻은 무엇일까?

필자의 생각은 빠르게 답을 찾으려고 하는 것이다.

 

• 순간순간 최적의 선택을 해나가는 방법으로 진행하여 최종적인 정답에 도달하게 된다.
• 계속해서 최적의 선택을 하였다고 해서 최종적인 정답이 정답이 아닐 수도 있다.
• 따라서 그리디 알고리즘은 최적의 해를 구하는 데 사용하는 '근사 알고리즘'이라고 할 수 있다.

'근사 알고리즘'이란
해의 근사값을 구하는 알고리즘을 말한다.
가장 최적화되는 답을 구할 수는 없지만, 어느 정도 근삿값을 구할 수 있다.

 

---

방법

1. 선택

  - 현재 상태에서 최적의 해를 구한다.

2. 적절성 검사

  - 1번에서 선택한 해가 조건을 만족하는지 확인한다.

3. 해답 검사

  - 문제가 해결되었는지 확인하고 해결되지 않았다면 1번으로 돌아간다.

 

---

문제풀이

[알고리즘/문제] - 백준 11047 [동전 0] - JAVA

[알고리즘/문제] - 백준 2839 [설탕 배달] - JAVA

[알고리즘/문제] - 백준 1715 [카드 정렬하기] - JAVA

[알고리즘/문제] - 백준 1202 [보석 도둑] - JAVA