📍 출처 : 이것이 취업을 위한 코딩 테스트다, 나동빈, 2020
1. 거스름돈
- 500원, 100원, 50원, 10원
- N원을 거슬러줄때 최소 동전 개수는?
- 단, N은 10의 배수이다.
1.1 내 답안
N//coin==0인 경우도count += N//coin코드로 통일 가능
def exchange(N, coins = [500,100,50,10]):
count = 0
for coin in coins:
if N//coin == 0:
pass
else:
count += N//coin
N = N%coin
return count
print(exchange(1260, coins = [500,100,50,10]))1.2 책 답안
- 가장 큰 단위부터 작은 단위까지 순서대로 거슬러주기
- 그리디 알고리즘은 문제 해법을 찾았을 때 그 해법이 정당한지 검토
- Q. 큰 단위가 항상 작은 단위의 배수인가?
n = 1260
count = 0
coin_type = [500,100,50,10]
for coin in coin_type:
count += n//coin
n %= coin
print(count)
2. 큰수의 법칙
크기가 N인 배열을 입력받을 때
배열 내부 숫자들을 M번 더한 최대 값은?
단, 동일한 숫자는 연속해서 K번까지만 더할 수 있음. (인덱스가 다르면 다른 숫자로 간주)
N의 범위 : 2~1,000M의 범위 : 1~10,000
K의 범위 : 1~10,000배열 내부 자연수의 범위 : 1~10,000
2.1 내 답안
- 데이터 입력받는 부분 빠트림
- 가장 큰 수를 K번 더하고 두번째 큰 수를 한 번 더하는 연산하는건데, 만일 동일한 수열이 반복되는 형태가 아니라 조건이 추가된다면 while, for, 조건문으로도 풀 수 있어야할 듯
line1 = [5, 8, 3] #[N, M, K]
line2 = [2, 4, 5, 4, 6]
# 첫번째로 큰 수와 두번째로 큰 수만 이용.
line2 = sorted(line2, reverse=True)
first, second = line2[0], line2[1]
big = first * line1[2] + second
result = line1[1] // (line1[2] + 1) * big + line1[1] % (line1[2] + 1) * first
print(result)
2.2 책 답안
- 가장 큰 수 더하고 그 다음 두 번째로 큰 수 더함
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)2.3 책 답안, 단순하게 푸는 답안 예시
- M이 10,000 이하일 땐 시간 많이 안 걸리지만 M 커질수록 시간 많이 걸림.
n, m, k = map(int, input().split())
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
result += first
m -= 1
if m == 0:
break
result += second
m -= 1
print(result)3. 숫자 카드 게임
- 숫자가 쓰인 카드들이 N*M=(행개수)*(열개수) 형태로 놓여잇다.
- 행을 선택하고 카드를 뽑는데
- 선택된 행에 포함된 카드 중 가장 낮을 카드를 뽑아야한다.
- 이때 나올 수 있는 가장 큰 수는?
N과 M의 범위: 1이상 100이하카드의 숫자는 1이상 10,000이하의 자연수
3.1 내 답안
- data 한줄 씩 입력받을 때마다 처리할 수 있다는 생각 못했음
n, m = map(int, input().split())
data = []
for i in range(n):
data.append(list(map(int, input().split())))
min_num = [min(row) for row in data]
print(max(min_num))3.2 책 답안, min()을 이용하는 답안
- 한 줄 씩 입력받을 때마다 min_value 계산함.
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)
3.3 책 답안, 2중 반복문 구조를 이용하는 답안 예시
n, m = map(int, input().split())
result = 0
for i in range(n):
data = list(map(int, input().split()))
min_value = 10001 # 입력받는 수는 1~10,000 사이
for a in data:
min_value = min(a, min_value)
result = max(result, min_value)
print(result)4. 1이 될 때까지
어떠한 수 N이 1이 될 때까지 다음의 두 과정중 하나를 반복적으로 수행한다. 이 과정의 최소 횟수는?
1. N을 K로 나눈다.(단, N이 K로 나누어떨어질 때만)
2. N에서 1을 뺀다.
N의 범위 : 2~100,000K의 범위 : 2~100,000
N은 항상 K보다 크거나 같다.
4.1 내 답안
- 답안 4.3이랑 비교
n, k = map(int, input().split())
count = 0
while True:
if n%k == 0:
n /= k
else:
n -= 1
count += 1
if n==1:
break
print(count)
4.2 책 답안
- 주어진 N에 대하여 최대한 많이 나누는것. 이게 어떻게 최적의 해(최소 횟수)를 보장할까?
- K는 2 이상이라는 가정
- K로 나누는 것이 1을 빼는 것보다 N 값을 더 빨리 줄인다. - 하지만 N이 100억 이상의 큰 수라면 아래 코드는 시간이 많이 걸릴수 있다.
n, k = map(int, input().split())
result = 0
while n>=k:
# N 이 K로 나누어 떨어지지 않는다면 N에서 1을 빼기
while n % k != 0:
n -= 1
result += 1
n //= k
result += 1
# 마지막 남은 수에 대하여 1씩 빼기
while n > 1:
n -= 1
result += 1
print(result)4.3 책 답안, N이 클때는?
- 다음을 반복함. n<k 일때까지
- 1단계 : n이 k로 나누어 떨어질 때까지 1을 뺀다.
- 2단계 : n을 k로 나눈다.
- 마지막으로 남은 수에 대해 1씩 빼기 (총 n-1번)
- 내 답안과 비교) n에서 1빼는 작업을 한번에 함.
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로 나누기
n //= k
result += 1
# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n-1)
print(result)📍 실수 정리
- 내가 생각한 알고리즘 해법이 정당한지 어떻게 검토할까? 고민
DEEP DIVER