🔥이 시리즈는 한빛 미디어-'이것이 코딩 테스트다'의 모든 문제를 풀고, 회고합니다!
생각보다 짧은 실력에 깜짝 놀랄수도 있습니다..
이제 발등에 불떨어진 막학기 대학생이 뭐라도 해보는 중 입니다. 최대한 하루에 하나씩 올리는 것을 목표로 하고 있습니다.
1. 그리디 알고리즘
많은 회사의 코딩테스트에서 빠지지 않고 등장하는 알고리즘입니다. 현재 상황에서 가장 좋은 것을 선택하는 알고리즘입니다.
가장 흔한 그리디 알고리즘은 '가게 점원이 거스름돈을 줄 때 어떻게 하면 가장 적은 수의 동전을 거슬러 줄 수 있을까?' 이다.
그리디 알고리즘을 적용하면 '가장 큰 단위의 동전부터 거슬러 준다.'의 결과가 나온다.
이와 같이 현재의 상태에서 가장 좋은 판단을 하는 알고리즘을 그리디 알고리즘이라고 한다.
✏️ 큰수의 법칙
동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.
입력
- 첫째 줄에 N,M,K 의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
- 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1이상 10,000이하의 수로 주어진다.
- 입력으로 주어지는 K는 항상 M보다 작거나 같다.
출력
첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다.
# n = number of input value m = total iteration , k = iteration of big number
n, m ,k = map(int, input().split())
data = list(map(int,input().split())) # input array
data.sort() # sort array as ascending
first = data[n-1] # biggest number
second = data[n-2] # second biggest number
result = 0
while True:
for i in range(k):
result += first
m -= 1
if first == second:
for i in range(k):
result += first
m -= 1
else:
result += second
m -= 1
if m == 0:
break
print(result)
주어진 문제를 살펴보면서 가장 큰 값 두개만 사용된다는 것을 깨달았습니다. 가장 큰 값 두개가 같다면 (가장 큰 값 M) 이 정답입니다. 만약 그렇지 않다면 가장 큰 값 K 한후 두번째로 큰 값을 한번 더해주는 방식을 반복합니다.
If first == second : first x m
If first != second : first x k + second (총 m회)
가장 큰 값이 k번 곱해진후 그 다음 값이 1번 더해진다. 이를 총 m/(k+1) 번 반복한다. 나머지 값 역시 곱해준다.
이 문제를 더욱 효율적으로 풀기 위한 코드는 아래와 같습니다.
n, m ,k = map(int, input().split())
# n =number of input value m =total iteration ,k = iteration of big number
data = list(map(int,input().split())) # input array
data.sort() # sort array as ascending
count = int (m/(k+1))*k
count += int (m % (k+1))
result = data[n-1]*count + data[n-2]*(m-count)
print(result)✏️ 숫자 카드 게임
문제: 숫자가 쓰인 N x M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.
풀이
- 각 행을 한줄씩 입력받음과 동시에 각 행의 최소값을 찾아낸다.
- 최소값을 배열에 저장한다.
- 최소값의 배열 중 최대값을 찾아낸다.
별다른 고민없이 알고리즘을 짤 수 있었다.
n, m = map(int, input().split())
result =0
for i in range(n):
data = list(map(int,input().split())) array
min_value = min(data)
result = max(result, min_value)
print(result)다음 시간에는 남은 그리디 알고리즘을 풀어볼것이다.그 이후에는 구현문제들을 풀어볼 것이다.
