알고리즘 코딩테스트/알고리즘 이론

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

문기문기! 2024. 4. 24. 15:11

그리디(Greedy) , 탐욕법

현재상황에서 지금 당장 좋은 것만 고르는 방법

매 순간 가장 좋아 보이는 것을 선택하며, 현재 선택이 나중에 미칠 영향을 고려하지 않음

 

 

출제방식

그리디 알고리즘은 "기준"에 따라 좋은 것을 선택하므로 문제에서

'가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 알게 모르게 제시해준다.

대체로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

 

 

그리디 알고리즘의 정당성

대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없기에 모든 알고리즘 문제에 적용할 수 없다. 거스름돈 문제(문제1)를 그리디 알고리즘으로 해결할 수 있는 이유는 "가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다" .

 

대부분의 그리디 알고리즘 문제에서 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

 

 

문제 1. 거스름돈

  • 카운터에 거스름돈으로 사용할 500,100,50,10원짜리 동전이 무한히 존재한다고 가정한다.
  • 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라.
  • 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다
n = 1260
count = 0

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

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

 

그리디 알고리즘을 이용해 푸는 대표적인 문제로 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 아이디어만 떠올릴 수 있다면 문제를 해결할 수 있다.

 

 

문제 2. 큰 수의 법칙

  • 주어진 수를 M번 더하여 큰수를 만드는 법칙
  • 단, 배열의 특정 인덱스에 해당하는 수가 연속해서 K번을 초과해서 더해질 수 없다
  • 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주
  • 예1) [2, 4, 5, 4, 6] 배열이 있을 때 M=8, K=3 이라면 6+6+6+5+6+6+6+5 = 46 이 된다.
  • 예2) [3, 4, 3, 4, 3] 배열이 있을 때 M=7, K=2 이라면 4+4+4+4+4+4+4 = 28 이 된다

 

# n, m, k 를 공백으로 구분하여 입력받기
n, m, k = map(int, input().split())

# N개의 수를 공백으로 구분하여 입력 받기
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)

 

반복되는 수열에 대해 파악해야 한다.

 

수열의 길이 : K+1

수열 반복 횟수 : M/(K+1)

수열에서 가장 큰 수 등장횟수 : (M/(K+1))*K

나누어 떨어지지 않는 경우 : M%(K+1)

큰 수가 더해지는 횟수 : (M/(K+1)) * K + M % (K+1)

 

 

문제 3. 숫자 카드 게임

  • 숫자 카드게임은 가장 높은 숫자가 쓰인 카드 한장을 뽑는 게임이다.
  • 숫자로 쓰인 카드들이 N * M 형태로 놓여 있다.
  • 먼저 뽑고자 하는 카드의 행을 선택하고, 선택된 행에서 가장 숫자가 낮은 카드를 뽑아야 한다.
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)

# 개인풀이
max = 0
# 한 줄씩 입력 받아 확인
for i in range(n):
    data =list(map(int, input().split()))
    # 바로 비교하기
    if max<min(data):
        max = min(data)

print(max)

 

각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾아서 해결할 수 있다.

 

 

문제 4. 1이 될 때 까지

  • 어떤 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 수행하려고 한다
  • 단, 두번쨰 연산은 나누어 떨어질때만 선택 할 수 있다
  • 연산 1. N에서 1을 뺀다
  • 연산 2. N을 K로 나눈다
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 

result += (n-1)
print(result)


# 개인풀이
result = 0
# N이 K 이상이라면 계속 나누기
while n >= k:
    if n%k == 0:
        # 결과값 int 반환
        n //= k
        result += 1
        if n == 1:
            break
    else:
        n-1
        result +=1
        if n == 1:
            break

print(result)

 

주어진 N에 대하여 '최대한 많이 나누기'를 수행해야 한다.

왜냐하면 '1을 빼는 것'보다 '2 이상의 수로 나누는 것'이 숫자를 훨씬 많이 줄일 수 있기 때문이다.

 

 

 

진~짜 면접준비로 인해 알고리즘 공부가 늦어졌다 하하;;; 

그리고 이번주 과제 테스트 시험이 있어 다음 공부도 좀 미뤄질듯? ㅎㅎㅎ