[이것이 코딩테스트다] 그리디(탐욕법)

📚 그리디 (Greedy) 알고리즘

'탐욕법'이라고도 소개되는 이 알고리즘은 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다.

• 단순하지만 강력한 문제 해결 방법
• 매 순간 가장 좋아보이는 것을 선택. 현재의 선택이 나중에 미칠 여향에 대해서는 고려하지 않는다.
• 보통 코딩 테스트에서 출제되는 그리디 알고리즘 문제는 창의력, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구

 

---

📃 [예제 1] 거스름돈

- 풀이시간 : 15분

 

- 문제풀이

n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인
list = [500, 100, 50, 10]

for coin in list:
    count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin

print(count)

화폐의 종류만큼 반복을 수행 => 시간 복잡도 O(K) 

이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고 거슬러 줘야 하는 금액의 크기와는 무관하다는 것을 알 수 있다.

 

- 정당성 확인

가지고 있는 동전 중에서 가장 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없다.

 

만약 서로 배수형태가 아니라 무작위로 주어진 경우 그리디알고리즘으로 해결 X => 다이나믹 프로그래밍으로 해결

 ex) 화폐단위가 500, 400, 100 이고 800원을 거슬러 줘야함.

• 그리디 알고리즘으로 풀었을 때 : 500원 + 100원 + 100원 + 100원
• 최적의 해 : 400원 + 400원

---

⚡ [문제 1] 큰 수의 법칙 

- 풀이시간: 30분

 

- 문제풀이

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 _ in range(k): # 가장 큰 수를 K번 더하기
    if m == 0 : break
    result += first
    m -= 1 
  if m == 0 : break
  result += second   # 두 번째로 큰 수를 한 번 더하기
  m -= 1
print(result)

입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장

'가장 큰 수를 K번 더하고 두 번째로 큰 수를 한번 더하는 연산'을 반복 수행

 

🙌 더 효율적인 문제 해결방법

M = 100억 이상이면 위의 소스코드는 시간 초과 판정

간단한 수학적 아이디어를 이용해 다음과 같이 문제를 더 효율적으로 해결할 수 있다.

 

예를 들어 N, M, K값과 입력값이 다음과 같을 때

• N = 5, M = 8, K = 3
• 입력값 = 2, 4, 5, 4, 6
• 가장 큰 수 : 6, 두 번째로 큰 수 : 5

정답은 (6 + 6 + 6 + 5) + (6 + 6 + 6 + 5) 으로 46이 된다.

 

1. 우선 반복되는 수열에 대해서 파악 (6 + 6 + 6 + 5)
2. 반복되는 수열의 길이는 (K + 1) 
3. M을 (K + 1) 로 나눈 몫이 반복되는 수열의 횟수 M / K+1 = 2
4. 다시 여기에 K를 곱해주면 가장 큰 수가 등장하는 횟수 (M / K+1) * K = 6
5. 만약 M이 (K + 1) 로 나누어떨어지지 않는 경우 (M % K+1) = 0

가장 큰 수가 더해지는 횟수(4번 + 5번의 합)

int(M / (K + 1)) * K + M % (K + 1) 

 

최종 풀이

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

# 가장 큰 수가 더해지는 횟수 계산
max  = int(m / (k + 1)) * k
max += m % (k + 1)      

# 가장 큰 수 더하기 + 두 번째로 큰 수 더하기
result = (first * max) + (second * (m-max))   

print(result)

 

---

⚡ [문제 2] 숫자 카드 게임 

- 풀이시간: 10분

 

- 문제풀이

# 1. 나의 풀이

n,m = map(int,input().split())
result = 0;

for i in range(n):
  data = list(map(int,input().split()))
  data.sort()                          # 정렬해서 최소값을 찾는 방식
  if data[0] > result:
    result = data[0]
print(result)


# 2. 교재 풀이

n,m = map(int,input().split())
result = 0;

for i in range(n):
  data = list(map(int,input().split()))
  result = max(result, min(data))      # min(), max() 함수를 이용해서 찾는 방식
print(result)

 

---

⚡ [문제 3] 1이 될 때까지 

- 풀이시간: 4분

 

- 문제풀이

# 1. 나의 풀이

n,k = map(int, input().split())
result = 0

while True:
  if n == 1: break
  if n % k == 0:
    n //= k
    result += 1
  else :
    n -= 1
    result += 1
print(result)    


# 2. 교재 풀이 (시간복잡도 O(NlogN))

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)    

 

-정당성 확인

K가 2 이상이기만 하면 K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N의 값을 줄일 수 있으며, N이 결국 1에 도달한다는 것을 알 수 있다.

 

---

🐾 정리

 위의 세 문제 모두 어렵지 않은 문제였지만, 얼마나 논리적으로 생각해서 알고리즘을 구현하느냐에 따라 코드 차이가 많이 나는 것을 느꼈다. 

마지막 문제 '1이 될 때까지' 는 N을 K로 나눌 수 있을 때와 없을 때를 if문을 사용하여 쉽게 구현했는데 이 소스코드는 N의 범위가 10만 이하이므로 빠르게 동작했지만, 만약 N이 100억 이상의 큰 수가 되는 경우를 가정했을 때는 교재풀이처럼 효율적으로 한 번에 빼는 방식으로 작성해줘야 통과했을 것이다.

 

 회사에서도 새로운 프로젝트는 들어가기 전 담당한 파트를 설계할 때, 과장님께서 늘 논리적으로 생각하고 접근해야한다고 말씀하셨는데 컴퓨터를 사용해서 뭐든 하려고 하면 컴퓨터적인 사고, 즉 논리적인 사고를 하는 것이 진리인 것 같다.

 

※ 해당 포스팅은「이것이 취업을 위한 코딩테스트다(나동빈 저)」책 내용을 바탕으로 작성하였습니다.