그리디 문제

Algorithm/Study

그리디 문제

ʕっ•ᴥ•ʔっ 프론트엔드 개발하는 쿼카 2023. 9. 9. 15:57

'당장 좋은 것만을 선택'하는 그리디

문제에서 '가장 큰 순서대로' 혹은 '가장 작은 순서대로'와 같은 기준을 제시한다면, 정렬 알고리즘을 사용한다. 이때, 그리디 알고리즘은 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

그리디의 대표적인 문제로는 '거스름돈 문제'이다.

거스름돈 예제에서의 시간 복잡도는 O(K)로 이때 K는 화폐의 종류이다. 즉, 이 알고리즘의 시간 복잡도는 화폐의 종류에 영향을 받는다.

실전 문제

1. 큰 수의 법칙

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

단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없음

ex) 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때, M이 8이고, K가 3이라고 가정하자.

이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5인 46이 된다.

단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주

ex) 3, 4, 3, 4, 3으로 이루어진 배열이 있을 때, M이 7이고, K가 2라고 가정.

이 경우 서로 다른 인덱스인 4를 번갈아 두 번씩 더하는 것이 가능하다. 결과적으로 4 + 4 + 4 + 4 + 4 + 4 + 4 인 28이 된다.

배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 떄 길동이의 큰 수의 법칙에 따른 결과를 출력하시오.

입력 조건

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

출력 조건

첫째 줄에 길동이의 큰 수의 법칙에 따라 더해진 답을 출력한다.

힌트

이 문제를 풀려면 가장 먼저 '반복되는 수열'에 대해서 파악해야 한다.

내가 쓴 답

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

data.sort(reverse = True)

K_count = 0
result = 0

for i in range(m):
    if K_count == k:
        K_count = 0
        result += data[1]
        continue
    K_count += 1
    result += data[0]


print(result)

해설

일단 배열을 정렬하는데, 거꾸로 정렬을 함으로써 가장 큰 수와 그 다음으로 큰 수를 구했다.

그리고 나서 for문 안에서 가장 큰 수를 사용하는 수를 사용할 때마다 count를 증가시키고 같아지면 count를 0으로 초기화시키고 두번째 수를 사용하였다.

2. 숫자 카드 게임

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

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

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

카드들이 N x M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오.

입력 조건

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

출력 조건

첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.

힌트

각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는다.

내가 쓴 답

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

min_list = []

for i in range(n):
    input_list = []
    input_list = list(map(int, input().split()))
    input_list.sort()
    min_list.append(input_list[0])

min_list.sort(reverse=True)

print(min_list[0])

해설

맨 처음에는 list를 먼저 입력받고 최소값을 추출하려고 했는데, 그러기에는 너무 복잡해지기도 하고 코드가 길어질 거 같아서

for문으로 list를 입력받고 정렬하여 가장 최소값을 min_list에 추가하였다.

그리고 for문을 마치고 min_list를 거꾸로 정렬하여 가장 큰 수를 찾았다.

하지만 해설을 보고나니, min함수와 max함수를 알게 되었고 이를 토대로 코드를 수정하였다.

3. 1이 될 때까지

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

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

예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다.

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

입력 조건

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

출력 조건

첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.

힌트

최대한 많이 나누기를 수행한다.

내가 쓴 답

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

while True:
    if n == 1:
        break

    if n % k == 0:
        n = n // k
        count += 1
        continue

    n -= 1
    count += 1

print(count)

해설

먼저 n이 1이 될때까지라고 했기 때문에 n이 1일 때는 while문을 나오게 했다.

그리고 k로 나누었을 때, 나머지가 0이 되면 count를 증가시키고 n을 k로 나눴을 때의 몫으로 했다.

만약 k로 나누었을 때, 나머지가 0이 아니라면 n에서 1을 빼고, count를 증가시켯다.