[Python] 그리디

# 그리디 알고리즘

• 현재 상황에서 당장 좋은 것만 고르는 방법
• 다양한 유형의 문제가 있다.
• 가장 큰 순서/작은 순서대로와 같은 기준의 정렬 알고리즘에서 많이 사용

 

# 예제

1. 거스름돈 문제

- 가지고 있는 동전 중(500, 100, 50, 10)에서 가장 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전을 종합하여 다른 해가 나올 수 없다.

-  만약 동전의 단위가 (500, 400, 100)이 되는 경우 그리디 X

- 그리디 알고리즘은 문제 풀이를 위한 아이디어를 떠올리고 정당한지 검토할 수 있어야 답을 도출할 수 있다.

n = 1260
count = 0

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

for coin in coin_types:
    count += n //coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin # 거슬러준 후 남은 금액
    
print(count)

 

2. 큰 수의 법칙

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

- 입력받은 수의 가장 큰 수와 두번 째로 큰 수를 저장한 후 큰 수 3번 + 다음 큰 수 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)

 

3. 숫자 카드 게임

- N x M 개의 카드에서 가장 높은 숫자 카드를 뽑는다. 단, 하나의 행을 선택한 후 행에서 가장 낮은 숫자를 뽑아야 한다.

- 단순히 각 행마다 가장 작은 수를 찾은 뒤 그 중에서 가장 큰 수를 뽑는다.

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

result = 0
# 한 줄씩 입력받아 확인
for i in range(n):
	data = list(map(int, input().split()))
    # 현재 줄에서 가장 작은 수 찾기
    min_value = min(data)
    # 가장 작은 수들 중에서 가장 큰 수 찾기
    result = max(result, min_value)
    
print(result)

 

4. 1이 될때까지

- N과 K를 입력받는다. N에서 1을 빼거나 K로 나누는 연산을 반복해 N을 1로 만든다. 최소 연산 횟수 구하기.

- K가 2 이상의 자연수 이므로 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)

 

 

---

# 백준 풀이

https://www.acmicpc.net/problem/1026

1026번: 보물

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
count = 0

a.sort(reverse=True) # 작은 값을 만드므로 a는 역순 정렬렬
b2 = sorted(b)
i=0
    
while (i<n):
    for j in range(0, n):
        if (b2[i]==b[j]): # b가 작은 값이면(작은 수부터 비교교)
            count += a[i]*b2[i]
            i+=1
            break

print(count)

 

 

https://www.acmicpc.net/problem/2217

2217번: 로프

n = int(input())
array=[]
result=[]

for i in range(n):
    array.append(int(input()))
    
array.sort(reverse=True)

for i in range(n):
    result.append(array[i]*(i+1))

print(max(result))

- 단순히 (루프의 개수 * 가장 작은 견딜 수 있는 무게)로 풀 수 있을 것 같았는데 루프를 전부 사용하지 않아도 된다는 조건때문에 틀렸다.

 

https://www.acmicpc.net/problem/1789

1789번: 수들의 합

n = int(input())
total = 0
cnt = 0

while True: 
    cnt += 1
    total += cnt
    if total > n:
        break
    
print(cnt-1)

- 규칙이 존재한다. i가 1부터 N까지일 때, K=X에서 K는 X<=S(n)<=X+1 을 만족한다.

- 그냥 n까지 더하다가 n보다 크면 그 직전값이 정답이다.

 

---

# 회고 

 

코테 공부를 어떻게 해야할지 모르겠다.

그냥 무작정 풀어보면 되려나...? 일단 알고리즘 별로 감을 잡고 단계별로 문제를 풀기로 함.