그리디 알고리즘 (탐욕 알고리즘)
미래를 내다보지 않고 당장 눈 앞에 보이는 최적의 선택을 하는 방법으로, 목표 달성을 위해 매 순간마다 탐욕적인 선택을 한다.
- (장점) 간단하고 빠르다
- (단점) 최적의 답이 보장되지 않는다.
동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다. 동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념이다.
알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택한다. 현재의 선택이 마지막 해답의 최적성을 해치지 않을 때 탐욕법으로 최적해를 찾을 수 있다.
최적의 솔루션 필수 조건
그리디 알고리즘이 최적의 답을 보장해 주는 경우를 만족하기 위한 두 가지 조건이 있다.
- 최적 부분 구조 (Optimal Substructure)
- 탐욕적 선택 속성 (Greedy Choice Property)
최적 부분 구조는 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것이다.
탐욕적 선택 속성은 각 단계에서의 탐욕스런 선택이 최종 답을 구하기 위한 최적의 선택이라는 것이다.
대표적인 예로 최소 동전 거슬러주기 문제가 있다.
# 최소 동전 거슬러주기
def min_coin_count(value, coin_list):
# params : 거슬러 줘야 하는 총액, 동전 리스트
count = 0
for coin in sorted(coin_list)[::-1] : # or reverse=True
count += (value // coin)
value %= coin
return count예제 문제
- 체육복 빌려주기
- 지각 벌금 적게 내기
- 수강신청 분석
- 큰 수 만들기
- 최대곱 구하기
➲ 체육복
- 학생 수만큼 배열을 확보하고, 여기에 각자가 가지고 있는 체육복의 수를 기록한다.
- 빌려줄 학생들을 정해진 순서로 스캔하면서 빌려줄 방향을 정한다.
# 방법 1. 효율적인 방법 O(n)
def solution(n, lost, reserve):
u = [1] * (n + 2)
# 1) 여벌을 가져온 학생 처리 : reserve 길이에 비례 O(n)
for i in reserve :
u[i] += 1
# 2) 체육복을 잃어버린 학생 처리 : lost 길이에 비례 O(n)
for i in lose :
u[i] -= 1
# 3) 체육복 빌려주기 처리 : 전체 학생 수 n에 비례 O(n)
for i in range(1, n+1) :
if u[i-1] == 0 and u[i] == 2 :
u[i-1:i+1] = [1, 1]
elif u[i] == 2 and u[i+1] == 0 :
u[i:i+2] = [1, 1]
# 3) 나는 아래와 같이 풀었다.
for r in reserve :
if x[r-1] == 0 and x[r] > 1 :
x[r-1] += 1
elif x[r+1] == 0 and x[r] > 1 :
x[r+1] += 1
return len([x for x in u[1:-1] if x>0])
--------------------------------------------------
# 방법 2. 전체 학생 수가 크고, 여벌을 가져온 학생이 적을 경우 O(klogk)
def solution(n, lost, reserve):
s = set(lost) & set(reserve) # 도난 o, 빌려야 하는 학생
l = set(lost) - s # 체육복을 빌릴 필요 없는 학생
r = set(reserve) - s # 여분 o, 빌려줄 수 있는 학생
# 여벌의 체육복을 가져온 학생 정렬 O(klogk)
# 빌려줄 수 있는 다른 학생을 찾아서 처리 : 해시 적용, O(k)*O(1)
for x in sorted(r) :
if x-1 in l :
l.remove(x-1)
elif x+1 in l :
l.remove(x+1)
return n - len(l)➲ 지각 벌금 적게 내기
합주에 1분에 1달러씩 내야 하는 벌금 제도가 있는데, 마침 익중이와 친구 넷이 놀다가 또 지각할 위기다. 아직 악보도 출력해 놓지 않은 상황이다. 어차피 같이 놀다 늦은 것이니 벌금을 다섯 명이서 똑같이 나눠 내기로 하고, 벌금을 가능한 적게 내는 방법을 고민해 보기로 했다.
다섯 사람이 각각 출력해야 하는 페이지 수는 3장, 1장, 4장, 3장, 2장입니다. 프린터는 한 대밖에 없고, 1장을 출력하기 위해서는 1분이 걸린다.
현재 순서대로 출력한다면,
첫 번째 사람: 3분 지각
두 번째 사람: 3+1분 지각
세 번째 사람: 3+1+4분 지각
네 번째 사람: 3+1+4+3분 지각
다섯 번째 사람: 3+1+4+3+2분 지각
총 39달러의 벌금을 내야 한다. 더 적게 내는 방법은 없을까?
(최적 부분 구조)
(탐욕적 선택 속성) 기다리는 시간을 최소화하기 위해서는, 페이지 수가 적은 사람 순으로 출력하는 것이 최선이라고 확신할 수 있다.
# 벌금 적게 내기
def min_fee(pages_to_print):
sorted_list = sorted(pages_to_print)
total_fee = 0
for i in range(len(sorted_list)):
total_fee += sorted_list[i] * (len(sorted_list) - i)
return total_fee
# 나의 풀이
def min_fee(pages_to_print):
fee = 0
total_fee = 0
for time in sorted(pages_to_print) :
fee += time
total_fee += fee
return total_fee➲ 수강 신청 분석
리스트에 담겨있는 튜플들은 각각 하나의 수업을 나타낸다. 각 튜플의 0번째 항목은 해당 수업의 시작 시간, 그리고 1 번 항목은 해당 수업이 끝나는 시간이다.
열정이 불타오르는 신입생 지웅이는 최대한 많은 수업을 들을 수 있는 수업 조합을 찾아주는 함수를 작성하려고 한다. 파라미터로 전체 수업 리스트를 받고 가능한 많은 수업을 담은 리스트를 리턴한다.
(최적 부분 구조)
(탐욕적 선택 속성) 남은 수업 중 가장 먼저 끝나는 수업을 선택하면, 늘 최선의 결과를 이뤄낼 수 있다.
# 수강 신청
def course_selection(course_list):
# 수업을 끝나는 순서로 정렬한다
sorted_list = sorted(course_list, key=lambda x: x[1])
# 가장 먼저 끝나는 수업은 무조건 듣는다
my_selection = [sorted_list[0]]
# 이미 선택한 수업과 안 겹치는 수업 중 가장 빨리 끝나는 수업을 고른다
for course in sorted_list:
# 마지막 수업이 끝나기 전에 새 수업이 시작하면 겹친다
if course[0] > my_selection[-1][1]:
my_selection.append(course)
return my_selection
# 나의 풀이
def course_selection(course_list):
time = [(0, 0)]
for course in sorted(course_list, key = lambda x:x[1]) :
if course[1] > time[-1][1] and course[0] > time[-1][1] :
time.append(course)
return time[1:]➲ 큰 수 만들기
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자 구하기
- number는 1자리 이상, 1,000,000자리 이하인 숫자
- k는 1 이상 Number의 자릿수 미만인 자연수
- 앞 자리부터 하나씩 골라서 담되, 큰 수가 나오면 앞에 나온 작은 수는 뺀다.
- 제약 조건에 도달하면 나머지 수를 그대로 붙인다.
- 빼야 할 횟수가 남아있으면 맨 뒤의 수를 뺀다.
# 복잡도 O(n) (n은 자릿수)
def solution(number, k) :
collected = []
for i, num in enumerate(number) :
while len(collected) > 0 and collected[-1] < num and k > 0 :
collected.pop()
k -= 1
if k == 0 :
collected += list(number[i:])
break
collected.append(num)
collected = collected[:-k] if k > 0 else collected
answer = ''.join(collected)
return answer
# 나의 풀이
def solution(number, k):
num = []
for i, n in enumerate(number) :
while len(num) > 0 and num[-1] < n and k > 0 :
num.pop()
k -= 1
num.append(n)
if k == 0 :
return ''.join(num) + number[i+1:]
if k > 0 :
return ''.join(num)[:-k]앞 단계에서의 선택 "앞 자리에 큰 수를 두는 것"이 이후 단계에서의 동작에 의한 해의 최적성에 영향을 주지 않기 때문에 탐욕법이 적용 가능하다.
➲ 최대곱 구하기
여럿이서 카드 게임을 하고 있는데, 각 플레이어는 3장의 카드를 들고 있다. 한 사람당 카드를 하나씩 뽑아서 모두 곱했을 때 가능한 최대 곱을 구하라.
(최적 부분 구조) max_product([[1, 2, 4], [8, 2, 4], [3, 4, 1]])를 풀고 그 결과값을 9랑 곱한 값, 6이랑 곱한 값, 3이랑 곱한 값 중 가장 큰 값이 기존 문제의 정답이 된다.
(탐욕적 선택 속성) 각 값은 카드에 적혀 있는 숫자이기 때문에 0보다 큰 양수다. 따라서 무조건 큰 숫자를 고르는 게 최적의 선택이라고 확신할 수 있다.
# 최대곱 구하기
def max_product(card_lists):
max_card = 1
for card_list in card_lists :
max_card *= max(card_list)
return max_card코드잇-알고리즘패러다임 프로그래머스
