: 단순 무식하게, 탐욕적으로(현재 상황에서 지금 당장 좋은 것만 고르는 방법) 문제를 푸는 알고리즘
마트 카운터에는 거스름돈으로 사용 가능한 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원 일때, 거슬러 줘야 할 동전의 최소 개수를 구하는 프로그램을 작성하시오.
💡 풀이 아이디어
가장 큰 화폐 단위부터 돈을 거슬러준다.
N = int(input()
count = 0
coin_types = [500, 100, 50, 10]
for coin in coin_types :
count += (N // coin)
N %= coin
print(count)
1260
6
✓ 이 문제는 화폐의 종류만큼 반복을 수행하므로, 화폐의 종류가 개라 할때, 시간 복잡도는 가 된다. 즉, 이 알고리즘의 시간 복잡도는 동전의 총 종류 K에 대해서만 영향을 받고, 거슬러 주어야 할 금액 N의 크기와는 무관하다.
학생 A의 큰 수의 법칙은 '다양한 수로 이루어진 크기가 N인 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙'이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속으로 K번을 초과하여 더해질 수 없다. 또한 서로 다른 인덱스에 해당하는 수가 같은 경우 서로 다른 것으로 간주한다. 학생 A의 큰수에 법칙에 따른 결과를 출력하는 프로그램을 작성하시오.
## 내 풀이
n, m, k = map(int, input().split())
n_list = list(map(int, input().split()))
a = m//k # max(n_list)가 K번 더해진 덩어리의 최대 개수
b = m%k # n_list에서 두번쨰로 큰 숫자를 위의 덩어리 사이사이에 배치해야하는 개수
n_list_sorted = sorted(n_list)
n_list_sorted_set = set(n_list_sorted) # 두번째로 큰 수를 골라야하는데, 받은 리스트는 중복을 허용하므로 집합으로 중복 제거 수행
n_set_to_list = list(n_list_sorted_set) # 집합에서 인덱스 접근하려면 다시 리스트나 튜플로 변환해야함
res = (max(n_list)*k)*a + (n_set_to_list[-2]*b)
print(res)
5 8 3
2 4 5 4 6
46
답은 맞는데, 사실 중복을 제거할 필요가 없었다. 문제를 다시 읽어보면, "서로 다른 인덱스에 해당하는 수가 같은 경우 서로 다른 것으로 간주한다."라고 써져있다. 즉, 중복되는 수가 있어도 정렬만 되어있다면 해결 가능한 문제였다.
다시 풀어봄
## 내 풀이 (2)
n, m, k = map(int, input().split()) # n: n_list 원소 개수, m: 더하기 횟수, k: 같은수 연속 더하기 횟수
n_list = list(map(int, input().split()))
answer = 0
n_list = sorted(n_list, reverse = True) # 내림차순 정렬
while m > 0:
for i in range(k): # 반복문 시작할때마다 k는 복구되어야하므로 while말고 for문 사용
answer += n_list[0]
m -= 1
answer += n_list[1]
m -= 1
print(answer)
5 8 3
2 4 5 4 6
46
💡 풀이 아이디어
반복되는 수열에 대해서 파악하기
여기서 반복되는 수열은 가장 큰수와 두 번째로 큰 수가 묶음으로 반복되는 것이다. 반복되는 수열의 길이는(k+1)
이 된다.
수열이 반복되는 횟수는m % (k+1)
이 된다.
m
이(k+1)
로 나누어 떨어지지 않는 경우에는m % (k+1)
만큼 가장 큰 수가 추가로 더해진다.
즉, 가장 큰 수가 더해지는 횟수는int(m/(k+1)) * k + m % (k+1)
이다.
## 모범답안
n, m, k = map(int, input().split())
n_list = list(map(int, input().split()))
n_list.sort()
first = data[-1] # 가장 큰 수
second = data[-2] # 두 번째로 큰 수
cnt = int(m/(k+1))*k # 가장 큰 수가 더해지는 횟수
cnt += m % (k+1)
result = (first * cnt) + (m - cnt)*second
print(result)
5 8 3
2 4 5 4 6
46
N x M으로 놓인 카드들 중에서 아래 게임 규칙에 맞게 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 프로그램을 작성하시오.
1. 숫자가 쓰인 카드들이 N x M 형태로 놓여있다. 먼저 뽑고자 하는 카드가 포함되어있는 행을 선택한다.
2. 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑는다.
💡풀이 아이디어
각 행에서 가장 숫자가 낮은 카드를 모아 별도의 리스트에 담은 다음, 그 리스트의 최대값을 출력하게 만들었다.
## 내 풀이
n, m = map(int, input().split())
card = [map(int, input().split()) for _ in range(n)]
lowest = []
for i in range(n):
card_n = sorted(card[i])
lowest.append(card_n[0])
print(max(lowest))
2 4
7 3 1 8
3 3 3 4
3
## 모범답안 (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 4
7 3 1 8
3 3 3 4
3
## 모범답안 (2) - 2중 반복문 사용
n, m = map(int, input().split())
result = 0
for i in range(n) :
data = list(map(int, input().split()))
# 현재 줄에서 가장 작은 수 찾기
min_value = 10001
for x in data:
min_value = min(min_value, x)
result = max(result, min_value)
print(result)
2 4
7 3 1 8
3 3 3 4
3
어떤 수 N이 1이 될 때까지 아래의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야하는 최소 연산 횟수를 구하는 프로그램을 작성하시오.
1. N에서 1을 뺀다.
2. N을 K로 나눈다. (N이 K로 나누어떨어질 때만 사용 가능)
💡 풀이 아이디어
최대한 k로 나눌 수 있을 때 까지 나누고 -1 연산 수행하기
## 내 풀이
n, k = map(int, input().split())
cnt = 0
while n > 1 :
if n % k == 0:
n //= k
cnt += 1
else:
n -= 1
cnt += 1
print(cnt)
25 5
2
## 모범답안 (1)
n, k = map(int, input().split())
cnt = 0
# n이 k이상이라면 최대한 k로 계속 나누기
while n >= k:
# n이 k로 나누어 떨어지지 않을 경우 먼저 1 빼기
if n % k != 0:
n -= 1
cnt += 1
n //= k
cnt += 1
# 마지막으로 남은 수에 대해 1 빼기
while n > 1:
n -= 1
cnt += 1
print(cnt)
## 모범답안 (2)
n, k = map(int, input().split())
cnt = 0
while True:
# n이 k로 나누어 떨어지는 수가 될 때 까지 1씩 빼기
target = (n//k) * k
cnt += (n-target)
n = target
# n을 더이상 k로 나눌 수 없을 때 : 반복문 탈출
if n < k :
break
# k로 나누기
cnt += 1
n //= k
# 마지막으로 남은 수에 대해 1씩 빼기
cnt += (n-1)
print(cnt)
사실 모범답안(2)는 온전히 이해하지 못했다. 왜 target
이라는 변수를 따로 두어 작업을 추가했는지 모르겠다.(혹시 아시는 분은 댓글 남겨주세요..😭)