알고리즘 이론 - 그리디 알고리즘

그리디 알고리즘

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 단순히 가장 좋아보이는 것을 반복적으로 선택해도 답을 구할 수 있을지 확인함.

ex) 루트 노드 1부터 거쳐간 노드의 합을 최대로 만들어라.

• 단순히 한 눈에 봐도 좋아보이는 1 3 7을 거쳐 11이라는 답을 낼 수 있다.

그러나!

• 그리디는 1에서 2, 3 두 수 중에 큰 값을 고르고, 6, 7중에 또 다시 큰 값을 고른다. 즉, 현재 상황에서 고를 수 있는 최선의 수를 고르는 방법이다. 문제에서 요구한 답과는 결과 값이 같을 수도 있고, 다를 수도 있는 것이다. 그러니, 문제를 유심히 분석해봐야한다.

• 대표적으로 거스름돈을 최소의 동전의 개수로 거슬러주는 문제를 예를 들 수 있다.
  500원, 100원, 50원, 10원을 가지고 있을 때, 선택할 수 있는 가장 큰 500원부터 주는게 동전의 개수를 최소화하는 방법이다.
• 만약 1250원을 거슬러준다면, 500원 X 2 + 100원 X 2 + 50원 X1 총 5개의 동전이 최소 개수이다.

  그리고 반례로는 1200원을 거슬러 줘야하는데 500원, 400원, 100원의 단위라면? 500X2 + 100X2가 아닌 400X3이 답이므로 그리디 알고리즘으로 풀 수 없다.

#거스름돈 그리디 구현

n = 1260
count = 0

arr = [500, 100, 50, 10]

for coin in arr:
    count +=n //coin
    n %= coin # 가장 큰 coin부터 모두 사용하므로 coin보다 무조건 작아야만 한다.

print(count)

• 위의 코드에서 보면 arr의 원소의 개수 4개만큼만 반복이 수행되므로 N이 arr원소의 개수라고 할 때, 시간복잡도는 O(N)이다.

Example1

• 1이 될때까지

#1이 될 때까지 아래를 수행한다.
#N과 K가 공백 단위로 입력되고, N이 1이 될 때까지
#1. N에서 -1
#2. N에서 K를 나눔.
#이 과정의 최소값을 구해야함.

N, K = map(int, input().split())
count = 0 # 횟수를 저장
while True:
    if N % K == 0:
        N //= K
        count +=1
    else:
        N -= 1
        count +=1
    
    if N < K:
        break

print(count)

Example2

• 곱하기 또는 더하기

#곱하기 혹은 더하기
#각자릿수가 0~9로 이루어진 문자열 S입력
#각 숫자들 사이에 + 나 *를 넣어 가장 큰 수를 만들자.
#모든 연산은 왼쪽부터 순차적으로 이루어진다.

#풀이 ->극단적으로 0122313이면 1 * 2 보다는 1+2가 더 커지므로 result 값이 0, 1이 나오면 더하기
S = input()
result = 0 #결과를 저장할 result 변수
for i in S:
    if int(i) == 1 or int(i) == 0 or result == 0 or result == 1:
        result += int(i)
    else:
        result *= int(i)

print(result)

Example3

• 모험가 길드

#최대 몇 개의 그룹을 만들 수 있을까?
#모험가 N명과 N이하의 자연수를 두 번째 줄에 각 모험가의 공포도의 값을 공백 단위로 입력.

#풀이 -> 공포도가 높을수록 사람을 많이 요구하므로 공포도가 높은 사람부터 계산 (그리디 알고리즘)
''' 1. 모험가 수를 0부터 시작해주지 않아 복잡해짐.
N = int(input())

num_fear = list(map(int, input().split()))#N명 만큼 모험가의 공포도를 입력받음

sorted_fear = sorted(num_fear) # 오름차순 정렬
people_left = N #people_left가 0이 되거나 그 이하면 그룹을 만들 수 없음.
count = 0
for i in sorted_fear:
    if people_left <=0:
        print(count-1)
        break
    else:
        people_left = people_left - i # i는 공포도이므로 사람 수만큼 빼준다.
        count +=1 # 그룹 1개 생성. 
'''
#2. 모범답안
N = int(input())

data = list(map(int, input().split()))
data.sort()

result = 0 #그룹의 수
count = 0 #현재 그룹에 포함된 모험가의 수

for i in data: #공포도를 낮은 순으로 확인하며, 공포도보다 모험가 수가 같거나 많다면, 그룹의 수를 +1하고 현재 그룹원을 0으로 초기화.
    count += 1
    if count >= i:
        result += 1
        count = 0
print(result)