Greedy Algorithm
04 Aug 2022 | Algorithm
해당 게시물은 이것이 코딩 테스트다 with 파이썬을 바탕으로 언제든지 블로그에 들어와서 보기위해 작성되었습니다.
그리디(Greedy)
- 그리디 알고리즘(탐욕법)은 “현재 상황에서 지금 당장 좋은 것만 고르는 방법” 을 의미합니다.
- 즉 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘으로, 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다.
- 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다.
- 그리디 해법은 그 정당성 분석이 중요 합니다.
- 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토합니다.
[문제 상황] 루트 노드부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶습니다.
최적은 해는 무엇인가요?
- 5 -> 7 -> 9로 가는 것이 가장 큰 값을 얻을 수 있는 방향입니다.
단순히 매 상황에서 가장 큰 값만 고른다면 어떻게 될까요?
- 루트노드에서 인접한 노드는 7, 10, 8이므로 현재상황에서 가장 큰 값인 10으로 이동합니다.
- 10에서 이동할 수 있는 4와 3중 더 큰 값을 가지는 4로 이동할 수 있습니다.
- 여기서는 5 + 10 + 4 = 19로 최적의 해인 21보다는 낮은 값입니다.
그리디 알고리즘은 이처럼 단순히 매 상황에서 가장 큰 값만 고르는 방식이라고 말할 수 있습니다.
- 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많습니다.
- 하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황해서, 이를 추론 할 수 있어야 풀리도록 출제됩니다.
거스름돈
문제 정의
- 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
문제 해설
- 해당 문제는 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제입니다.
- 간단한 아이디어를 생각하면 “가장 큰 화폐 단위부터 돈을 거슬러 주는 것” 입니다.
- N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 주고, 그다음 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있습니다.
예를 들어 입력으로 주어진 N이 1,260이라면 다음과 같이 가장 큰 화폐 단위부터 거슬러 주는 과정을 통해 1,260원을 모두 거슬러 줄 수 있습니다.
step 0 - 남은 돈: 1,260원
화폐 단위
손님이 받은 개수
500
0
100
0
50
0
10
0
step 1 - 남은 돈: 260원
화폐 단위
손님이 받은 개수
500
2
100
0
50
0
10
0
step 2 - 남은 돈: 60원
화폐 단위
손님이 받은 개수
500
2
100
2
50
0
10
0
step 3 - 남은 돈: 10원
화폐 단위
손님이 받은 개수
500
2
100
2
50
1
10
0
step 4 - 남은 돈: 0원
화폐 단위
손님이 받은 개수
500
2
100
2
50
1
10
1
Solution
n = 1260
count = 0
# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]
for coin in coin_types:
count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
n %= coin
print(count)
- 그리디 알고리즘으로 문제의 해법을 찾았을 때는 정당성을 검토해야 합니다.
- 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유
- 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문 입니다.
- 만약 800원을 거슬러 주어야 하는데 화폐 단위가 500원, 400원, 100원이라면?
- 이 경우 그리디 알고리즘으로 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 (2N≤ 1,000), M(1 ≤ M ≤ 10,000), K(1≤K ≤ 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
- 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.
- 입력으로 주어지는 K는 항상 M보다 작거나 같다.
출력 조건
- 출력 조건첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다.
Test Case
[input]
5 8 3
2 4 5 4 6
[output]
46
My Solution
_, M, K = map(int, input().split())
input_data = list(map(int, input().split()))
input_data.sort(reverse=True)
first_data = input_data[0] # 첫번째로 큰 수
second_data = input_data[1] # 두번째로 큰 수
result = 0
for m in range(M):
if m == 0:
result += first_data
continue
if m % K == 0:
result += second_data
else:
result += first_data
print(result)
Solution 1
# N, M, K를 공백으로 구분하여 입력받기
from unittest import result
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
if m == 0: # m이 0이라면 반복문 탈출
break
result += second # 두 번째로 큰 수를 한 번 더하기
m -= 1 # 더할 때마다 1씩 빼기
print(result) # 최종 답안 출력
- 이 문제는 전형적인 그리디 알고리즘 문제로, 이 문제를 해결하려면 일단 입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하면 됩니다.
- 연속으로 더할 수 있는 횟수는 최대 K번이므로 ‘가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 연산’을 반복하면 됩니다.
Solution2
# 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) # 최종 답안 출력
- Test Case를 보면 다음과 같다.
- 가장 큰 수: 6
- 두 번째로 큰 수: 5
- 이때 M이 8이고, K가 3이라면 (6 + 6 + 6 + 5) + (6 + 6 + 6 + 5)와 같이 더했을 때 합을 최대로 할 수 있다. 정답은 46이 됩니다.
- 이 문제를 풀려면 가장 먼저 반복되는 수열 에 대해서 파악해야 합니다.
- 가장 큰 수와 두 번째로 큰 수가 더해질 때는 특정한 수열 형태로 일정하게 반복해서 더해지는 특징이 있습니다.
- 위의 예시에서는 수열 {6, 6, 6, 5}가 반복됩니다.
- 반복되는 수열의 길이는 (K+1)로 위의 예시에서는 4가 됩니다.
- 따라서 M (K + 1)로 나눈 몫이 수열이 반복되는 횟수가 됩니다.
- 다시 여기에 K를 곱해주면 가장 큰 수가 등장하는 횟수가 됩니다.
- 이때 M이 (K + 1)로 나누어떨어지지 않는 경우도 고려해야 합니다.
- 그럴 때는 M을 (K + 1)로 나눈 나머지만큼 가장 큰 수가 추가로 더해지므로 이를 고려해주어야 합니다.
- 즉, ‘가장 큰 수가 더해지는 횟수’는 다음과 같습니다.
\[int(M\ /\ (K\ +\ 1))\ *\ K\ +\ M\ \%\ (K\ +\ 1)\]
숫자 카드 게임
문제 정의
- 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.
- 숫자가 쓰인 카드들이 N X M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
- 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
- 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
- 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.
예를 들어 3×3 형태로 카드들이 다음과 같이 놓여 있다고 가정하자.
3 1 2
4 1 4
2 2 2
여기서 카드를 골라낼 행을 고를 때 첫 번째 혹은 두 번째 행을 선택하는 경우, 최종적으로 뽑는 카드는 1이다. 하지만 세 번째 행을 선택하는 경우 최종적으로 뽑는 카드는 2이다. 따라서 이 예제에서는 세 번째 행을 선택하여 숫자 2가 쓰여진 카드를 뽑는 것이 정답이다. 카드들이 N × M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오.
입력 조건
- 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1≤ N, M≤ 100)
- 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.
출력 조건
- 첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.
Test Case
[input]
2 4
7 3 1 8
3 3 3 4
[output]
3
My Solution
N, _ = map(int, input().split())
result = 0
for i in range(N):
dummy = min(list(map(int, input().split())))
result = max(dummy, result)
print(result)
- 이 문제를 푸는 아이디어는 바로 각 행마다 가장 작은 수를 찾은 뒤에 그 수중에서 가장 큰 수를 찾는 것 입니다.
- 입력 조건에서 입력으로 들어오는 수는 모두 10,000 이하이므로 단순히 배열에서 가장 작은 수를 찾는 기본 문법을 이용하여 각 행에서 가장 작은 수를 찾은 다음 그 수중에서 가장 큰 수를 찾는 방식으로 문제를 해결할 수 있습니다.
Solution 1
# 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) # 최종 답안 출력
Solution2
# 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이 될 때까지
문제 정의
- 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단,두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.
- N에서 1을 뺀다.
- N을 K로 나눈다.
예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이된다. 이는 N을 1로 만드는 최소 횟수이다.
N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.
입력 조건
- 첫째 줄에 N (2 N 100,000)과 K2 ≤K ≤ 100,000)가 공백으로 구분되며 각각 자연수로 주어진다.
- 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.
출력 조건
- 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.
Test Case
[input]
25 5
[output]
2
My Solution
n, k = map(int, input().split())
result = 0
while 1:
if n == 1:
break
result += 1
if n % k == 0:
n /= k
else:
n -= 1
print(result)
- 해당 문제는 주어진 N에 대하여 ‘최대한 많이 나누기’ 를 수행하면 됩니다.
- 왜냐하면 어떠한 수가 있을 때, ‘2 이상의 수로 나누는 것’이 ‘1을 빼는 것’보다 숫자를 훨씬 많이 줄일 수 있기 때문입니다.
- 문제에서는 K가 2 이상의 자연수이므로, 가능하면 나누는 것이 항상 더 숫자를 빠르게 줄이는 방법이 됩니다.
- 따라서 다음의 과정을 반복할 수 없을 때까지 반복하면 정답을 구할 수 있다.
- N이 K의 배수가 될 때까지 1씩 빼기
- N을 K로 나누기
예를 들어 N = 25, K=3 일 때는 다음과 같습니다.
단계
연산 과정
N의 값
0단계(초기 단계)
N = 25
1단계
N에서 1 빼기
N = 24
2단계
N을 K로 나누기
N = 8
3단계
N에서 1 빼기
N = 7
4단계
N에서 1 빼기
N = 6
5단계
N을 K로 나누기
N = 2
6단계
N에서 1 빼기
N = 1
6번의 과정으로 N = 1을 만들 수 있습니다.
Solution 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
while n > 1:
n -= 1
result += 1
print(result)
Solution2
# 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)
- 해당 코드는 N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식입니다.
해당 게시물은 이것이 코딩 테스트다 with 파이썬을 바탕으로 언제든지 블로그에 들어와서 보기위해 작성되었습니다.
그리디(Greedy)
- 그리디 알고리즘(탐욕법)은 “현재 상황에서 지금 당장 좋은 것만 고르는 방법” 을 의미합니다.
- 즉 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘으로, 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다.
- 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다.
- 그리디 해법은 그 정당성 분석이 중요 합니다.
- 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토합니다.
[문제 상황] 루트 노드부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶습니다.
최적은 해는 무엇인가요?
- 5 -> 7 -> 9로 가는 것이 가장 큰 값을 얻을 수 있는 방향입니다.
단순히 매 상황에서 가장 큰 값만 고른다면 어떻게 될까요?
- 루트노드에서 인접한 노드는 7, 10, 8이므로 현재상황에서 가장 큰 값인 10으로 이동합니다.
- 10에서 이동할 수 있는 4와 3중 더 큰 값을 가지는 4로 이동할 수 있습니다.
- 여기서는 5 + 10 + 4 = 19로 최적의 해인 21보다는 낮은 값입니다.
그리디 알고리즘은 이처럼 단순히 매 상황에서 가장 큰 값만 고르는 방식이라고 말할 수 있습니다.
- 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많습니다.
- 하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황해서, 이를 추론 할 수 있어야 풀리도록 출제됩니다.
거스름돈
문제 정의
- 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
문제 해설
- 해당 문제는 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제입니다.
- 간단한 아이디어를 생각하면 “가장 큰 화폐 단위부터 돈을 거슬러 주는 것” 입니다.
- N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 주고, 그다음 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있습니다.
예를 들어 입력으로 주어진 N이 1,260이라면 다음과 같이 가장 큰 화폐 단위부터 거슬러 주는 과정을 통해 1,260원을 모두 거슬러 줄 수 있습니다.
step 0 - 남은 돈: 1,260원
| 화폐 단위 | 손님이 받은 개수 |
|---|---|
| 500 | 0 |
| 100 | 0 |
| 50 | 0 |
| 10 | 0 |
step 1 - 남은 돈: 260원
| 화폐 단위 | 손님이 받은 개수 |
|---|---|
| 500 | 2 |
| 100 | 0 |
| 50 | 0 |
| 10 | 0 |
step 2 - 남은 돈: 60원
| 화폐 단위 | 손님이 받은 개수 |
|---|---|
| 500 | 2 |
| 100 | 2 |
| 50 | 0 |
| 10 | 0 |
step 3 - 남은 돈: 10원
| 화폐 단위 | 손님이 받은 개수 |
|---|---|
| 500 | 2 |
| 100 | 2 |
| 50 | 1 |
| 10 | 0 |
step 4 - 남은 돈: 0원
| 화폐 단위 | 손님이 받은 개수 |
|---|---|
| 500 | 2 |
| 100 | 2 |
| 50 | 1 |
| 10 | 1 |
Solution
n = 1260
count = 0
# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]
for coin in coin_types:
count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
n %= coin
print(count)
- 그리디 알고리즘으로 문제의 해법을 찾았을 때는 정당성을 검토해야 합니다.
- 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유
- 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문 입니다.
- 만약 800원을 거슬러 주어야 하는데 화폐 단위가 500원, 400원, 100원이라면?
- 이 경우 그리디 알고리즘으로 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 (2N≤ 1,000), M(1 ≤ M ≤ 10,000), K(1≤K ≤ 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
- 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.
- 입력으로 주어지는 K는 항상 M보다 작거나 같다.
출력 조건
- 출력 조건첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다.
Test Case
[input]
5 8 3
2 4 5 4 6
[output]
46
My Solution
_, M, K = map(int, input().split())
input_data = list(map(int, input().split()))
input_data.sort(reverse=True)
first_data = input_data[0] # 첫번째로 큰 수
second_data = input_data[1] # 두번째로 큰 수
result = 0
for m in range(M):
if m == 0:
result += first_data
continue
if m % K == 0:
result += second_data
else:
result += first_data
print(result)
Solution 1
# N, M, K를 공백으로 구분하여 입력받기
from unittest import result
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
if m == 0: # m이 0이라면 반복문 탈출
break
result += second # 두 번째로 큰 수를 한 번 더하기
m -= 1 # 더할 때마다 1씩 빼기
print(result) # 최종 답안 출력
- 이 문제는 전형적인 그리디 알고리즘 문제로, 이 문제를 해결하려면 일단 입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하면 됩니다.
- 연속으로 더할 수 있는 횟수는 최대 K번이므로 ‘가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 연산’을 반복하면 됩니다.
Solution2
# 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) # 최종 답안 출력
- Test Case를 보면 다음과 같다.
- 가장 큰 수: 6
- 두 번째로 큰 수: 5
- 이때 M이 8이고, K가 3이라면 (6 + 6 + 6 + 5) + (6 + 6 + 6 + 5)와 같이 더했을 때 합을 최대로 할 수 있다. 정답은 46이 됩니다.
- 이 문제를 풀려면 가장 먼저 반복되는 수열 에 대해서 파악해야 합니다.
- 가장 큰 수와 두 번째로 큰 수가 더해질 때는 특정한 수열 형태로 일정하게 반복해서 더해지는 특징이 있습니다.
- 위의 예시에서는 수열 {6, 6, 6, 5}가 반복됩니다.
- 반복되는 수열의 길이는 (K+1)로 위의 예시에서는 4가 됩니다.
- 따라서 M (K + 1)로 나눈 몫이 수열이 반복되는 횟수가 됩니다.
- 다시 여기에 K를 곱해주면 가장 큰 수가 등장하는 횟수가 됩니다.
- 이때 M이 (K + 1)로 나누어떨어지지 않는 경우도 고려해야 합니다.
- 그럴 때는 M을 (K + 1)로 나눈 나머지만큼 가장 큰 수가 추가로 더해지므로 이를 고려해주어야 합니다.
- 즉, ‘가장 큰 수가 더해지는 횟수’는 다음과 같습니다.
숫자 카드 게임
문제 정의
- 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.
- 숫자가 쓰인 카드들이 N X M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
- 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
- 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
- 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.
예를 들어 3×3 형태로 카드들이 다음과 같이 놓여 있다고 가정하자.
3 1 2
4 1 4
2 2 2
여기서 카드를 골라낼 행을 고를 때 첫 번째 혹은 두 번째 행을 선택하는 경우, 최종적으로 뽑는 카드는 1이다. 하지만 세 번째 행을 선택하는 경우 최종적으로 뽑는 카드는 2이다. 따라서 이 예제에서는 세 번째 행을 선택하여 숫자 2가 쓰여진 카드를 뽑는 것이 정답이다. 카드들이 N × M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오.
입력 조건
- 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1≤ N, M≤ 100)
- 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.
출력 조건
- 첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.
Test Case
[input]
2 4
7 3 1 8
3 3 3 4
[output]
3
My Solution
N, _ = map(int, input().split())
result = 0
for i in range(N):
dummy = min(list(map(int, input().split())))
result = max(dummy, result)
print(result)
- 이 문제를 푸는 아이디어는 바로 각 행마다 가장 작은 수를 찾은 뒤에 그 수중에서 가장 큰 수를 찾는 것 입니다.
- 입력 조건에서 입력으로 들어오는 수는 모두 10,000 이하이므로 단순히 배열에서 가장 작은 수를 찾는 기본 문법을 이용하여 각 행에서 가장 작은 수를 찾은 다음 그 수중에서 가장 큰 수를 찾는 방식으로 문제를 해결할 수 있습니다.
Solution 1
# 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) # 최종 답안 출력
Solution2
# 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이 될 때까지
문제 정의
- 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단,두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.
- N에서 1을 뺀다.
- N을 K로 나눈다.
예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이된다. 이는 N을 1로 만드는 최소 횟수이다.
N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.
입력 조건
- 첫째 줄에 N (2 N 100,000)과 K2 ≤K ≤ 100,000)가 공백으로 구분되며 각각 자연수로 주어진다.
- 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.
출력 조건
- 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.
Test Case
[input]
25 5
[output]
2
My Solution
n, k = map(int, input().split())
result = 0
while 1:
if n == 1:
break
result += 1
if n % k == 0:
n /= k
else:
n -= 1
print(result)
- 해당 문제는 주어진 N에 대하여 ‘최대한 많이 나누기’ 를 수행하면 됩니다.
- 왜냐하면 어떠한 수가 있을 때, ‘2 이상의 수로 나누는 것’이 ‘1을 빼는 것’보다 숫자를 훨씬 많이 줄일 수 있기 때문입니다.
- 문제에서는 K가 2 이상의 자연수이므로, 가능하면 나누는 것이 항상 더 숫자를 빠르게 줄이는 방법이 됩니다.
- 따라서 다음의 과정을 반복할 수 없을 때까지 반복하면 정답을 구할 수 있다.
- N이 K의 배수가 될 때까지 1씩 빼기
- N을 K로 나누기
예를 들어 N = 25, K=3 일 때는 다음과 같습니다.
| 단계 | 연산 과정 | N의 값 |
|---|---|---|
| 0단계(초기 단계) | N = 25 | |
| 1단계 | N에서 1 빼기 | N = 24 |
| 2단계 | N을 K로 나누기 | N = 8 |
| 3단계 | N에서 1 빼기 | N = 7 |
| 4단계 | N에서 1 빼기 | N = 6 |
| 5단계 | N을 K로 나누기 | N = 2 |
| 6단계 | N에서 1 빼기 | N = 1 |
6번의 과정으로 N = 1을 만들 수 있습니다.
Solution 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
while n > 1:
n -= 1
result += 1
print(result)
Solution2
# 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)
- 해당 코드는 N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식입니다.