이것이 코딩테스트다(그리디 편)

오늘은 그리디 편을 공부해 봤습니다.

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

그리디 예시 이미지

보통의 사람에 경우 가장 큰수인 128을 고르기 위해 오른쪽부터 고르지만 그리디 알고리즘은 현재 주어진 상황에서 가장 큰 수를 고르기에 16을 고르고 24를 고른다.

 

대표적인 문제 거스름돈 문제를 보겠다.

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원 10원 짜리 동전이 무한히 존재한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라, 단 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

 

나의 풀이 과정:

일단 나는 N의 가장 큰 단위부터 거슬러 줄것이다. N원을 거슬러 줘야할 때 500원부터 거슬러주고 나머지를 100원 나머지를 50원 나머지를 10원 짜리로 거슬러 줄것이다.

 

해당 파이썬 코드를 작성해보면

n=int(input())
count = 0

coin_type = [500, 100, 50, 10]

for coin in coin_type:
    count +=n//coin #500원짜리부터 몇개씩 줄수 있는지 count에 더한다.
    n %= coin
print(count)

 

실전문제 큰수의 법칙

‘서로 다른 수로 이루어진 배열에서 가장 큰수를 M번 더하여 가장 큰 수를 만드는 법칙이다. 수가 연속해서 k번을 초과할수도 없고 배열안에 같은 숫자가 있으면 서로 다른수로 판별한다.’

 

 

나의 풀이 과정:

1. 가장 큰수를 저장
2. 그다음으로 큰수를 저장
3. 가장큰수를 더하고 K번까지 반복 더할때마다 M-K를 한다. M이 0이 되면 그만하고 M이 0보다 크면 그다음으로 큰수를 더하고 다시 가장 큰수를 K번까지 반복

매우 단순한 방법이다. 별로 좋은 방법은 아니다. 

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
result += m*first
result -= (first-second)*(m%k)

print(result)

위에는 그냥 제일 큰수에 M번 곱한후 젤 큰수와 두번째 큰 수 차이만큼 반복되는 횟수의 나머지 만큼 빼준 값이다.

 

앞으론 그리디 문제라고 너무 단순하게만 접근하는게 아닌 시간복잡도를 최대한 줄여보는 방향성으로 생각해 볼 것이다.

 

실전 문제 숫자 카드 게임

숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한장을 뽑는 게임이다.

단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.

1. 숫자가 쓰인 카드들이 N * M 형태로 놓여 있다. 이때 N은 행의 개수를 의마하며, M은 열의 개수를 의미한다.
2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
3. 그다음 선택된행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
4. 따라서 처음에 카드를 골라낼 행을 선택할 떄, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 생각해야 한다.

나의 풀이 과정:

1. 한줄씩 입력 받으므로 가장 작은수를 저장
2. 입력 받을떄 더 큰 수를 입력 받을경우 그 수를 저장

n,m  = map(int, input().split())
result=0
for i in range(0,n):
    data = list(map(int, input().split()))
    if(result<min(data)):
        result=min(data)
    
    
print(result)

실전문제 1이 될때까지

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단 두번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

1. N에서 1을 뺀다.
2. N을 K로 나눈다.

 

나의 풀이 과정:

1. 나누어 떨어지는 안떨어지는지 체크
2. 나누어 떨어지면 나누고 안딸어지면 빼기 이걸 반복
3. N에서 K의 나머지를 구하고 나머지가 0이면 k를 나눠주고 아니면 1을 빼준다.

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

while True:
    target = n %m
    if(target !=0):
        result += target
        n -=target
    if (n<m):
        break
    result += 1
    n //= m 
    
result+=(n-1)
print(result)

 

한줄평:
오늘 그리디의 대해서 공부했는데 생각보다 단순하게 접근하기만 하면 좋은 시간복잡도를 얻을수 없어서 좀 더 많은 연습이 필요한것 같다.