그리디(Greedy) 정리

'이것이 취업을 위한 코딩테스트다'를 읽고 정리한 내용입니다.

 

그리디(Greedy) : 현재 상황에서 지금 당장 좋은 것만 고르는 방법

 

 

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이기에 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같이 힌트를 제공!

---

예제 3-1 거스름돈

'가장 큰 화폐 단위부터' 돈을 거슬러 주는 것

n = 1260
count = 0
# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500,100,50,10]

for coin in coin_types:
    count += n//coin # 해당 화폐로 거슬러 줄 수 있는 동전 세기
    n %= coin
    
print(count)

 

가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

---

대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다!

 

'10원짜리로만 모두 거슬러줄 경우' -> '최적의 해x' -> '500원짜리부터 거슬러 가장 작은 10원짜리까지 차례대로 거슬러 준다면?' -> '거스름돈 문제에서는 큰 단위가 항상 작은 단위의 배수 형태이므로, 최적의 해 보장!'

 

화폐의 단위가 무작위로 주어진 경우에는 그리디 알고리즘으로 해결할 수 없다.

 

---

예제 3-2 큰 수의 법칙

def solution(n,m,k,num):
    num.sort(reverse=True)
    num_1 = num[0]
    num_2 = num[1]
    answer = num_1*k*(m//k) + num_2*(m%k)
    return answer
    
num = [2,4,5,4,6]
print(solution(5,8,3,num))

 

반복되는 수열에 대해서 파악!

{6,6,6,5}가 반복되며 반복되는 수열의 길이가 바로 (K+1)이다.

M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수가 된다.

 

M이 (K+1)로 나누어떨어지지 않는 경우:

M을 (K+1)로 나눈 나머지만큼 가장 큰 수가 추가로 더해지므로 이를 고려해주어야 한다.

 

가장 큰 숫자가 더해지는 횟수는 : (M//(K+1))*K+M%(K+1) = 반복되는 횟수*수열의 길이 + 나머지만큼 가장 큰수가 더해짐

 

[6,5,4,4,2], M=8, K=3일 경우 : (8//4)*3 + 8%4

6+6+6+5 + 6+6+6+5

 

[4,4,3,3,3], M=7, K=2일 경우 :

4+4 + 4+4 + 4+4 + 4 

def solution(n,m,k,num):
    num.sort(reverse=True)
    num_1 = num[0]
    num_2 = num[1]
    
    # 가장 큰 숫자가 더해지는 횟수
    first = (m//(k+1))*k + m%(k+1)
    second = m-first
    answer = num_1*first + second*num_2
    return answer

 

---

예제 3-3 숫자 카드 게임

각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾기!

 

1) 이중반복문을 쓰지 않을 경우

num = [[3,1,2],[4,1,4],[2,2,2]]
print(num)

def solution(n,m,num):
    result = []
    for i in range(n): # 행마다 반복
        min_value = min(num[i])
        result.append(min_value)
    return max(result)

 

2) 이중반복문 쓸 경우

def solution(n,m,num):
    result = []
    for i in range(n):
        for j in num:
            min_value = min(j)
            result.append(min_value)
    return max(result)

 

---

예제 3-4 1이 될 때까지

 

def solution(n,k):
    answer = 0
    while n!=1:
        if n%k!=0:
            n = n-1
            answer += 1
        else:
            n = n//k
            answer += 1
    return answer

 

N이 매우 큰 수일 경우 빠르게 동작하기 위해서는 N이 K의 배수가 되도록 효율적으로 한번에 빼는 방식이 필요.

def solution(n,k):
    result = 0
    while True:
        
        # n==k로 나누어떨어지는 수가 될 때까지 1씩 빼기
        target = (n//k)*k # 24
        result += (n-target) # 1
        n = target 
        
        # n이 k보다 작을 때 반복분 탈출
        if n<k:
            break
        result += 1 # 2
        n //= k # 8
        
    # 마지막으로 남은 수에 대하여 1씩 빼기    
    result += (n-1)
    return result

 

---

Q1. 모험가 길드 : N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹의 최댓값을 구하는 프로그램 작성하기.

공포도를 오름차순으로 정렬해서 순서대로 그룹을 묶는다.

 

why?

• 공포도가 오름차순으로 정렬되어 있다면 그룹을 편성할 때 이미 그룹에 포함되어 있는 인원은 생각하지 않아도 된다.
• 최소한의 모험가의 수만으로 그룹이 편성된다.
• 최소한의 인원으로 그룹을 만들어야 그룹의 수도 최대가 된다.

num = [2,3,1,2,2]

def solution(n, num):
    num.sort()
    result = 0
    count = 0
    
    for i in num:
        count += 1
        if count >= i:
            result += 1
            count = 0
            
    return result

 

i=1일 때, count=1이라서 result +1, count = 0

i=2일 때, count=1이라서 count +1

i=2일 때, count=2라서 result +1, count=0

---

---

Q2. 곱하기 혹은 더하기 : 두 수에 대하여 연산을 수행할 때, 두 수 중에서 하나라도 1 이하인 경우에는 더하며, 두 수가 모두 2 이상인 경우에는 곱하면 된다.

 

def solution(s):
    num = []
    for i in range(len(s)):
        num.append(int(s[i]))
        
    answer = num[0]
    for j in range(1,len(num)):
        if num[j]<=1 or answer<=1:
            answer += num[j]
        else:
            answer *= num[j]
            
    return answer

 

---

Q3. 문자열 뒤집기 : 전부 0으로 바꾸는 경우와 전부 1로 바꾸는 경우 중에서 더 적은 수를 가지는 경우를 계산

 

def solution(s):
    
    count_0 = 0
    count_1 = 0

    # 첫 번째 원소
    if s[0]=='1':
        count_0 += 1
    else:
        count_1 += 1
    
    # 모두 0으로 바꾸는 경우
    for i in range(len(s)-1):
        if s[i] != s[i+1]:
            if s[i+1]=='1':
                count_0 += 1
            else:
                count_1 += 1
    return min(count_0, count_1)

 

---

Q4. 만들 수 없는 금액 : 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램

 

coin_types = [1,2,3,8]

 

step 0 : 처음에는 금액 1을 만들 수 있는지 확인하기 위해 target = 1로 설정한다.

step 1 : target = 1을 만족할 수 있는 지 확인한다. 화폐 단위가 1인 동전이 있기에 이 동전을 이용해서 금액 1을 만들 수 있다. 이어서 target = 1+1 =2로 업데이트를 한다. (1까지의 모든 금액을 만들 수 있다는 말과 같다.)

step 2 : target = 2를 만족할 수 있는지 확인한다. 화폐 단위가 2인 동전이 있다. 따라서 target = 2+2 = 4가 된다. (3까지의 모든 금액을 만들 수 있다는 말과 같다.)

step 3 : target = 4를 만족할 수 있는지 확인한다. 3인 동전이 있기에 target = 4+3 = 7이 된다.(6까지의 모든 금액을 만들 수 있다는 말과 같다.)

step 4 : target = 7을 만족할 수 있는지 확인한다. 이보다 큰 화폐 단위가 8인 동전이 있기에 따라서 금액 7을 만드는 방법은 없다.

def solution(n, coin_types):
    coin_types.sort()
    answer = 1
    for i in coin_types:
        if answer < i:
            break
        answer += i
    return answer

 

---

Q5. 볼링공 고르기

 

내가 푼 코드 : 

def solution(n,m,ball):
    answer = 0
    for i in range(len(ball)-1):
        for j in range(i+1,len(ball)):
            if ball[i]!=ball[j]:
                answer += 1
            
    return answer

 

내가 푼 코드 2(24.03.28) :

from collections import deque
def solution(data):
    queue = deque([i, ball] for i, ball in enumerate(data))
    answer = 0
    while queue:
        q = queue.popleft()
        for i in queue:
            if q[1] != i[1]:
                answer += 1
    return answer

 

이렇게 하면 n과 m 없이 풀 수 있지만 두 코드 모두 시간 복잡도가 O(N^2)이 된다.

 

동빈나님 코드 : 

def solution(n, m, ball):
    array = [0]*11

    for x in ball:
        array[x] += 1

    result = 0
    for i in range(1, m+1):
        n -= array[i]
        result += array[i] * n
    
    print(result)

 

1) 문제에 1부터 10까지의 볼링공 무게가 있다고 했기 때문에 array로 무게 리스트를 만든다.

2) array에 ball에 있는 무게들을 추가하여 무게 몇 개수를 확인!

3) 전체 개수 n에서 특정 무게 개수를 빼고 남은 볼링공과 곱하면 된다!

 

