Greedy

* intro

"현재 상황에서 지금 당장 좋은 것만 고르는 방법"

 

→ 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 적절히 떠오르면 풀리는 경우 많음

→ 단순히 가장 좋아보이는 걸 반복적으로 선택해도 최적의 해를 구할 수 있는 지 검토하게 된다.

→ 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없는 경우가 많음

→ 하지만 코딩 테스트에서의 대부분 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 추론할 수 있어야 풀리게 출제

 

★ 주어진 문제를 모든 상황을 다 고려한 채로, 각 상황의 최적의 결과를 상황별로 계속 모으면, 그 결과가 곧 최적의 결과가 되는 유형이 greedy 유형

☆ 주의점: 문제의 모든 상황을 생각해야 하고 / 각 상황의 greedy한 솔루션을 알아내야 함.

* 대표 예제

ex1) 음식점 거스름돈)

Q. 음식점의 계산을 도와주는 점원이라 가정. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다 가정. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수 (N은 항상 10의 배수)

 

A. 탐욕법에 의해 최적의 해를 구할 수 있는 상황은 우선적으로, 500원 동전 먼저 사용. 그 다음 100원 - 50원 - 10원 순서로 거슬러 줄 수 있음

→ 정당성 보장? 큰 단위가 항상 작은 단위의 배수이기에 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문.

(예를 들면, 800원을 거슬러 주는 상황에서 화폐 단위가 500원, 400원, 100원이라면 위와 같은 알고리즘으로 최적의 해를 보장할 수 없음)

 

- code)

n = 1260
count = 0

array = [500, 100, 50, 10]

for coin in array:
    count += n//coin
    n %= coin

print(count) #6

 

- 분석)

→ 화폐의 종류가 K라면 시간복잡도는 O(K) (for문)
(즉, 금액 자체가 시간복잡도에 영향을 받지 않으며, 동전의 종류만 영향을 받는다.)

ex2) 1이 될 때까지)

Q. 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려 한다. 단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택 가능.

(1) N에서 1을 뺀다.

(2) N을 K로 나눈다.

 

→ 예를 들어 N이 17, K가 4라고 가정. 1번의 과정 한 번 수행하면 N은 16이 된다. 이후에 두 번 수행하면 N은 1. 결과적으로 전체 과정 실행 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수.

→ N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램 작성하기

 

→ 입력조건) 첫째 줄에 N(1이상 100,000이하), K(2이상 100,000이하)가 공백을 기준으로 하여 각각 자연수로 주어짐

→ 출력조건) 첫째 줄에 N이 1이 될때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값 출력

→ 예시) 입력 25 5 출력 2

 

A.

→ 탐욕법에 의해 최적의 상황인 'N에 대해 최대한 많이 나누기'를 선택 - 즉 (2)를 최대한 선택해야 횟수를 줄일 수 있음

→ 정당성 분석) 가능하면 최대한 많이 나누는 작업이 최적의 해 보장? K가 2 이상이라면 (1)보다 (2)를 통해 N을 빠르게 줄일 수 있다.

 

→ 내 풀이 O(N)

N, K = map(int, input().split())

cnt = 0

while N != 1:
    if N % K == 0:
        N //= K
        cnt += 1
    
    else:
        N -= 1
        cnt += 1

print(cnt)

 

- 시간복잡도 고려 풀이) O(logN)

N, K = map(int, input().split())

res = 0

while True:
    #N이 K로 나누어 떨어지는 수가 될 때까지 빼기

    target = (N//K)*K #N이 K로 나누어 떨어지지 않는다고 했을 때, 가장 가까운 K로 나누어 떨어지는 수 구해줌
    res += (N - target) #res는 1을 빼는 연산 횟수를 '한 번'에 수행해줌

    N = target
    if N < K:
        break

    #K로 나누기
    res += 1
    N //= K

res += (N-1) #마지막으로 남은 수 1씩 빼는 연산 횟수 포함
print(res)

 

→ 내 풀이는 N이 1이 될 때까지 if문을 돌며 계속 연산을 하는 code라 O(N)이지만, 그 다음 풀이의 경우, 몫의 연산 //을 수행해 1부터 N까지 전체를 일일이 점검을 하지 않는 code이므로 상대적으로 더 빠른 code라 할 수 있다. 시간복잡도는 O(logN)

ex3) 곱하기 혹은 더하기)

Q. 각 자리가 숫자(0~9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 x 혹은 + 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램 작성하기

(단, +보다 x를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다 가정)

(예를 들어 02984로 만들 수 있는 가장 큰 수는 ((((0+2)x9)x8)x4) = 576이다. 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어진다.)

 

A. 두 수 중 하나라도 적어도 0 또는 1이라면, 곱하기보다는 더하기를 수행하는 게 효율적. 2이상의 두 수라면 곱하기 수행

data = input()

res = int(data[0])

for i in range(1,len(data)):
    num = int(data[i])

    if num <= 1 or res <= 1:
        res += num
    
    else:
        res *= num

print(res)

ex4) 모험가 길드)

Q. 한 마을에 모험가가 N명 존재. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다. 모험가 길드장인 동번이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다. 동번이는 최대 몇 개의 모험가 그룹을 만들 수 있는 지 궁금하다. N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램

(예를 들어 N = 5이고, 각 모험가의 공포도가 2, 3, 1, 2, 2라면 그룹 1에 공포도가 1, 2, 3인 모험가를 한 명씩 넣고, 그룹 2에 공포도가 2인 남은 두 명을 넣어 총 2개의 그룹을 만든다. 또한 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에 모든 모험가를 특정 그룹에 넣을 필요는 없다)

 

※ 입력, 출력 조건과 입출력 예시 ※

 

A. 그리디 알고리즘에 의해 최대한 많은 그룹을 결성하려면 공포도가 제일 작은 사람부터 그룹에 묶어 나가며 그룹을 최대한 많이 만들어야 한다. 공포도가 작은 사람이 공포도가 높은 사람보다 우선적으로 그룹을 바로 만들 수 있기 때문에, 두 가지 상황 - 공포도가 높은 사람 / 낮은 사람 상황에서 우선적으로 공포도가 낮은 사람 먼저 grouping

 

★ 나는 거꾸로 공포도 최댓값부터 그룹을 묶었지만, 이럴 경우 greedy 알고리즘 논리에 위배되고, 여러 반례에 의해 최대 그룹 수를 못찾을 수 있다. (아래 내 code - 정답 아님)

N = int(input()) #1<= N <= 100,000

fears = list(map(int, input().split()))

fears.sort(reverse=True)
group = 0
print(fears)

while len(fears) != 0 :
    max_fear = fears[0]

    if len(fears) < max_fear:
        break

    del fears[:max_fear]

    group += 1


print(group)

 

★ 공포도 최솟값부터 grouping하되, 해당 group 내에 주어진 fear보다 큰 fear를 가진 사람이 있어서는 안된다. 즉 현재 그룹에 포함된 모험가의 수가 현재 확인하고 있는 fear보다 작으면 group 설정 x

 

★ 이코테 풀이> 당장의 starting point부터 조건을 세우며 data 전체 traverse

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

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

for i in data: #공포도를 낮은 것 부터 하나하나씩 확인!
    count += 1 #현재 그룹에 해당 모험가 포함시키기
    if count >= i: #현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
        result += 1 #총 그룹의 수 증가시키기
        count = 0 #현재 그룹에 포함된 모험가의 수 초기화

print(result) #총 그룹의 수 출력

---

* 출처 일부) 이코테 2021