[ Python ] 이것이 코딩테스트다! | 당장 좋은 것만 선택하는 그리디

 

최근들어 나의 알고리즘 지식이 굉장히 빈약하다는 것을 깨닫고

책을 빌려 읽기 시작했다.

 

나동빈님이 쓰신 책이길래 우와! 하면서 계속 읽었던 것 같다. 나동빈씨,,, 정말 리스펙,,,

 

 

 

---

 

 

 

 

 

사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형

그리디 알고리즘

 

 

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 것을 말한다.

 

보통 코테에서 출제되는 그리디 알고리즘 유형 문제는

문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다고 한다.

 

 

즉, 문제를 접했을 때 단순하게 현재 상황에서 가장 좋아보이는 것만을 선택해도

문제를 풀 수 있는지를 파악할 수 있어야한다.

 

 

Tip !

 

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이기 때문에서

문제에서 힌트를 준다.

 

"가장 큰 순서대로", "가장 작은 순서대로" 와 같은 기준을 제시한다?

그럼 그리디 알고리즘 문제가 아닐까 의심해보도록 하자.

 

 

 

 

 

 

 

---

 

[실전 문제]

 

큰 수의 법칙

 

 

동빈이의 큰 수의 법칙은

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 m번 더하여 가장 큰 수를 만드는 법칙이다.

단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 k번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

 

 

 

자세한 문제는 이미 많은 분들이 올려놓았으니 문제 설명은 여기까지 하겠다.

 

 

5 8 3
2 4 5 4 6

 

input.txt 의 내용은 위와 같다.

 

import sys

sys.stdin = open('input.txt')

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):
        if m <= 0: break
        result += first
        m -= 1

    if m <= 0 : break
    result += second
    m -= 1

print(result)

 

 

내 처음 해답은 위 코드와 같이 작성되었는데,

책에서 내 코드의 문제를 정확하게 짚어내줬다.

 

 

문제는, m이 엄청나게 커진다면, 시간 초과 판정을 받을 수 있다는 것이다.

 

위 문제를 아래와 같이 수학적으로 더 간단하게 해석할 수 있다.

 

 

반복되는 수열로 생각해서,

가장 큰 수와 두 번째로 큰 수가 더해질 때는

특정한 수열 형태로 일정하게 반복해서 더해진다는 것을 캐치하는 것이다.

 

 

 위 예시에서는 수열 6,6,6,5가 반복된다.

 

반복되는 수열의 길이는 K+1 이다.

따라서 m 을 k+1 로 나눈 몫이 수열이 반복되는 횟수가 된다.

다시 여기에 k 를 곱하면 가장 큰 수가 등장하는 횟수가 되는 것이다.

 

 

새롭게 생각해낸 규칙을 바탕으로 코드를 작성해보자.

 

 

 

import sys

sys.stdin = open('input.txt')

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

data = list(map(int, input().split()))
data.sort()

first = data[n-1]
second = data[n-2]

cnt = int(m/(k+1))*k
cnt += m % (k+1)

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

print(result)

 

 

정말 짜릿하다... 반복문 없이 클린하다. 최고다 정말로..

그럼 다음 문제인 숫자 카드 게임을 풀어보자!

 

 

 

[실전 문제]

 

숫자 카드 게임

 

 

숫자 카드 게임은 여러 개의 숫자 카드 중에서

가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다.

 

룰은 다음과 같다.

 

 

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

 

 

이 문제 또한 자세한 설명은 하지 않도록 하겠다.

 

import sys

sys.stdin = open('input.txt')

n, m = map(int, input().split())
data = []

for _ in range(n):
    data.append(sorted(list(map(int,input().split())))[0])

data.sort()
print(data[n-1])

 

나는 코드를 이렇게 작성했다.

 

 

책에서는 아래와 같은 방법을 제시한다.

 

 

import sys

sys.stdin = open('input.txt')

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)

 

 

데이터가 많아질수록 sort 하는 시간이 오래 걸리니까, 아래 코드가 훨씬 좋아보인다.

읽기도 참 쉬운 것 같다!

 

 

 

 

[실전 문제]

 

1이 될 때 까지

 

 

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다.

단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.

 

 

 

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

 

 

 

이 문제는 주어진 N에 대해 최대한 많이 나누면 된다.

따라서 아래 과정을 반복할 수 없을 때까지 반복하면 정답을 구할 수 있다.

 

 

1. n이 k의 배수가 될 때까지 1씩 빼기
2. n을 k로 나누기

 

 

단순하게 풀면 아래와 같은 코드가 나온다.

 

 

 

import sys

sys.stdin = open('input.txt')

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

while n >= k:
    while n % k != 0:
        n -= 1
        result += 1
    n //= k
    result += 1

while n > 1:
    n -= 1
    result += 1
print(result)

 

 

위 코드를 큰 수에서도 가능하게끔 수정하면 아래와 같다.

 

 

 

import sys

sys.stdin = open('input.txt')

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

while True:
    target = (n // k) * k
    result += (n - target)
    n = target

    if n < k :
        break

    result += 1
    n //= k

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

 

 

while 문 내를 보면서 수학적으로 생각하는 그 느낌? 뉘앙스를 좀 익히면 좋을 것 같다!