일명 탐욕쟁이 알고리즘이라 불리는 그리디 알고리즘은 '현재 상황에서 가장 좋은 것만 고르는 방법'을 의미한다.
다른 알고리즘과 다르게 암기가 아니고 여러 유형을 접해보고 문제를 풀어보면 훈련을 해야 한다.
문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준이 제시된다면 그리디 알고리즘으로 해결할 수 있다.
'순서'를 가지고 정렬이 되는 것을 전제로 하기 때문에, 정렬 알고리즘과 짝을 이루어 출제되는 경향이 있다.
백준 11047번 : 동전
n, k = map(int, input().split())
m = []
num = 0
for i in range(n):
m.append(int(input()))
for i in range(n - 1, -1, -1):
if k == 0:
break
if m[i] > k:
continue
num += k // m[i]
k %= m[i]
print(num)접근 방식
1. 가장 큰 화페단위부터 거슬러주고 몫은 따로 저장한다
2. 점차 작은 화페 단위로 나눈다.
"최소"의 화폐 갯수를 위해 큰 단위로 나누었다.
"첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)"
라는 조건이 중요하다!
배수 단위이기 때문에 문제가 수월해졌다.(큰 단위가 작은 단위의 배수 형태)
배수 단위라는 조건으로 인해 "큰 화폐에서 작은 화폐 순으로 거슬러준다"는 접근이 정당성을 가지기 때문이다.
동전 문제의 시간 복잡도는 O(K)이다.(K = 화폐의 종류)
화폐의 가치가 아니라 단순히 동전의 총 종류의 개수만이 시간 복잡도에 영향을 미친다.
백준 13305번: 주유소
N = int(input())
roads = list(map(int,input().split()))
price= list(map(int,input().split()))
minVal = price[0]
#가장 작은 주유비를 가진 도시를 첫번째로
sum = 0
for i in range(N-1):
#마지막 도시 제외한 n-1 도시의 수만큼 반복
if minVal > price[i]:
#최소금액이 현 도시의 금액보다 크면
minVal = price[i]
#최소금액을 현 도시의 금액으로 바꾼다(최소라는 조건을 유지하기 위해)
sum +=(minVal * roads[i])
print(sum)
접근 방식
1. 첫번째 도시에서 주유를 꼭 해야 출발할 수 있으므로 1L당 5원의 주유를 실행한다.
2. 이전의 주유했던 도시보다 주유비가 싼 도시를 만나면 주유한다.
3. 현재 도시보다 주유비가 비싸다면 이전 도시에서 주유해야 "최소"라는 조건에 부합할 수 있다.
4. 주유비 기준으로 "내림차순 정렬"을 하면 최소 주유비가 성립된다.
백준 11000번: 강의실
import heapq
N = int(input())
q =[]
for i in range(N):
S,T= list(map(int, input().split()))
q.append([S,T])
q.sort()
#시작시간과 종료시간을 q에 입력 후 리스트 q 오름차순 정렬
room = []
heapq.heappush(room,q[0][1])
for i in range(1,N):
if q[i][0]<room[0]:
#다음 시작 시간보다 끝나는 시간이 더 늦으면 heappush로 추가
heapq.heappush(room,q[i][1])
else:
#다음 시작 시간보다 끝나는 시간이 더 빠르면 heappop으로 제거 후 기존 강의실 사용하기 위해 heappush로 추가
heapq.heappop(room)
heapq.heappush(room, q[i][1])
print(len(room))
접근 방식
1. 수업 시작 시간 S, 수업 종료 시간 T를 입력값으로 받는다.
2. 수업 1의 S보다 수업 2의 T가 더 작으면 새로운 강의실을 추가한다.
3. 수업 1의 S보다 수업 2의 T가 더 크면 수업 1이 끝나고 수업 2가 같은 강의실을 사용할 수 있다.
4. S, T값을 가진 리스트가 필요하고 시간순으로 정렬해야 하므로 heapq를이용한다.
첫 시도 때, heapq의 존재를 모르고 있었기 때문에 처음에 i값과 j값을 가지는 이중 for문을 돌리는 접근을 시도하였는데 종료시간보다 시작시간이 더 빠른 경우를 처리하는데 문제가 있어 실패하였다..ㅠ
채점 결과
시간 초과!!!
프로그래머스: 그리디-체육복
def solution(n, lost, reserve):
answer=0
set_lost = set(lost)-set(reserve)
set_reserve= set(reserve)-set(lost)
for i in set_reserve:
#reseve에 존재하면 lost에서 제거
if i-1 in set_lost:
set_lost.remove(i-1)
elif i+1 in set_lost:
set_lost.remove(i+1)
#전체 학생수에서 lost만큼 제거(이 전제는 reserve와 lost가 중복되지 않았기 때문에 가능하다.)
answer =n-len(set_lost)
return answer 접근 방식
1. 여벌을 가진 학생(reserve)과 잃어버린 학생(lost) 두 집합으로 나눈다.
2. 여벌을 가진 학생 중에서도 잃어버릴 수 있다.>>"단, 중복 불가"
3. 여벌을 가진 학생은 자신의 앞 뒤 번호(index)에게 빌려줄 수 있다.(1번은 2번에게 빌릴 수 있고, 5번은 4번에게 빌릴 수 있다.)
중복을 제거하는 부분 때문에 for문에 여러 조건을 넣었는데 set을 이용하면 중복이 자동으로 제거된다는 것을 알게 되었다.
역시 아는 만큼 보이는구나...ㅎㅎ
