그리디 알고리즘 (이것이 취업을 위한 코딩 테스트다)

이것이 취업을 위한 코딩 테스트다를 정리한 글입니다.

그리디 알고리즘

그리디 알고리즘은 “현재 상황에서 지금 당장 좋은 것만 고르는 방법”이다. 매 순간 가장 좋은 선택을 하고, 현재의 선택이 나중에 미칠 영향은 고려하지 않는 방법이다.

거스름돈

거스름돈 문제는 그리디 알고리즘을 잘 나타내는 문제이다.

상점에는 500원, 100원, 50원, 10원짜리 동전으로 거스름돈을 줄 수 있다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구한다. 단, 거슬러 줘야 할 돈은 항상 10의 배수이다.

def solution(n):
    '''
    :param n: 거스름돈
    :return: 동전 개수
    '''
    count = 0

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

    for coin in array:
        count += n // coin
        n %= coin

    return count

거스름돈을 큰 단위 화폐부터 나눠가며 몫과 나머지를 사용해 동전 개수를 더해 간다.

시간 복잡도 분석

• 화폐의 종류가 K라고 할 때, 소스코드의 시간 복잡도는 O(K)이다.
• 시간 복잡도는 거슬러줘야 하는 금액과는 상관이 없으며, 동전의 총 종류에만 영향을 받는다.

큰 수의 법칙

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

입력 조건

• 첫째 줄에 N(2≤N≤1,000), M(1≤K10,000), K(1≤K≤10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.
• 입력으로 주어지는 K는 항상 M보다 작거나 같다.

5 8 3
2 4 5 4 6

def solution(N, M, K, arr):
    lst.sort()

    first = lst[-1]
    second = lst[-2]

    result = 0

    while True:
        for i in range(K):
            if M == 0:  # M이 0이면 탈출
                break
            result += first
            M -= 1  # 더할 때마다 1씩 빼기
        if M == 0:  # M이 0이면 탈출
            break
        result += second  # 두 번재 큰 수를 한번 더하기
        M -= 1  # 더할때마다 1씩 빼기
    return result

리스트 중 큰 값과 다음으로 큰 값을 구하기 위해 정렬을 한 후 더해준다. 가장 큰 수를 연속으로 K번 더하게 구현하고 매번 더할 때마다 M을 줄여가며 연산한다. 하지만 이 풀이는 M의 크기가 커지면 시간 초과가 날 수 있다고 한다.

def solution2():
    n, m, k = map(int, input().split())
    data = list(map(int, input().split()))

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

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

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

    return result

count를 구해 가장 큰 수를 더할 횟수를 정하고 총 횟수 M에서 count를 빼 두 번째로 큰 수를 더할 횟수를 구해 큰 수를 구할 수 있다.

숫자 카드 게임

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

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

입력 조건

• 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1≤N, M≤100)
• 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.

3 3
3 1 2
4 1 4
2 2 2

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)

각 행에서 작은 값들을 뽑아낸 다음 result와 비교해서 큰 값을 갱신한다.

1이 될 때까지

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

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

N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하라.

입력 조건

• 첫째 줄에서 N(1 ≤ N ≤100,000)과 K(2 ≤ K ≤ 100,000)가 공백을 기준으로 하여 각각 자연수로 주어진다.

출력 조건

• 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

def solution():
    # 입력 받기
    n, k = map(int, input().split())

    result = 0

    while True:
        # N이 K로 나누어 떨어지는 수가 될 때까지 빼기
        target = (n // k) * k
        result += (n - target)
        n = target
        # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
        if n < k:
            break
        result += 1
        n //= k

    # 마지막으로 남은 수에 대해 1씩 빼기
    result += (n - 1)
    return result

N이 K로 나눠지는지 매번 확인하고 나눠지지 않으면 1을 빼는 방법으로 푸는 것이 가장 기본적인 생각일 것이다. 위 풀이는 K로 나눌 수 있는 만큼 나누고 result에 1을 얼마나 빼야 하는지를 한번에 계산한다. n이 k보다 작게 되면 반복문을 탈출하게 되고, result를 하나 줄여 결과를 반환한다.