그리디 알고리즘

본문은 저자 나동빈님의 『이것이 취업을 위한 코딩테스트다 with 파이썬』 책을 공부하며 작성한 내용입니다. 글은 편의상 반말로 작성되었습니다.

최초 작성일 : 20.01.24
최종 수정일 : 20.01.30

개념

단순하지만 강력한 문제 해결 방법으로, 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다. 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해 고려하지 않는다.

특성

- 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형

- 매우 다양하게 출제되어 암기만으로 모든 문제를 잘 풀 수 없다.

- 특정 문제를 만났을 때 현재 상황에서 가장 좋아 보이는 것만 선택해도 문제를 풀 수 있는지 파악할 수 있어야 한다.

- 자주 정렬 알고리즘과 짝을 이뤄 출제

예제

1. 거스름돈

작성 코드

price = int(input())
A, B, C, D = 0, 0, 0, 0
if price / 500 > 0:
    A = int(price / 500)
    price %= 500
if price / 100 > 0:
    B = int(price / 100)
    price %= 100
if price / 50 > 0:
    C = int(price / 50)
    price %= 50
if price / 10 > 0:
    D = int(price / 10)
    price %= 10
print(A + B + C + D)

• 동전 종류에 따라 변수를 따로 지정해 동전 개수를 따로 저장
• 일일이 if문으로 하나하나 비교 후 실행

답안 예시

n = 1260
count = 0

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

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

print(count)

• list에 동전 종류를 순서대로 저장, 동전 개수는 한 가지 변수에 계속 저장
• list에 저장된 동전 종류를 순서대로 가져와 반복하여 바로 계산

피드백

1. // 연산자를 이용하면 나누기 연산의 정수 결과만 얻을 수 있음
2. list와 for문으로 원하는 단위를 순서대로 반복 계산
3. 단위별 변수를 따로 지정할 필요가 없음 (어차피 동전 총 개수를 구하는 것)
4. 직관적인 변수명은 코드 이해에 도움이 됨

2. 큰 수의 법칙

작성 코드

N, M, K = map(int, input().split(" "))
array = list(map(int, input().split(" ")))
sumNum = 0

array.sort(reverse=True)
for i in range(0, M):
    if i == 0 or i % K != 0:
        sumNum += array[0]
    else:
        sumNum += array[1]
print(sumNum)

• .sort()에서 reverse를 사용해 내림차순 정렬
• for문으로, i가 0부터 M까지 증가하면서 그 이상이 되면 for문이 끝나도록

답안 예시 (1)

M이 10,000 이하일 때

# 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: # m이 0이라면 반복문 탈출
        	break
        result += first
    	m -= 1 # 더할 때마다 1씩 빼기
    if m == 0: # m이 0이라면 반복문 탈출
    	break
    result += second # 두 번째로 큰 수를 한 번 더하기
    m -= 1 # 더할 때마다 1씩 빼기

print(result) # 최종 답안 출력

• .sort()로 오름차순 정렬하면 n값도 사용하여 코드를 작성할 수 있음
  (오름차순이기 때문에 전체 길이 n에서 -1, -2)
• 계산을 한 번 할 때마다 m에서 1씩 빼서 m이 0일 때 while문을 탈출하도록, m을 인덱스로 활용
• while 안에 가장 큰 수를 k번만큼 더하기 위해 for문 사용. 해당 for문이 끝나면 두 번째 큰 수를 더한 후 다시 for문으로

답안 예시 (2)

M이 100억 이상일 때

# 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) # 최종 답안 출력

• 반복되는 수열을 파악하여 코드 설계

* 정확히 이해되지 않아서 일단 넘어가고 다음에 다시 보기 *

  : 가장 큰 수가 더해지는 횟수를 구하는 것이 헷갈림(책 94p 체크한 부분) 

피드백

1. 입력 값을 공백으로 나눌 때는 .split(" ") 대신 .split() 사용 가능
2. 0부터 M까지 반복할 때는 range(0, M) 대신 range(M) 사용 가능
3. 가장 큰 수와 다음으로 큰 수를 변수에 저장하여 사용하면 더 보기 좋은 코드가 됨

3. 숫자 카드 게임

작성 코드

N, M = map(int, input().split())
array = []
result = 0

for _ in range(N):
    a = list(map(int, input().split()))
    array.append(a)
for i in range(N):
    minNum = 99999
    for j in range(M):
        if array[i][j] < minNum:
            minNum = array[i][j]
    if result < minNum:
        result = minNum
print(result)

• 2차원 리스트로 입력 받은 후 결과 구함
  (개념 정리가 부족했던 2차원 리스트 초기화/입력받기는 따로 포스팅)
• min() 함수를 사용하고 싶었지만 기억이 안나서 직접 구현
  (손코딩이라 min() 함수 검색 X)

답안 예시 (1)

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) # 최종 답안 출력

• 한 줄 입력받을 때마다 해당 줄에서 가장 작은 수를 구함
• 구한 수를 result와 비교하여 더 큰 수를 result에 저장
• max로 값을 비교하고 적절한 결과 저장
• 아래 예시와 차이점 : min(data)로 리스트 내의 값 중 가장 작은 수를 바로 구해 min_value에 저장

답안 예시 (2)

2중 반복문 구조 이용

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

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

print(result) # 최종 답안 출력

• 위 예시 (1)과 동일하게 매번 입력받을 때마다 결과 도출
• 위 예시와 차이점 : data 리스트를 처음부터 끝까지 반복 후 min(min_value, a)로 비교하여 가장 작은 값을 min_value에 저장

피드백

1. 여러 줄을 입력받고 결과를 구해야 할 경우, 굳이 2차원 리스트로 저장할 필요가 없다.
   (쓸데없이 for문을 많이 쓰게 되고, 저장하고 다시 꺼내서 계산하는 과정이 비효율적)
   한 줄 입력받고 바로 바로 결과를 구할 수 있는지 생각해보자.
2. 내장 함수를 잘 알아두자

4. 1이 될 때까지

작성 코드

N, K = map(int, input().split())
count = 0

while 1:
    if N == 1:
        break
    if N % K == 0:
        N /= K
    else:
        N -= 1
    count += 1
print(count)

• N이 1이 될 때까지 반복
• 하나의 while문으로 계산

답안 예시 (1)

단순하게 푸는 방법

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

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

# 마지막으로 남은 수에 대해 1씩 빼기
while n > 1:
	n -= 1
    result += 1

print(result)

• n >= k가 조건인 while문과 n > 1이 조건인 while문으로 나누어 계산

답안 예시 (2)

# 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)

• target은 n이 k로 나누어 떨어지지 않을 때, 가장 가까운 k로 나누어 떨어지는 수를 구해줌
• 남은 수 n을 빼는 횟수를 (n - 1)로 바로 result에 더해 불필요한 반복문을 사용하지 않음
• 반복문이 한 번 실행될 때마다 n이 k로 나누어지는 연산이 수행
  > 반복 횟수에 따라 기하급수적으로 n이 빠르게 줄어듦 (log 시간 복잡도)

피드백

1. // 연산자 사용할 수 있는 상황을 잘 캐치하자