[이코테] 그리디 알고리즘 개념 및 문제

👀그리디 알고리즘(탐욕법)

🔒 현재 상황에서 지금 당장 좋은 것만 고르는 방법
🔒 문제를 풀기 위한 최소한의 아이디어를 떠올리는 능력
🔒 정당성 분석이 중요
*단순히 가장 좋아 보이는 것을 반복해도 최적의 해를 구할 수 있는지 검토**

기출 유형

일반적으로 최적의 해를 보장할 수 없는 경우가 많다.

때문에 코딩테스트에서는 그리디 알고리즘으로 얻은 해가 최적의 해가 되는 상황에서 출제된다.

---

문제 1 : 거스름돈

거스름돈으로 500, 100, 50, 10원짜리 동전으로 N원을 거슬러 주어야 할 때 동전의 최소 개수를 구하시오.
*동전은 무한히 존재한다.
*N은 10의 배수이다.

아이디어

가장 큰 화폐단위 부터 돈을 거슬러 준다.

정당성

가장 큰 화폐단위부터 거슬러 주는 것이 최적의 해를 보장하는 이유는?

큰 단위의 화폐가 항상 작은 단위의 배수 이므로 작은 단위로 다른 해를 구할 수 없다.

*그리디 알고리즘에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 정당한지 검토 할 수 있어야 한다.

답

개인 풀이

참고로 이건 꽤 재미있게 접근했다고 생각 했지만 오답이다.

*왜 오답인지 찾아보는 것도 재미있을 것이다.

시간 복잡도

화폐의 종류가 k라고 할때 시간 복잡도는 O(k) 이다.

*화폐의 종류에만 영향을 받는다.

---

문제 2 : 1이 될 때까지

N이 1이 될때까지
1. N에서 1을 뺀다
2. N에서 K를 나눈다..
1 번 혹은 2번을 반복할때 최소 횟수를 구하시오.

아이디어

N에 대하여 최대한 많이 나누기를 수행한다.

*2이상의 수로 나누는 작업이 1을 빼는 것보다 횟수를 효과적으로 줄일 수 있다.

정당성

최대한 많이 나누는 것이 최적의 해를 보장하는가?

K가 2 이상일 때 1을 빼는 것보다 빠르게 N의 크기를 줄일 수 있으며 N은 항상 1에 도달한다.

답

개인 풀이

시간 복잡도

한번에 뺄셈과 나눗셈을 실행하므로 로그시간 복잡도로 계산할 수 있다.

---

문제 3 : 곱하기 혹은 더하기

아이디어

숫자가 2 이상일 경우 곱셈을 한다.

정당성

숫자가 0 혹은 1이 아닌이상 + 보다 *이 값을 더 크게 만든다.

답

개인 풀이

---

문제 4 : 모험가 길드

모험가가 N명이다.
그룹을 생성할 때 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 한다.
여행을 떠날 수 있는 그룹수의 최댓값을 구해라.
모든 모험가를 그룹에 넣을 필요는 없다.

아이디어

오름차순으로 정렬한 모험가 배열을 앞에서 부터 그룹에 포함된 모험가의 수가 공포도 보다 크거나 같다면 그룹으로 설정한다.

 

정당성

공포도가 오름차순으로 정렬되어 있기 때문에 항상 최소한의 모험가만 포함하여 그룹을 결성하게 된다.

답