Chapter 03 그리디

그리디 알고리즘 :  '현재 상황에서 지금 당장 좋은것만 고르는 방법'/ 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘

정렬 라이브러리의 사용방법 : 여러 개의 데이터를 빠르게 정렬해야 하는 문제

플로이드 워셜 : 다른 예시로 최단 경로를 빠르게 찾아야 하는 문제

다익스트라 알고리즘 : '암기'가 필요한 알고리즘으로 특정 알고리즘을 미리 알고 있거나, 팀 노트를 통해 준비해야하는 알고리즘

 

-> 코딩테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면, 그리디 알고리즘을 의심해보고 이 문제를 해결할 수 있는 탐욕적인 해결방법이 존재하는지 고민해보자.

---

예제 3-1 거스름돈

'가장 큰 화폐 단위부터' 돈을 거슬러 주는 것.

n = 1260
count = 0

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

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

print(count)

 

실전문제 2 큰수의 법칙

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]

result = 0

while True:
	for i in range(k): # 가장 큰 수 k번 더하기
    	if m == 0:
        	break
        result += first
        m -= 1
    if m == 0:
    	break
    result += second # 두번째로 큰 수 더하기
    m -= 1
    
print(result)

2) py 대표 답안 예시

# 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. 숫자 카드 게임

'각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수'를 찾는 것

1) py min() 함수를 이용하는 답안 예시

# N, 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 이 될 때까지

  1. N에서 1을 뺀다.

  2. N을 K로 나눈다.

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

# N이 K 이상이라면 K로 계속 나누기
while n >= k:
    while n % k != 0:
        # N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기
        n -= 1
        result += 1
    # K로 나누기
    n //= k
    result += 1

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

10만 이상일 경우, 효율적으로 한번에 빼는 방식을 고려해봐야함.

주의) 몇번 더 봐야함!

#효울적으로 빠르게 접근하는 방식
n, k = map(int, input().split())
result = 0

While True:
    # (N == K로 나누어떨어지는 수)가 될 때까지 1씩 빼기
    target = (n//k) * k
    result += (n - target)

    if n < k:
        break
    result += 1
    n //= k # // 연산자 : 몫 , % 연산자 : 나머지


result += (n -1)
print(result)