[Algorithm 이론] 그리디(Greedy)
단순하지만 강력한 문제 해결 방법인 그리디(Greedy)에 대해서 알아보자.
그리디(탐욕법)
: 현재 상황에서 지금 당장 좋은 것만 고르는 방법 (나중에 미칠 영향 생각 X)
- 문제에서 넌지시 가장 큰/작은 순서대로와 같은 기준 제시
- 문제 유형을 파악하기 어렵다면 그리디 알고리즘 의심
예제 3-1. 거스름돈
- 점원: 500원, 100원, 50원, 10원 무한히 존재
- 손님에게 거슬러 줘야할 돈 = N(원) = 10의 배수
- 손님에게 거슬러 줘야할 동전의 최소 개수는?
[나의 생각]
- 큰 동전부터 거슬러준다.
- 큰 동전으로 나누면 ‘몫 = 거슬러주는 동전 개수’ / ‘나머지 = 아직 거슬러 줘야할 돈’
- 나머지를 가지고 다음으로 큰 동전으로 나누고를 반복하여 가장 작은 동전까지 반복
[시간 복잡도]
- O(화폐의 종류의 수)
풀이
def get_rest_coin_count(n): # n=거슬러 줘야할 돈
coins = [500, 100, 50, 10] # 큰 동전부터 거슬러 줘야하기 때문에 내림차순 입력
coin_count = 0
for coin in coins:
coin_count += n // coin # 몫
n = n % coin # 나머지 (정수)
return coin_count
get_rest_coin_count(1200)
4
실전문제-1. 큰 수의 법칙
- 배열의 크기 N / 숫자가 더해지는 횟수 M / K번 연속해서 더할 수 없음
[입력 조건]
- 첫째 줄: $N(2<= N <= 1000), M(1 <= M <= 10000),K(1<= K <=10000)$의
자연수, 공백으로 구분 - 둘째 줄: N개의 자연수, 공백으로 구분, 1이상 10000이하의 수
- K는 항상 M보다 작거나 같다.
[나의 생각]
- 가장 큰 수(a) , 그 다음 큰 수(b) 추출
- (a+a+a+b) + (a+a+a+b) 이런 형식으로 반복 <=> (a*k + b)가 반복
- 즉, M // (K+1) = (a*k + b)가 반복된 횟수
- M % (K+1) = a가 추가적으로 더해져야할 횟수
[시간 복잡도]
- data.sort(): 퀵 정렬과 같은 효율적인 정렬 알고리즘을 사용하므로 O($n log n$)의 시간이 소요
풀이-1
n, m, k = map(int, input().split())
data = list(map(int, input().split()))
data.sort() # sorted(data)는 바로 저장안되어서 data = sorted(data)라고 해야함.
first = data[-1]
second = data[-2]
count_repeat = m // (k+1)
additional_add_fisrt = m % (k+1)
result = (first*k + second) * count_repeat + first*additional_add_fisrt
print(result)
46
풀이-2
# 문제에 제시된 데이터 입력
# n = 배열의 크기 / m : 숫자가 더해지는 횟수 / k번 초과해서 더할 수 없음
n, m, k = map(int, input().split())
data = list(map(int, input().split()))
# 데이터 정렬
data.sort()
# 가장 큰 수, 그 다음 큰 수 추출
first = data[-1]
second = data[-2]
result = 0
# 계산
while True:
for i in range(k):
# 더해지는 횟수가 0일 경우 바로 꺼버리기
if m == 0:
break
result += first
m -= 1
if m == 0:
break
result += second
m -= 1
print(result)
46
풀이-3
# 문제에 제시된 데이터 입력
# n = 배열의 크기 / m : 숫자가 더해지는 횟수 / k번 초과해서 더할 수 없음
n, m, k = map(int, input().split())
data = list(map(int, input().split()))
# 데이터 정렬
data.sort()
# 가장 큰 수, 그 다음 큰 수 추출
first = data[-1]
second = data[-2]
# 계산
count_first = ((m // (k+1)) * k) + (m % (k+1))
count_seonct = m - count_first
result = 0
result += count_first * first
result += count_seonct * second
print(result)
46
실전문제-2. 숫자 카드 게임
- 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한장을 뽑는 게임
- 카드 N행 M열 형태로 놓여있다.
- 뽑고자 하는 카드가 포함되어 있는 행 선택
- 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드 뽑아야함
- 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숮자의 카드를 뽑을 수 있도록 전략을 세워야한다.
[나의 생각]
- 문제가 이해안가서 답지를 봤었다….
문제 이해 능력을 키우는 것도 중요하다고 느끼게 되는 계기였다.
풀이
n, m = map(int, input().split()) # n개의 행, m개의 열
result = 0
for i in range(n): # 각 행별로 뽑아야하므로
data = list(map(int, input().split()))
min_val = min(data)
result = max(result, min_val)
print(result)
3
실전문제-3. 1이 될 때까지
- N이 1이 될때까지 두 과정 중 하나를 반복 수행
- N에서 1을 뺀다.
- N을 K로 나눈다. -> N이 K로 나누어 떨어질 때 선택
[입력 조건]
- 첫째 줄 : $N(2<= N <= 100000), K(2<= K <=100000), N >= K$의 자연수, 공백으로 구분
[나의 생각]
- N이 K의 배수가 되기만하면 1이 되는건 순식간임.
- 따라서 1번 과정으로 N이 K의 배수가 될때까지 진행(a번)
- 그 후, N이 K의 몇 배수인지 구함(b) -> 즉, a + b하면 됨
풀이-1
def count_cal(n, k):
n_cal = 0
rest = 0
# 배수가 아닐때 -1, 배수이면 break
while True:
if n % k != 0:
n += -1
n_cal += 1
else:
break
while n >= k:
n //= k
n_cal += 1
rest += (n % k)
# 마지막 남은 수 빼기
while rest > 1:
rest += -1
n_cal += 1
return n_cal
count_cal(150, 27)
1번째 while 문
n = 135, n_cal = 15
2번째 while 문
n = 5, n_cal = 16
20
풀이-2 노가다 방법
def count_cal(n, k):
n_cal = 0
while True:
if n % k != 0:
n += -1
n_cal += 1
else:
n = n / k
n_cal += 1
if n == 1:
break
return n_cal
count_cal(150, 27)
20
방법-3 예시 답안
n, k = map(int, input().split())
result = 0
while True:
# (N == K로 나누어떨어지는 수)가 될 때까지 1씩 뺴기 -> k의 배수로 만들기
target = (n // k) * k
result += (n - target)
n = target
# N이 K보다 작을때 탈출
if n < k:
break
# K로 나누기
result += 1
n //= k
# 마지막으로 남은 수 에 대해서 1씩 빼기
result += (n-1) # 1이 될때까지이므로 -1을 해준다.
print(result)
20
댓글남기기