그리디 알고리즘
- 현재 상황에서 지금 당장 좋은 것만 고르는 방법
- 정당성 분석이 중요하다.
- 반복적으로 그리디 알고리즘을 따라가도 최적의 해를 구할 수 있는지를 검증해야 한다.
- 암기한다고 풀 수 있는 유형이 아니며, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 줄 알아야 한다.
예제 <거스름돈>
문제
거슬러줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 갯수는?
Key
가장 큰 화폐부터 거슬러주자
n = 1260
count = 0
array = [500, 100, 50, 10] # 큰 단위의 화폐부터 차례대로 확인한다.
for coin in array:
count += n// coin # 해당 화폐로 거슬러 줄 수 있는 동전의 갯수를 세자
n %= coin
print(count)- 화폐의 종류가 K라고 한다면, 소스코드의 시간 복잡도는 O(K)
- 이 알고리즘의 시간복잡도는 거슬러줘야 하는 금액과는 무관, 동전의 총 종류에만 영향을 받는다
- 같은 코드를 C++ 로 구현하면 다음과 같다.
#include <iostream>
using namespace std;
int n = 1260;
int cnt; // 0으로 초기화 되어 있음
int coinTypes[4] = {500, 100, 50, 10}; // 배열에 화폐의 종류를 담는다
int main(void){
for (int i = 0; i<4; i++){
// 모든 과정을 화폐 단위 갯수만큼 반복한다.
cnt += n / coinTypes[i];
// 매번 현재의 동전을 확인하고
// 남아있는 돈을 현재의 동전으로 나눈 몫을 cnt에 넣어준다.
n %= coinTypes[i];
// 거슬러 주는 것이 끝나고 남은 금액도 n에 넣어준다.
}
cout << cnt << "\n";
}큰 수의 법칙
문제
다양한 수로 이뤄진 배열이 있을 때 주어진 수들을 M번 더해 가장 큰 수를 만드는 법칙 (단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번 초과해서 더해질 수 없다)
Key
반복되는 수열
가장 큰 수를 만들려면 주어진 수 중에서 가장 큰 수를 최대한 더하면 된다. 그러나 연속으로 더하는 것에 대한 횟수 제한이 있으므로 그 횟수를 소진했을 때는 두 번째로 큰 수를 사용하여야 한다.
n, m, k = map(int, input().split()) #n,m,k
# n개의 자연수
# m은 숫자가 더해지는 횟수
# k는 연속으로 더할 수 있는 횟수 (k번을 초과할 수 없다 )
data = list(map(int, input().split())) # n개의 자연수를 공백을 구분하여 입력받는다
data.sort() # 입력받은 data들을 오름차순으로 정렬
first = data[n-1] # 가장 큰 수 (배열 가장 오른쪽에 있는게 가장 크겠지)
second = data[n-2] # 두번째로 큰 수 (배열 오른쪽에서 하나 왼쪽에 있는게 가장 크겠지)
result = 0 # result 값 초기화
while True:
for i in range(k): # k번 반복한다
if m == 0: # 0이면 멈춤
break
result += first # 결과값에 가장 큰수를 더한다
m -= 1 # 더할때마다 m번 횟수에서 1씩 뺀다
if m == 0:
break
result += second
m -= 1
print(result)
위와 같은 코드는 생각해내기는 쉽지만 M의 크기가 매우매우 큰 수 이상이 되면 시간 초과 판정을 받을 수 있다.
수열을 이용한 더 효율적인 코드를 고민해보자.
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에 넣는다.
result += (m - count) * second
# 두 번째로 큰 수 더해서 result에 넣는다
print(result)count = int(m / (k+1)) * k
: 가장 큰 수가 더해지는 횟수를 계산한다.
: 반복되는 수열의 길이는? -> m을 k+1로 나눈 몫!
그러나 나누어 떨어지지 않는 경우 남는 부분도 더해주어야 하므로
count += m % (k+1) 이 코드를 통해 나머지를 count에 더해준다.
숫자 카드 게임
문제
여러 개의 숫자 카드 중 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임
<룰>
1. 카드는 NXM 형태로 놓여있음
2. 행을 먼저 선택
3. 선택한 행에서 가장 작은 숫자가 있는 카드 선택
4. 각 행에서 가장 작은 숫자를 선택하더라도 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있어야 함
Key
각 행에서는 가장 작은 수 / 그 수 중에서 가장 큰 수 찾기
n, m = map(int, input().split())
#행렬을 입력받는다
result = 0
# 결과값 초기화
for i in range(n): # 행을 탐색
data = list(map(int, input().split()))
# 각 행에 수를 입력해서 데이터 값에 넣는다
data_min = min(data)
# 입력한 데이터 값 중에서 작은 값을 찾는다
result = max(result, data_min)
# result 값과 위에서 찾은 최소값을 비교하여 큰 수를 result에 넣는다.
print(result)2 4
7 3 1 8
3 3 3 4
3
1이 될 때 까지 최소 연산 쵯수 구하기
문제
어떤 수 N이 1이 될 때까지 두 과정 중 하나를 반복적으로 선택해 수행 (두 번째 연산은 N이 K로 나누어떨어질 때만 가능)
1. N에서 1을 뺀다 :n-1
2. N을 K로 나눈다 : n // k
1번 혹은 2번 과정을 수행해야하는 최소 횟수를 출력
key
최대한 나누기를 많이 하면 n을 크게 줄일 수 있으므로 최소한의 횟수로 1로 만들 수 있다
- 단순한 코드
n, k = map(int, input().split())
result = 0
# n이 k이상이면 k로 나눈다
while n >= k:
while n % k != 0:
n -= 1
result += 1
# 횟수를 구해야 하므로 연산을 할 때마다 result 값을 1씩 증가시켜준다
#k로 나눈다
n //= k
result += 1
while n>1:
n -= 1
result += 1
print(result) - 나누어 떨어지는 값을 바로 찾는 코드
n, k = map(int, input().split())
result = 0 # 횟수
while True:
target = (n//k) * k
result += (n - target)
n = target
if n < k:
break # n이 k보다 작다면 무한루프 탈출
result += 1
n //= k
# n이 k의 배수이므로 나누어준다
# n이 1보다 크다면 남은 수에 대해서 1씩 빼는 연산을 한다
result += (n-1)
print(result)target = (n//k) * k
n을 k로 나눈 몫에 k를 곱해서 target에 넣게 되면 target은 k로 나누어 떨어지는 가장 가까운 값을 찾은 것이 된다.
result += (n - target)
이 부분에서 result에는 n이 target이 될 때 까지 (나누어 떨어지는 가장 가까운 값을 찾을 때 까지) 1을 빼는 연산을 하는 횟수가 담기게 된다.
- 시간복잡도
두 번째 방법으로 풀게 되면 O(log n) 시간복잡도가 나온게 된다. (한 번 반복 할 때마다 바로 n이 k로 나눠지는 연산이 수행이 되므로 기하급수적으로 n이 빠르게 감소하여 1로 향하여 간다)
: 매우 큰 수일 때도 쓸 수 있다
- 동일한 코드를 C++로 구현
#include <iostream>
using namespace std;
int n, k;
int result;
int main(void){
cin >> n >> k;
while(true){
int target = (n/k) * k;
result += (n - target);
n = target;
if (n<k) break;
result++;
n /= k;
}
result += (n-1);
cout << result << '\n';
}