그리디

 

 

📍 정의 및 특징

- 각 단계마다 지금 당장 가장 좋은 방법만을 선택
   (현재 선택이 앞으로 남은 선택들에 어떤 영향을 미칠지 고려 X)

- 그리디를 사용해 항상 최적해를 구할 수 있는 문제를 만난 경우, DP보다 훨씬 빠름

 

 

🧩 필요한 자료구조

✔ 정렬된 배열 / 리스트

✔ 우선순위 큐 : 가장 크거나 작은 원소 찾을 때 사용 (최소 힙 / 최대 힙 활용)

✔ 스택 / 큐       : 특정 순서로 요소 처리 시 활용 (ex ; 회의실 시간표 짤 때 시간 / 종료 시간 기준 정렬된 배열 -> 스택 / 큐로 활용 가능)

✔ 해시 맵          : 특정 값을 빠르게 찾고 업데이트 할 때 사용

✔ 배열 / 리스트를 활용한 직접 구현

 

 

📍 실행 과정

1. 해 선택        : 현재 상태에서 가장 최선이라고 생각되는 해 선택
2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건을 위배하지 않는지 검사
3. 해 검사        : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사

 

 

📍 문제 유형

• 동전 문제
• Knapsack문제

 

➕ 예제

문제집: 0x11강 - 그리디 (BaaaaaaaaaaarkingDog)

---

(참고)

[알고리즘] 탐욕스러운 그리디(Greedy) 알고리즘 정리 (Java)

[이것이 코딩 테스트다 with Java] 그리디 알고리즘 (Greedy Algorithm)

알고리즘 - 그리디 알고리즘(Greedy Algorithm)

[Java/알고리즘] 그리디 알고리즘(탐욕법, Greedy Algorithm) 이해하기

[Java] 탐욕 알고리즘이란? (개념/ 코드 예제/ 알고리즘 한계)