[코딩테스트] 그리디 알고리즘

JY·2022년 5월 5일

그리디 알고리즘

현재 상황에서 지금 당장 좋은 것만을 고르는 방법의 알고리즘
매 순간 가장 좋아 보이는 것을 선택하며 현재의 선택이 나중에 미칠 영향 고려 x
사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형
(but 예외로 다익스트라(Dujkstra) 알고리즘은 암기가 필요한 알고리즘)
보통 코딩 테스트에서 해당 알고리즘 유형은 창의력, 최소한의 아이디어를 요구
기준에 따라 좋은 것을 선택해야하기 때문에 문제를 통해 기준 제시
=> 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로
그리디 알고리즘 문항은 주로 정렬 알고리즘과 짝을 이뤄 출제가 됨

그리디 알고리즘의 정당성

그리디 알고리즘을 이용했을 때 '최적의 해' 찾을 수 없을 가능성 높음
그리디 알고리즘으로 해를 찾았을 때 해법이 정당한지 검토해야함
대부분 그리디 알고리즘의 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있음

Ex1) 거스름돈

sol) 가장 큰 화폐 단위부터 돈을 거슬러 주기

N원을 거슬러줘야할 때, N=1260

n = 1260
count = 0

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

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

print(count)

-> 여기서 시간 복잡도가 화폐 종류에 영향 받음. 금액에는 무관.
-> 이 문항을 그리디 알고리즘으로 해결할 수 있는 이유
  : 항상 가지고 있는 동전의 큰 단위가 작은 단위의 배수이기 때문에 
    작은 단위 동전들을 조합하여 다른 해가 나올 수 없음

Ex2) 큰 수의 법칙

배열의 크기 N, 숫자가 더해지는 횟수 M, 같은 인덱스에 해당하는 수가 K번을 초과하여 연속해서 더해질 수 없는 조건을 가질 때 가장 큰 수를 만드는 경우

sol) 입력받은 배열에서 가장 큰 수와 두 번째로 큰 수만을 저장하고,
가장 큰 수를 K번 더한 후 두 번째로 큰 수를 1번 더하는 것을 반복한다.

입력조건
- 첫째 줄에 N (2 $\leq$ N $\leq$ 1,000), M (1 $\leq$ M $\leq$ 10,000),
K (1 $\leq$ K $\leq$ 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
- 둘째 줄에는 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.
- 입력으로 주어지는 K는 항상 M보다 작거나 같다.

출력조건
- 첫째 줄에 큰수의 법칙을 따라 더해진 값을 출력한다.

n, m, k = map(int, input(),split())  #n,m,k를 공백으로 구분하여 입력받기
data = list(map(int, input().split()) #n개의 수를 공백으로 구분하여 입력받기

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
    if m == 0 :
    	break
    result += second # 두 번째로 큰 수 한 번 더하기
    m -= 1 #더할 때마다 m을 1씩 줄이기
    
print(result)

여기서 M이 매우 크다면 시간 초과 판정을 받을 것.
이를 해결하기 위해 '반복되는 수열에 대해 파악'
=> 가장 큰 수 K번 + 두 번째로 큰 수 1번; (K+1)번
=> M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수

=> 가장 큰 수가 더해지는 횟수: int (M / (K+1) * K + M % (K+1))

이를 이용한 코드

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

data.sort() 
first = data[n-1]
second = data[n-2]

#가장 큰 수가 더해지는 횟수 계산 (count)
count = int(m / (k+1) * k + m % (k+1))
count += m % (k+1)

result = 0
result += (count) * first #'횟수*값'을 결과 값에 더하기
result += (m-count) * second

print(result)

Ex3) 숫자 카드 게임

각 행의 여러 개의 숫자 카드 중 가장 높은 숫자가 쓰인 카드 한 장 뽑는 게임

Rule
1. 숫자가 쓰인 카드들이 N x M 형태로 놓여있다. (N:행, M:열)
2. 먼저 뽑고자 하는 카드가 포함되어 있는 행 선택한다.
3. 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.

sol) 각 행마다 가장 작은 수를 찾은 뒤 그 수 중 가장 큰 수를 찾는다.

입력조건
- 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1 $\leq$ N,M $\leq$ 100)
- 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.

출력조건
- 첫째 줄에 게임의 룰에 맞게 선택된 카드에 적힌 숫자를 출력한다.

min() 함수를 이용한 코드

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

result = 0

for i in range(n): #각 행에 대하여
	data = list(map(int, input().split()) # 한 줄씩 입력 받기
    min_value = min(data) #min() 함수 이용하여 현재 행에서 가장 작은 수 찾기
    result = max(result, min_value) # 현재 행에서 찾은 가장 작은 수와 저장되어있던 result 값 중 큰 값 찾기
    
print(result)

2중 반복문 구조를 이용한 코드

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)

Ex4) 1이 될 때까지

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나만을 선택하여 반복적으로 수행한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

N에서 1을 뺀다.
N을 K로 나눈다.

sol) 주어진 N에 대하여 최대한 많이 나누기 (2번을 최대한 많이 실행하기)

입력조건
- 첫째 줄에 N (2 $\leq$ N $\leq$ 100,000)과 K(2 $\leq$ K $\leq$ 100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이 때, 입력으로 주어지는 N은 항상 K보다 크거나 같다.

출력조건
- 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

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

while n >= k: #N이 K 이상일 때 
	while n % k != 0: #N이 K로 나누어 떨어지지 않을 때
    	n-=1 #N에서 1 빼기
    	result += 1
    n //= k #N이 K로 나누어 떨어질 때 K로 나누기
    result += 1
    
while n>1: #N이 K보다 작을 때
	n -= 1 #남은 N에 대하여 1 빼기
    result += 1
    
print(result)

but 1을 일일이 빼기 때문에 해당 코드에서는 N이 매우 클 때는 시간 초과 판정을 받을 것.

N이 K의 배수가 되도록 한 번에 빼는 방식의 코드

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

while True:
	# N == (K로 나누어 떨어지는 수) 될 때까지 1 빼기
	target = (n // k) * k
    result += (n - target)
    n = target
    
    if n<k: #N이 K보다 작아 더 이상 나눌 수 없을 때
    	break #반복문 탈출
    
    result += 1
    n //= k
    
result += (n-1) #마지막으로 남은 N에 대하여 1 빼기
print(result)

실전문제 #1

각 자리각 숫자(0~9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수 구하는 프로그램 작성하시오. 단, 연산자 우선 순위를 고려하지 않고 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정)

sol) 연산하는 두 수 중 하나라도 1 이하일 때는 연산자 '+' 선택,
그 외의 경우는 'x' 연산자 선택

입력조건
- 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어집니다. (1 $\leq$ S의 길이 $\leq$ 20)

출력조건
- 첫째 줄에 만들어질 수 있는 가장 큰 수를 출력합니다.

s = input() #문자열 입력 받음

result = int(s[0])  #첫번째 인덱스의 문자를 숫자로 변경하여 대입

for i in range(1, len(s)):
	num = int(s[i]) #i번째 문자를 숫자로 변경하여 대입
    if num <= 1 or result <= 1:
    	result += num
    else:
    	result *= num
        
print(result)

출처: 나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2020)

다음 포스트