대기업 코딩테스트 준비 2 : 그리디

https://github.com/ndb796/python-for-coding-test

• 해당 내용을 보고 정리한 글임

  그리디

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

• 정렬과 자주 사용된다.

  거스름돈

  대부분의 문제는 그리디 알고리즘으로 최적해를 찾을 수 없음

coin_types = [500,100,50,0] for coin in coin_types: count += n // coin n %= coin print(count)

• 탐욕적으로 답을 찾을 수 있다는 보장이 있어야 함.

• 큰 단위가 가장 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없음

• 무작위면 불가능

큰 수의 법칙

• 주어진 수를 연속 사용 가능하게 M번 더하여 가장 큰 수를 만드는 법

• 특정 인덱스에 해당하는 수가 K이상 쓸 수 없음

  • 제일큰 2개 갖고 만들기

 # `int(M / (K + 1)) \* K + M % (K + 1)`
# 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) # 최종 답안 출력

1이 될 때까지

• N이 K의 배수가 될 때까지 1씩 빼기
• N을 K로 나누기
  • 최대한 많이 나누기
  • 1 빼는 횟수
    • target = (n//k)*k
    • result += (n-target)
    • n = target

# N, K공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())

result = 0

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
    target = (n // k) * k
    result += (n - target)
    n = target
    # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
        break
    # K로 나누기
    result += 1
    n //= k

# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)

실전 문제 풀이

• 현재 상황에서 가장 좋은 선택
  • 다익스트라 최단 경로
    • 그리디 + 다이나믹
  • 크루스칼

모험가 길드

• 공포도 오름차순 정렬 시 3 1 있으면 1 못보냄
• 내림차순이 적절하다.

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) # 총 그룹의 수 출력

곱하기 혹은 더하기

• 하나의 수가 (input or result) 1 이하이면 더하기
• 아니면 곱하기

data = input()

# 첫 번째 문자를 숫자로 변경하여 대입
result = int(data[0])

for i in range(1, len(data)):
    # 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행
    num = int(data[i])
    if num <= 1 or result <= 1:
        result += num
    else:
        result *= num

print(result)

문자열 뒤집기

• 진입점만 check

data = input()
count0 = 0 # 전부 0으로 바꾸는 경우
count1 = 0 # 전부 1로 바꾸는 경우

# 첫 번째 원소에 대해서 처리
if data[0] == '1':
    count0 += 1
else:
    count1 += 1

# 두 번째 원소부터 모든 원소를 확인하며
for i in range(len(data) - 1):
    if data[i] != data[i + 1]: # 진입점만 체크해준다~
        # 다음 수에서 1로 바뀌는 경우
        if data[i + 1] == '1':
            count0 += 1 # 0으로 바꾸기 +1
        # 다음 수에서 0으로 바뀌는 경우
        else:
            count1 += 1

print(min(count0, count1))

만들 수 없는 금액

• 1부터 target-1 까지 만들 수 있음
  • 매번 target인 금액도 만들 수 있는지? (현재 확인하는 동전의 단위가 target 이하인지)

target = 1
for x in data:
    # 만들 수 없는 금액을 찾았을 때 반복 종료
    if target < x:
        break
    # x <=target
    target += x
    # target이 7이면 6까지는 다 만들 수 있다는 의미

볼링공 고르기

• 무게마다 몇 개의 볼링공이 있는지를 계산해야 한다
  • 서로 다른 무게의 볼링공
  • 오름차순 소거법

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

# 1부터 10까지의 무게를 담을 수 있는 리스트
array = [0] * 11

for x in data:
    # 각 무게에 해당하는 볼링공의 개수 카운트
    array[x] += 1

result = 0
# 1부터 m까지의 각 무게에 대하여 처리
for i in range(1, m + 1):
    n -= array[i] # 무게가 i인 볼링공의 개수(A가 선택할 수 있는 개수) 제외
    result += array[i] * n # B가 선택하는 경우의 수와 곱해주기

print(result)

무지의 먹방 라이브

• 모든 음식을 시간 기준 정렬
  • 시간이 적게 걸리는 음식부터 제거
  • 우선순위 큐
  • (음식 시간, 음식 번호)
• 이동시간과 남은 시간 고려

import heapq

def solution(food_times, k):
    # 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
    if sum(food_times) <= k:
        return -1

    # 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
    q = []
    for i in range(len(food_times)):
        # (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
        heapq.heappush(q, (food_times[i], i + 1))  

    sum_value = 0 # 먹기 위해 사용한 시간
    previous = 0 # 직전에 다 먹은 음식 시간
    length = len(food_times) # 남은 음식의 개수

    # sum_value + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
    while sum_value + ((q[0][0] - previous) * length) <= k:
        now = heapq.heappop(q)[0]
        sum_value += (now - previous) * length # 6에서 이전 음식 4를 빼준 것 * 음식 갯수
        length -= 1 # 다 먹은 음식 제외
        previous = now # 이전 음식 시간 재설정

    # 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
    result = sorted(q, key=lambda x: x[1]) # 음식의 번호 기준으로 정렬
    return result[(k - sum_value) % length][1]