Greedy

JeongChaeJin·2022년 10월 4일

이것이 취업을 위한 코딩 테스트다 with 파이썬

목록 보기

1/10

현재 상황에서 가장 좋아보이는 것만 선택하는 알고리즘
그리디 알고리즘의 정당성을 고민하면서 문제 해결 방안을 떠올려야 한다.
- 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적 해를 구할 수 있는지를 검토 !!
- 최적해를 보장할 수 없을 때가 많다. 하지만, 코테는 탐욕법으로 얻은해가 최적해가 되는 상황에서 이를 추론할 수 있는지를 확인한다.

거스름돈

n = 1260
count = 0

array = [500, 100, 50, 10]

for coin in array:
	count += n // coin
    n %= coin
    
print(count)

Time Complexity : O(K) => 화폐 총 종류만 영향을 미침
거스름돈: 정당성 분석 예제에서 가장 큰 화폐 단위부터 돈을 거슬러주는 것이 최적해를 보장하는 이유는 ?
- 가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수이기 때문에 작은 단위 동전들을 종합해 다른 해가 나올 수 없기 때문이다.
- 800원을 거슬러 주기 위해 화폐 단위가 500, 400, 100 이라면 400원 2개를 거슬러주는 것이 최적해인데, 500원부터 거슬러주면 500원 1개, 100원 3개인 총 4개를 거슬러줘야 된다. 큰 단위 화폐가 작은 단위 화폐의 배수가 아니기 때문에 그리디 알고리즘이 최적해를 갖지 못하는 것이다.
그리디 알고리즘은 최소한의 아이디어를 떠올리고 이것이 정당한가?를 검토할 수 있어야한다.

1이 될 때까지

n, k = map(int, input().split())
result = 0
while True:
	# N이 K로 나누어 떨어지는 수가 될때까지 빼기
	target = (n // k) * k # 나누어 지는 수 target 만들기
    result += (n - target) # 1을 빼야되는 경우를 한번에 더해버리기
    n = target
    
    # N이 K보다 작으면 더 이상 나눌 수 없으므로 반복문 탈출
    if n < k:
    	break
    
    # 1을 빼야되는 경우를 모두 더해버렸으므로 나누는 연산 경우에 대해서만 더해주고
    # n을 나눌 수 있는 수로 만들어버리기
	result += 1
    n //= k

# 마지막 남은 수에 대해 1씩 빼기
# n-1인 이유는 1을 남겨야하기 때문이다. n이 0일 때에는 모두 빼버린 것이므로, -1로 1을 살려주는 것으로 보면된다.
result += (n-1)
print(result)

n, k가 매우 큰 수더라도 빠르게 처리할 수 있다.

Ex1) 모험가 길드

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

data.sort()
count = 0
result = 0

for i in data:
    count += 1
    if count >= i:
        result += 1
        count = 0

print(result)

Ex2) 곱하기 혹은 더하기

n = input()

result = ''
for number in n:
    result += number
    if number == '0':
        result += '+'
    else:
        result += '*'

result = eval(result[:-1])
print(result)

Reference

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)

Ex3)문자열 뒤집기

n = input()

count_0 = 0
count_1 = 0

prev = n[0]
for i in range(1, len(n)):
    if n[i] == prev and n[i] == '0':
        count_0 += 1
    elif n[i] == prev and n[i] == '1':
        count_1 += 1

    prev = n[i]


result = min(count_0, count_1)
print(result)

Reference

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으로 바뀌는 경우
        else:
            count1 += 1

print(min(count0, count1))

좀 더 세련된 코드 같다.
index만 사용해서 Space Complexity가 더 적다.

Ex4) 만들 수 없는 금액

Reference

N = 5
data = [3, 2, 1, 1, 9]

data.sort()
target = 1
for i in data:
    if target < i:
        break

    target += i

print(target)

정렬을 이용한 그리디 알고리즘
현재 상태를 1 ~ target - 1 까지 모든 금액을 만들 수 있다고 가정한다.
- 화폐 단위가 작은 순서대로 동전을 확인하며 현재 확인하는 동전으로 target 금액을 만들 수 있는지 확인한다.
- 만들 수 있다면 target을 update 한다. 만들 수 있다는 뜻은 현재 확인하는 coin의 화폐가 target이하 라는 뜻이다.

Ex5) 볼링공 고르기

Reference

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

array = [0] * 11
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)