[이코테] 그리디(탐욕법) 알고리즘

728x90

그리디 알고리즘(Greedy Algorithm)

어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘
즉, 현재 상황에서 지금 당장 좋은 것만 고르는 방법
코딩테스트에서 문제 유형을 파악하기 어렵다면 먼저 그리디 알고리즘을 의심

거스름돈

문제

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

내 풀이

n = int(input())
answer = 0
lst = [500, 100, 50, 10]

for i in lst:
  answer += n // i
  n %= i

print(answer)

# 1260
# 6

시간 복잡도

화폐의 종류가 K개라고 할 때 위 코드의 시간 복잡도는 O(K)이다. 즉, 거슬러 주어야 할 돈 N은 시간 복잡도와 무관하다.

그리디 알고리즘의 정당성

그리디 알고리즘을 통해 문제를 해결한 경우에는 해당 방법이 정당한지 검토하는 과정을 거쳐야 한다.

거스름돈 문제를 그리디 알고리즘으로 해결할 수 있었던 이유는 갖고 있는 동전 중 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

큰 수의 법칙

문제

'큰 수의 법칙'이란 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

ex) 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M = 8, K = 3이면

인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5인 46

단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주

ex) 3, 4, 3, 4, 3으로 이루어진 배열은 두 번째 4와 네 번째 4를 번갈아 사용 가능

풀이

# N: 배열의 크기, M: 숫자가 더해지는 횟수, K: 최대한 쓸 수 있는
N, M, K = map(int,input().split())
data = list(map(int,input().split()))

data.sort()             # 리스트 정렬
first = data[N - 1]     # 첫 번째 큰 수
second = data[N - 2]    # 두 번째 큰 수

result = 0

while True:
    for i in range(K): # 가장 큰 수를 K번 더하기
        if M == 0:
            break
        result += first
        M -= 1          # 더할 숫자의 횟수를 하나씩 줄여가는 역할
    if M == 0:
        break
    result += second
    M -= 1

print(result)

만약 M의 값이 커진다면 TimeOut이 될 수 있다.

더 효율적인 풀이

반복되는 수열의 길이 = (K+1)
M을 (K+1)로 나눈 몫 = 반복되는 횟수
나누어 떨어지지 않는 경우
- int(M / (K + 1)) * K + M % (K + 1)
- 가장 큰수가 더해지는 횟수를 구한 다음 이를 이용해 두번째로 큰수가 더해지는 횟수까지 구할 수 있다.

N, M, K = map(int,input().split())
data = list(map(int,input().split()))

data.sort()             # 리스트 정렬
first = data[N - 1]     # 첫 번째 큰 수
second = data[N - 2]

# 가장 큰 수가 더해지는 횟수 계산
count = int(M / (K + 1)) * K
count += M % (K + 1)

result = 0
result += (count) * first   # 가장 큰 수더하기
result += (M - count) * second  # 두 번째로 큰 수 더하기

print(result)

1. 모험가 길드

#모험가길드
N = int(input())
data = list(map(int,input().split()))
data.sort()

group_cnt = 0     # 그룹 수
traveler = 0     # 현재까지 확인한 모험가의 수

for i in data:
    traveler += 1
    if traveler >= i:
        group_cnt += 1  # 그룹 수
        traveler = 0    # 초기화 후 반복

print(group_cnt)

traveler에 1을 더하여 현재까지 확인한 모험가의 수를 업데이트
만약 traveler가 현재 확인한 모험가의 공포도보다 크거나 같다면, 이 모험가를 포함한 그룹을 만들 수 있으므로 group_cnt를 1 증가시키고, traveler를 0으로 초기화하여 다음 그룹을 위한 준비
반복문이 끝나면 최대 그룹 수인 group_cnt를 출력

2. 곱하기 혹은 더하기

내 풀이

S = list(map(int, input()))

nums = 1
for num in S:
    if num == 0 or num == 1:
        nums += num 
    else:
        nums *= num
        
print(nums)

0과 1인 경우를 제외하면 곱하기가 유리
- ex) 129이면 (1+2)*9 = 27, 1*2*9 = 18
곱하기 할 경우를 생각해 nums를 0이 아닌 1로 지정

정답

data = input()

result = int(data[0])

for i in range(1, len(data)):
  num = int(data[i])
  if num <= 1 or result <= 1:
    result += num
  else:
    result *= num

print(result)

3. 만들 수 없는 금액

정답

N = int(input())
nums = list(map(int, input().split()))
nums.sort()  

target = 1
for num in nums:
    if target >= num:
        target += num

print(target)

만들 수 있는 최솟값인 1을 target에 선
target보다 다음 동전의 금액이 작거나 같다면, target에 그 동전의 금액을 더하기
만약 target보다 다음 동전의 금액이 크다면, target이 만들 수 없는 최소 금액

4. 볼링공 고르기

정답

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

array = [1
  ] * 10  # 각 무게의 볼링공이 몇 개 있는지를 카운트하는 리스트를 생성( 배열 )

for x in data:

    array[x] += 1   # 입력받은 볼링공의 무게를 기준으로 무게별로 카운트

result = 0 # 결과 초기화

for i in range(1, m+1):
    n -= array[i]   # 선택할 수 있는 볼링공의 수는 현재 총 볼링공의 수에서 현재 무게의 볼링공의 수를 뺀 값
    result += array[i] * n # 현재 무게의 볼링공을 선택할 경우, 다른 무게의 볼링공과의 조합 수를 곱해서 결과에 더한다

print(result)

다른 방법

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

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

result = 0

for i, j in enumerate(K):
  for k in K[i+1:]:
    if j == k:
      continue
    else:
      result += 1

print(result)

[출처] 이코테 파트 3 파이썬 문제 풀이 및 내가 생각한 답, 05.볼링공 고르기|작성자 passgiant

enumerate를 사용해서 풀고 싶었는데 실패
다른 분 풀이 ver

참고 교재, 영상

https://www.youtube.com/watch?v=_IZuE7NIeW4