무게마다 볼링공이 몇 개 있는지를 계산해야 한다.

• 무게가 1인 볼링공 : 1개
• 무게가 2인 볼링공 : 2개
• 무게가 3인 볼링공 : 2개

이 때 A가 특정한 무게의 볼링공을 선택했을 때, 이어서 B가 볼링공을 선택하는 경우를 차례대로 계산하여 문제를 해결할 수 있다. A를 기준으로 무게가 낮은 볼링공부터 무게가 높은 볼링공까지 순서대로 하나씩 확인을 한다고 했을 때 다음과 같다.

step 1 : A가 무게가 1인 공을 선택할 때의 경우의 수는

 1(무게가 1인 공의 개수) X 4(B가 선택하는 경우의 수) = 4가지

step 2 : A가 무게가 2인 공을 선택할 때의경우의 수는

 2(무게가 2인 공의 개수) X 2(B가 선택하는 경우의 수) = 4가지 

step 3 : A가 무게가 3인 공을 선택할 때의 경우의 수는

 2(무게가 3인 공의 개수) X 0(B가 선택하는 경우의 수) = 0가지

 

단계가 진행됨에 따라 'B가 선택하는 경우의 수'는 줄어드는데, 이미 계산했던 경우(조합)는제외하기 때문.

또한, 볼링공의 무게가 1부터 10까지만 존재할 수 있다고 명시되어 있다. 따라서 하나의 리스트 변수를 선언해서, 각 무게별로 볼링공이 몇 개가 존재하는지 기록할 수 있다. 

---

Q6. 무지의 먹방 라이브

 

내가 푼 코드 :

def solution(food_times, k):
    result = 0
    time = 0
    while time>k:
        for i in range(len(food_times)):
            if food_times[i]!=0:
                food_times[i] = foold_times[i]-1
                time +=1
            else:
                food_times[::-1] = food
    result = time%len(food_times)+1
    return result

 

이렇게 풀었지만 책에 나와있는 

food_times=[8,6,4], K=15일 경우 틀린다.