그리디

그리디

• 특징: 가장 간단하면서 좋아보이는 것만 파악하게 하도록 루트를 짜게 함, 최적의 해 명시, 즉 더 좋은 다른 해가 나올 수 없음

• 문제 속 포인트: "가장 큰 순서대로" , "가장 작은 순서대로" 같은 기준을 제시한다.

예제 3-1 거스름돈

• 문제 포인트: 거스름돈 줄 수 있는 최소 동전의 개수

• 문제 핵심: 가장 큰 화폐단위 부터준다.

• 시간복잡도: O(K)

• CODE

n = 1260 
count = 0 
# 큰 단위의 화폐부터 차례대로 확인 
coin_types = [500, 100, 50, 10] 
for coin in  coin_types:
	count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기 
	n %= coin 
print (count) 

큰 수의 법칙

• 해결: 배열로 나열된 수를 M번 더하여 만드는 것이지만, 해당 수(특정 인덱스 번호 해당)가 연속해서 K번 초과하여 더해질 수 없는 방식.

  • 가장 큰 수를 최대 K번 더하고 두 번째 큰 수 더하고 다시 가장 큰 수 K번 더하기 반복

• CODE

• 핵심 식

  • 반복되는 수열의 횟수를 구할 수 있다.
  • 짝수로 나눠지면 앞에 것만 보지만 홀수로 되어서 안 나눠질 경우 나머지를 구하는 뒤의 식도 참고한다.

#3-2예제

# N:배열의 크기, M: 숫자가 더해지는 횟수, K가 주어짐
# 큰 수 법칙: 가장 큰 수 k번 더하고 두 번째로 큰 수 한 번 더하는 방식을 반복하면된다.(반복되는 수열)
# idea: 가장 큰 수 몇 번 더하는 지 식세우기, 반복되는 수열의 모양과 횟수 구하기

# 입력: 5 8 3
# 입력: 2 4 5 4 6
import collections

N , M, K =map(int,input().split()) #입력 조건 1번

figure = list(map(int,input().split())) # 입력조건 2번

figure.sort() # 입력조건 3번

first = figure[N - 1] # 가장 큰 수 (정렬 시 인덱스 번호가 앞일수록 크다. 내림차순)
second = figure[N - 2]# 두 번째로 큰 수(정렬 시 인덱스 번호가 앞일수록 크다. 내림차순)

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

count += M%(K+1) # 수열이 반복되는 횟수 나머지(만약 홀수이면)

result = 0 # 시작은 0

result += (count) * first # 가장 큰 수 더하기

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

print(figure) # 46

숫자 카드게임

• 그리디 알고리즘 유형이다

• 각 행마다 가장 작은 수 찾은 후에 큰 수를 찾기

• Min()함수로 직관적으로 풀기

# 입력 3 3
# 입력 3 1 2
#      4 1 4
#      2 2 2
# for문으로 행렬 꼴의 형태로 만들기
# 카드 행 고르기
# 낮은 카드 뽑기( min()함수 이용)
# Main idea: 각 행마다 작은 숫자 찾은 후 그 중에서 큰 수 찾기
# 수의 정렬은 리스트한다.

N,M = map(int, input().split()) # 숫자 입력

result = 0 # 최종 답안을 위해서 만들어진 변수

for i in range(N): # 각 행 뽑기
    
    data = list(map(int,input().split())) # M* N으 들어갈 식
    
    minima = min(data)
    
    result = max(result, minima)
    
print(result) # 2

• 2중 반복문 구조로 풀기

# 입력: 2 4

#       7 3 1 8
#       3 3 3 4
# 2중 반복문 구조

# 처음엔 그냥 그대로 하다가 최고점을 잡아준다

# 다음엔, 최고점과 나온 값을 비교해서 구하기

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

results = 0

for i in range(n):
    
    datas = list(map(int,input().split()))
    
    min_value = 10001
    
    for j in datas:
        
        min_value = min(min_value,j)
        
    results = max(results, min_value)
        
print(results) # 3

1이 될 때까지

• 핵심: 최소 횟수 구하기

• 해결:

  • 그리디 알고리즘 이용
  • 최대한 많이 나누기(속도가 빠르다. 큰 수일수록 나누기가 유리)

• N -1 -> N / K (나뉘어떨어질 때만 사용가능) : 이 사이클의 반복

• CODE 1

N,K = map(int,input().split()) # 25 5

result = 0 # 횟수를 알려주는 결과

while N >= K: # N >= K 라면 K로 계속 나누기
    
    while N % K !=0: # 나누어 떨어지지 않으면 N-1
        N -=1
        result +=1
        
    N //=K 
    
    result +=1
    
while N >1: # 나누기는 못하고 빼야할 경우
    
    N -=1
    
    result +=1
    
print(result)

n,k = map(int,input().split())

result = 0

while True:
    
    figure = (n // k ) * k  # -1씩 빼야하는 횟수
    
    result += (n- figure)
    
    n = figure
    
    if n < k: # k보다 크면 종료
        break
        
    result +=1
    
    n //= k # 나누기
    
    
result += (n-1)


print(result)