홈 [Algorithm] 코딩테스트 알고리즘 05 - 그리디
포스트
취소

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

게시 2022-02-02 업데이트 2022-10-16
By 19tak

본 포스팅은 “이것이 취업을 위한 코딩테스트다 with 파이썬” - (한빛미디어, 나동빈 지음)을 바탕으로 공부한 내용을 정리한 것입니다.

  1. 그리디 알고리즘
  2. 그리디 알고리즘의 정당성
  3. 예제
  4. 실전 문제 1
    • 큰 수의 법칙
    • 개선된 답안 예시
  5. 실전 문제 2
    • 숫자 카드 게임
  6. 실전 문제 3
    • 1이 될 때까지

1. 그리디 알고리즘

그리디 알고리즘은 이름 그대로 탐욕적으로 문제를 푸는 알고리즘이다.

현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

  • 코딩 테스트에서 그리디 유형 문제는 사전 지식 없이도 풀 수 있지만, 그만큼 많은 유형을 접해봐야한다.
  • 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
  • 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준을 제시한다.
  • 그래서 정렬 알고리즘과 짝을 이뤄 출제된다.

2. 그리디 알고리즘의 정당성

대부분의 문제는 그리디 알고리즘을 이용했을 때 ‘최적의 해’를 찾을 수 없을 가능성이 다분하다.

하지만 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적이다.

그리디 알고리즘으로 문제의 해법을 찾을 때는 해법이 정당한지 검토해야 한다.

대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고, 정당한지 검토할 수 있어야한다.

  • 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심해본다.
  • 그리디 알고리즘으로 해결 방법을 찾을 수 없다면, 다이나믹 프로그래밍이나 그래프 알고리즘을 고민해본다.

3. 예제

거스름돈 문제는 그리디 알고리즘을 설명할 때 자주 소개되는 문제이다.

음식점에서 계산을 할 때, 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원 동전이 무한히 존재한다고 가정한다.

손님에게 거슬러 줘야할 돈이 N원일 때, 거슬러줘야 할 동전의 최소 개수를 구하라.

단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

1
2
3
4
5
6
7
8
9
10

# n 입력
n = 1260

# 큰 단위의 화폐부터 차례대로 확인
list = [500, 100, 50, 10]
for coin in list:
	count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
	n %= coin

print(count)

4. 실전 문제 1

큰 수의 법칙

  • 2019 국가 교육기관 코딩 테스트 기출문제

‘큰 수의 법칙’은 일반적으로 통계 분야에서 다루어지는 내용이지만 이 문제에서는 다르게 사용한다.

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다.

단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 특징이다.

  • 첫째 줄에 N(2 <= N <= 1000), M(1 <= M <= 10000), K(1 <= K <= 10000)의 자연수가 주어지며 각 자연수는 공백으로 구분.
  • 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분. 각각의 자연수는 1 이상 10000 이하의 수.
  • 입력으로 주어지는 K는 항상 M보다 작거나 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

연속으로 더할 수 있는 횟수는 최대 K번이므로 다음과 같이 표현하면 된다.

가장 큰 수를 K번 더하고, 두 번째로 큰 수를 한 번 더하는 연산을 반복.

개선된 답안 예시

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

수열을 활용하여 가장 큰 수가 더해지는 횟수를 이용한 풀이이다.

[가장 큰 수 * k 번, 두 번째로 큰 수 한번]이라는 수열이 반복되는 구조이기에 이 반복 되는 수를 계산한다.

(가장 큰 수 * k * count)와 (두 번째로 큰 수 * count)를 더하면 정답이된다.

5. 실전 문제 2

숫자 카드 게임

  • 2019 국가 교육기관 코딩 테스트 기출문제

숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다.

  1. 숫자 카드들이 N x M 형태로 놓여있다. N은 행, M은 열의 개수다.
  2. 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
  3. 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑는다.
  4. 각 행에 대하여, 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세운다.
  • 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 각각 자연수로 주어진다. (1 <= N,M <= 100)
  • 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10000 이하의 자연수이다.

다음은 min() 함수를 이용하여 풀이한 소스이다.

1
2
3
4
5
6
7
8
9
10
11
12

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

다음은 2중 반복문을 이용한 풀이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

data에 입력받는 수는 최대 10000이기에 min_value를 10001로 초기화했다.

6. 실전 문제 3

1이 될 때까지

  • 2018 E 기업 알고리즘 대회

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복 수행한다.

단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

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

N과 K가 주어질 때 1이 될 때까지 과정을 수행하는 최소 횟수를 구하는 프로그램을 작성하시오.

  • 첫째 줄에 N(2 <= N <= 100000)과 K(2 <= K <= 100000)가 공백으로 구분, 자연수로 주어진다.
  • N은 항상 K 이상이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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의 범위가 10만 이하이므로 일일이 1씩 빼가며 문제를 해결했다.

다음은 N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식으로 빠르게 동작하게 한 소스이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

참고

“이것이 취업을 위한 코딩테스트다 with 파이썬” - (한빛미디어, 나동빈 지음)

Study, Algorithm
Python Algorithm
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.
최근 업데이트
바로가기