[이것이 코딩 테스트다] 그리디 알고리즘

네이버 AI 부스트캠프를 위한 코딩테스트 준비를

본격적으로 시작해보려고합니다.

 그동안 알고리즘에 대한 공부를 제대로 해본적이 없어서

 '이것이 코딩테스트다'를 다 끝내는 것을 목표로 열심히 공부해보겠습니다.

 

---

1. 그리디 알고리즘

그리디 알고리즘이라고 불리는 이 알고리즘을 그대로 해석하면 '탐욕법'입니다. '탐욕적인 알고리즘'이라는 것인데 이말은 현재 상황에서 지금 당장 좋은 것만 고르는 방법입니다. 즉, 직관적으로 봤을 때 좋아보이는 것만 고르다보면 알고리즘 문제가 해결된다는 것이죠!

 

그리디 알고리즘은 그리디 알고리즘임을 알면 매우 쉽게 문제를 해결할 수 있지만 그리디 알고리즘임을 알기가 쉽지 않습니다. 그만큼 문제 유형이 매우 다양합니다. 그래도 문제에 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 키워드를 알게 모르게 제시해주니 이를 잘 파악하는 것이 매우 중요합니다. 

 

또한, 그리디 알고리즘에서 중요한 것은 정당성을 파악하는 것입니다. 대부분의 그리디 알고리즘은 최소한의 아이디어로 문제 해결법이 눈에 보이는데 이런 해결법이 정당한지 검토할 수 있어야 합니다.

 

2. 문제

   2. 1 거스름돈 

카운터에  500원, 100원, 50원, 10원짜리 동전이 무한히 존재할때 손님에게 거슬러줄 동전의 최소 개수를 구하시오.

단, N은 항상 10의 배수이다.

 

모든 동전은 서로 배수 관계임으로 500원부터 차례대로 거슬러 주는 것이 가능함.

 

나의코드

N = int(input("거스름돈"))
coins=[500,100,50,10]
count=0
for coin in coins:
  count += N//coin
  N %= coin

print(count)

   2.2 큰 수의 법칙

다양한 수로 이루어진 배열이 있을때 주어진 수들을 M번 더하여 가장 큰 수를 만들어라. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번 초과하여 더해질 수 없다는 법칙이 있다.

 

나의 코드

n,m,k=map(int,input().split())
numbers=list(map(int, input().split()))

numbers.sort(reverse=True)
max=numbers[0]*k

idx=1
count=k
while count<m:
  if numbers[idx]<numbers[idx-1]: 
    max+=numbers[idx]
    idx-=1
    count+=1
  else:
    max+=numbers[idx]*k
    idx+=1
    count+=min(k,m-count)

print(max)

나의 코드를 보면 먼저 가장 큰 수를 k번 반복하고 이후 두번째로 작은 수를 한번 반복하고 다시 K번 가장 큰 수를 반복한 것을 볼 수 있다. 즉, 가장 큰 수 와 두번째로 큰 수만을 저장하여 반복하면 되는데 이를 파악하지 못했다.(해당 그리디 알고리즘의 정당성의 핵심이지만 어렴풋이 구현은 됐지만 이를 명확하게 생각하고 구현하지는 못했다.)

 

답안1

n,m,k=map(int,input().split())
numbers=list(map(int, input().split()))

numbers.sort()
first=numbers[n-1]
second=numbers[n-2]

while True:
    for i in range(k):
        if m==0:
            break
        result+=first
        m-=1
    if m==0:
        break
    result+=second
    m-=1

print(result)

첫번째 답안을 보면 첫번째로 가장 큰 수와 두번째로 가장 큰 수(두번째 인덱스)만 필요하다는 사실이 명확하게 나와있고 두 수의 반복으로만 나타나있다. 

 

답안2

# {첫번째로 큰수 k개, 두번째로 큰 수}가 계속해서 반복됨 즉,(k+1)개가 반복되는 구조
n,m,k=map(int,input().split())
numbers=list(map(int, input().split()))

numbers.sort()
first=numbers[n-1]
second=numbers[n-2]

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

result=0
result += first * count
result += (m-count)*second

print(result)

두번째 답안 코드는 반복 구조까지 파악하여 이를 통해 first, second의 개수를 파악하고 구하여 시간복잡도를 크게 단축시켰다.

 

   2.3 숫자카드 게임

숫자가 N x M으로 배열되어 있을 때 한 행을 선택하여 그 행에서 가장 작은 수를 선택한다. 이때 최종적으로 뽑은 수가 뽑을 수 있는 가장 높은 숫자여야한다.

 

나의 코드

n,m =map(int,input().split())
nums=[]
for i in range(n):
  c=list(map(int,input().split()))
  nums.append(min(c))

print(max(nums))

각 행마다 가장 작은 수를 별도의 nums 리스트에 넣고 이 중에서 가장 큰 값을 뽑았다.

 

답안

# 리스트에 넣어 max()를 사용하는 대신 max()로 수를 계속 비교하여 최대값을 찾을 수 있음.
n,m =map(int,input().split())
result=0
for i in range(n):
    c=list(map(int,input().split()))
    min_value=min(c)
    # 최댓값 찾기
    result=max(result,min_value)

print(result)

별도의 리스트를 생성하는 대신 행의 가장 작은 수를 max()를 통해 result와 비교하여 최정적으로 가장 큰 값만 남게함.

※ max()를 최대값을 구하기 위한 숫자들 비교로 사용할 수 있음

 

   2.4 1이 될 때까지

N이 1이 될 때까지 다음 두 과정을 반복한다. 

1. N에서 1을 뺀다.

2. N을 K로 나눈다.(단, N은 K로 나눠질때만!)

이때 N이 1이 되는 최소 횟수를 구하시오.

 

나의 코드

n,k=map(int,input().split())
count=0
while True:
  if n<k:
    break
  if n%k!=0:
    # 빼줘야하는 개수 구하기
    count+=n%k 
  n=n//k
  count+=1
  
while n>1:
  n-=1
  count +=1

print(count)

최소 회수는 결국 나누셈을 많이 할수록 유리하다. 즉, 먼저 나눠질 때까지 빼주고 나눠주고 안나눠지면 빼주고를 1이 될때까지 반복한다.

답안도 이와 큰 차이가 없다.