이코테 CHAPTER 03 그리디 정리 및 실전 문제(큰 수의 법칙)

당장 좋은 것만 선택하는 그리디

• 그리디 알고리즘(탐욕법)
  • 현재 상황에서 지금 당장 좋은 것만 고르는 방법
  • 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함
  • 그리디 해법은 그 정당성 분석이 중요
    • 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토

 

• 예시
  • 최적의 해를 보장하지 못함

 

 

 

• 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많음
• 하지만 코테에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됨

 

<문제> 거스름 돈

• 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다.
• N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다.
  • 그다음 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 준다.
• 정당성 분석 : 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유?
  • 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.
  • 반례: 800원을 거슬러 줘야 하는데, 화폐 단위가 500원, 400원, 100원인 경우

• 시간 복잡도 분석
  • 화폐의 종류가 K개라고 할 때 위 소스코드의 시간 복잡도는 O(K)
  • 이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야하는 금액의 크기와는 무관하다

 

•  

 

n = 1260
count = 0

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

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

print(count)​

 

 

큰 수의 법칙

'큰 수의 법칙'은 일반적으로 통계 분야에서 다루어지는 내용이지만 동빈이는 본인만의 방식으로 다르게 사용하고 있다. 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오.

 

• 나의 풀이

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

numbers.sort(reverse=True)

max = numbers[0]
cnt = numbers.count(max)

result = 0
if cnt>1:
    result = max*m
else: 
    while m>0:
        for i in range(k):
            result += max
            m -= 1
            print(result,m)
            if m <=0 :
                break
        if m>0:
            result += numbers[cnt]
            m -= 1

print(result)

- while 문의 TRUE 조건을 잘 활용하자.. m 범위 때문에 헷갈림,,

   - if m == 0 조건을 for 문 맨 앞에 배치하면 뒤에 배치하는 것보다 쉽게 반복문 탈출 가능

- 두번째로 큰 수가 가장 큰 수와 같은지 여부와 상관 없이 while문 하나로도 풀 수 있다.

- 그리고 두번째 답안 예시처럼 수열을 파악해서 풀 수 있는 문제인지 확인하자.

 

• 답안 예시 코드(단순하게 푸는 버전)

# N, M, K를 공백으로 구분하여 입력받기
n, m, k = map(int, input().split())
# N개의 수를 공백으로 구분하여 입력받기
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: # m이 0이라면 반복문 탈출
            break
        result += first
        m -= 1 # 더할 때마다 1 씩 빼기
    if m == 0: # m이 0이라면 반복문 탈출
        break
    result += second # 두 번째로 큰 수를 한 번 더하기
    m -= 1 # 더할 때마다 1 씩 빼기

print(result) # 최종 답안 출력

 

• 답안 예시 코드(반복되는 수열 파악하기)

# N, M, K를 공백으로 구분하여 입력받기
n, m, k = map(int, input().split())
# N개의 수를 공백으로 구분하여 입력받기
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) # 최종 답안 출력

 

 

 

Reference

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저