Greedy
그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다. 이 알고리즘 유형은 국내 알고리즘 교재에서 단어 그대로 번역하여 '탐욕법'으로 소개된다. 이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이라는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며 , 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
- Part 02 _ Chapter 03 그리디 86p
연습 문제: 거스름돈
실전 문제: 큰 수의 법칙, 숫자 카드 게임, 1이 될 때 까지
- 예제 1. 거스름돈
이 문제는 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제로 간단한 아이디어만 떠올릴 수 있으면 문제를 해결할 수 있다. 그것은 바로 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것이다. N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다. 그 다음 가장 큰 동전인 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있다.
change = 1260
count = 0
coin_types = [500, 100, 50, 10]
for coin in coin_types:
count += change // coin
n %= coin
print(count)
거스름돈은 1260원이며 동전의 종류는 4가지 종류가 있다고 가정하자. 각 동전으로 거스름돈을 몫연산 해서 동전의 개수를 구하고, 동전으로 거스름돈을 나머지 연산해서 반복문을 수행하면 최소의 동전 개수를 구할 수 있다.
그리디 알고리즘의 정당성
거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해를 도출할 수 없기 때문이다. 예를 들어 동전 단위가 500원, 400원, 100원이고 거스름돈이 800원인 경우를 생각해보자. 방금 해결한 알고리즘으로는 4개의 동전(500 + 100 + 100 + 100)을 최소의 동전 개수로 도출할 것이다. 그런데 최적의 해는 2개의 동전(400 + 400)을 거슬러 주는 것이다. 대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.
큰 수의 법칙
'큰 수의 법칙'은 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.
예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고 K가 3이라고 가정하다. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5인 46이 된다.
단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 예를 들어 순서대로 3, 4, 3, 4, 3으로 이루어진 배열이 있을 때 M이 7이고, K가 2라고 가정하자. 이 경우 두 번째 원소에 해당하는 4와 네 번째 원소에 해당하는 4를 번갈아 두 번씩 더하는 것이 가능하다. 결과적으로 4 + 4 + 4 + 4 + 4 + 4 + 4인 28이 도출된다.
배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 큰 수의 법칙에 따른 결과를 출력하시오.
입력 조건
● 첫째 줄에 N(2 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
● 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.
● 입력으로 주어지는 K는 항상 M보다 작거나 같다.
입력 예시
5 8 3
2 4 5 4 6
출력 예시
46
접근
먼저 주어진 N개의 자연수를 데이터 리스트로 만들고 난 뒤, 생각했다. 가장 큰 수는 k번 만큼 더해질 수 있으니 가장 큰 수를 더하는 과정을 우선 거치고, 그 수를 리스트에서 뺀 다음으로 큰 수를 한 번 더해주고 다시 뺀 수를 리스트에 집어넣는다. 이를 반복하면 정답을 찾을 수 있을 것이라고 생각했다. 반복문의 종료 조건은 cnt변수를 이용해서 m(연산 수)과 동일한지 확인한다.
구현
n, m, k = map(int, input().split())
data = list(map(int, input().split()))
result = 0
cnt = 0
for _ in range(m):
for _ in range(k):
result += max(data)
cnt += 1
if (cnt == m):
break
temp = max(data)
data.remove(temp)
result += max(data)
data.append(temp)
cnt += 1
if (cnt == m):
break
print(result)
반복문을 하나만 사용해서 풀 수 있을 것 같다는 생각이 들었는데, 번뜩 생각이 나지 않았다. 일일이 m과 cnt를 비교하면서 종료 조건을 확인하는 것도 마음에 들지 않았고, 변수를 너무 많이 사용한 느낌이었다. 문제 해설을 보며 풀이를 고쳐나가 보자.
해설 1
이 문제를 해결하려면 입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하면 된다. 연속으로 더할 수 있는 횟수는 최대 K번이므로 '가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더 더하는 연산'을 반복하면 된다.
n, m, k = map(int, input().split())
data = sorted(list(map(int, input().split())))
first = data[n - 1]
second = data[n - 2]
result = 0
while True:
for i in range(k):
if m == 0:
break
result += first
m -= 1
if m == 0:
break
result += second
m -= 1
print(result)
리스트를 정렬하고 가장 큰 수와 그 다음으로 큰 수를 뽑고 시작하면, 내 풀이처럼 max 함수를 두 번 쓸 이유도, temp 변수를 선언할 필요도, 리스트에서 넣다 빼는 행위도 필요 없을 것이다. m은 결과값을 계산하는 과정에서 영향을 주지 않으니 cnt 변수로 선언해서 사용하지 않아도 된다는 것까지 가져가자. 이중 반복문과 일일이 종료 조건을 확인해주는 것은 동일하다.
해설 2
이 문제는 M이 기하 급수적으로 커지면, 값을 1씩 줄여나가며 종료 조건을 판단하기 때문에 시간 초과 판정을 받을 수 있다. 간단한 수학적 아이디어를 이용해 더 효율적으로 문제를 해결해보자. 예를 들어 N이 5이고 입력값이 다음과 같이 주어졌다고 가정하자.
| 2 | 4 | 5 | 4 | 6 |
이때 가장 큰 수와 두 번째로 큰 수만 필요하므로, 선택하면 다음과 같다.
- 가장 큰 수 : 6
- 두 번째로 큰 수 : 5
문제의 조건에서 M = 8, K = 3이라면 다음과 같이 더했을 때 합을 최대로 할 수 있다.
(6 + 6 + 6 + 5) + (6 + 6 + 6 + 5) = 46
이 문제를 풀려면 가장 먼저 반복되는 수열에 대해서 파악해야한다. 가장 큰 수와 두 번째로 큰 수가 더해질 때는 특정한 수열 형태로 일정하게 반복해서 더해지는 특징이 있다. 위의 예시에서는 수열 {6, 6, 6, 5}가 반복된다. 그렇다면 반복되는 수열의 길이는 어떻게 될까? 가장 큰 수는 K번 만큼 더해질 것이고, 그 다음 수가 한번 더해지므로 K + 1이 된다. 따라서 M을 K + 1로 나눈 몫이 반복되는 수열의 개수가 된다. 다시 여기에 K를 곱하면 그 수는 가장 큰 수의 개수가 된다. 수열이 M // (K + 1)번 등장한다고 했으니 그 안의 가장 큰 수는 K개가 있기 때문이다.
만약 M이 (K + 1)로 나누어 떨어지지 않는다면? 그 나머지 만큼 가장 큰 수가 더해진다. 따라서 가장 큰 수가 더해지는 횟수는 다음과 같다.
(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 = int(m / (k + 1)) * k
count += m % (k + 1)
result = 0
result += (count) * first
result += (m - count) * second
print(result)
(m - count)가 잘 이해되지 않는다. m은 덧셈을 진행할 총 횟수다. count는 가장 큰 수가 더해지는 횟수다. 따라서 m - count는 가장 큰 수가 더해지지 않은 경우, 즉 그 다음으로 큰 수가 더해지는 경우이다.
숫자 카드 게임
숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단 , 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.
- 숫자가 쓰인 카드들이 N x M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
- 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
- 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
- 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.
예를 들어 3 x 3 형태로 카드들이 다음과 같이 놓여 있다고 가정하자.
| 3 | 1 | 2 |
| 4 | 1 | 4 |
| 2 | 2 | 2 |
여기서 카드를 골라낼 행을 고를 때 첫 번째 혹은 두 번째 행을 선택하는 경우, 최종적으로 뽑는 카드는 1이다. 하지만 세 번째 행을 선택하는 경우 최종적으로 뽑는 카드는 2이다. 따라서 이 문제에서는 세 번째 행을 선택하여 숫자가 2가 쓰여진 카드를 뽑는 것이 정답이다.
카드들이 N x M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오.
입력 조건
● 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1 ≤ N, M ≤ 100)
● 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.
입력 예시 1
3 3
3 1 2
4 1 4
2 2 2
출력 예시 1
2
입력 예시 2
2 4
7 3 1 8
3 3 3 4
출력 예시 2
3
접근
n, m이후의 입력값의 꼴이 2차원 배열 형태이기 때문에 이를 2차원 형태로 구성해서 풀면 쉽게 풀 수 있겠다고 생각했다. 첫 행에서 가장 작은 수를 뽑은 뒤, 다음 행에서 가장 작은 수를 뽑고 그 둘을 비교하는 과정을 거치는 방법을 생각했다. 비교할 때 더 큰 수로 결과값을 갱신하는 방법으로 구현하면 다음과 같다.
구현
n, m = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(n)]
result = min(data[0])
for i in range (1, n):
if result < min(data[i]):
result = min(data[i])
print(result)
n, m을 먼저 입력받으므로, 1차원 배열을 n번 입력받아 2차원 배열을 구성할 수 있다. 그리고 반복문을 통해 각 행에서 가장 작은 수들을 비교해 그 중에서 가장 큰 수를 도출한다. 딱히 고쳐나갈 부분은 없다고 생각한다.
이 문제를 푸는 아이디어는 바로 '각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는 것이다. 이 문제를 해결하기 위해서는 min 함수를 이용하는 것과 2중 반복문 구조를 이용할 수 있어야 한다.
해설 1 (min 함수)
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 (2중 반복문)
n, m = map(int, input().split())
result = 0
for i in range(n):
data = list(map(int, input().split()))
min_value = 0
for a in data:
min_value = min(a, min_value)
result = max(result, min_value)
print(result)1이 될 때까지
어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.
- N에서 1을 뺀다.
- N을 K로 나눈다.
N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.
입력 조건
● 첫째 줄에 N(2 ≤ N ≤ 100,000), K(2 ≤ K ≤ 100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.
입력 예시
25 5
출력 예시
2
접근
1번과 2번 연산을 각각 실행할 때 마다 횟수를 셀 변수 하나를 선언한 다음, 분기점을 나누어서 2번 과정이 가능하다면 수행하고 아니면 1번과정을 수행하는 식으로 문제를 풀었다.
구현
n, k = map(int, input().split())
cnt = 0
while n != 1:
if n % k == 0:
n /= k
else:
n -= 1
cnt += 1
print(cnt)
이렇게 풀었을 때는 문제가 없어 보이지만, 큰 수의 법칙문제와 마찬가지로 n의 범위가 매우 큰 문제에서는 시간 초과가 일어날 수도 있다. 종료 조건인 n을 -1씩 처리하기 때문이다. 어떻게 할 수 있을까?
해설
n, k = map(int, input().split())
cnt = 0
while True:
target = (n // k) * k
cnt += (n - target)
n = target
if n < k:
break
n //= k
cnt += 1
cnt += (n - 1)
print(cnt)
target은 n이 k로 나누어 떨어지는 수 중에 n에 가장 가까운 수라고 표현할 수 있다. 그리고 그 다음 cnt가 의미하는 것은 'n을 k로 나누어 떨어지게 하기 위해서 -1 연산이 몇번 이루어졌냐'를 카운트한 것이다. 바로 n을 k로 나누어 떨어지게하기 위해서 -1을 빼는 과정을 한번에 처리한 것이다.
n을 k로 나누어 떨어지게 만들었으니, k로 몫 연산을 해주고 카운트를 하나 올린다. 그렇게 해서 k로 n을 나눌 수 없을 만큼 n이 k보다 작아지게 되면 이제 n을 1로 만들어줘야 하니까 n - 1 만큼을 n에서 빼주어야 하는 것이다. >> n - (n - 1) = 1 이다. 따라서 cnt도 그만큼 카운트 해준다.
마치며
첫 알고리즘 공부로 그리디를 학습해 보았는데, 교재의 알고리즘 유형별 기출문제의 그리디 문제들은 제한 시간이 30분인데도 3~4시간씩 걸려서 풀어낸 문제가 있다. 시간복잡도는 상관하지 않고 풀어서 기쁨도 잠시였다. 오늘을 시작으로, 알고리즘 문제를 유형별로 풀어가면서 문제를 해결하는 것에 집중할 것이고, 다시 교재를 회독할 때는 시간 복잡도에 관해서 중심을 잡아보려고 한다.
'Algorithm > 취업을 위한 코딩테스트 with Python' 카테고리의 다른 글
| BFS - 그래프 탐색을 위한 너비 우선 탐색 알고리즘 (0) | 2023.05.16 |
|---|---|
| DFS - 그래프를 탐색하기 위한 깊이 우선 탐색 알고리즘 (0) | 2023.05.16 |
| DFS & BFS를 위한 (선형)자료구조의 기초 (0) | 2023.05.11 |
| Implementation - 아이디어를 코드로 바꾸는 구현 (0) | 2023.05.04 |
댓글