Greedy

Greedy

그리디 (탐욕법) : 현재 상황에서 지금 당장 좋은 것만 고르는 방법. 현재의 선택이 나중에 미칠 영향에 대해서는 고려 X

• ‘가장 큰 순서대로’, ‘가장 작은 순서대로’ 와 같은 기준을 제시
• 정렬 알고리즘과 짝을 이뤄 출제
• 대부분의 Greedy 알고리즘 문제에서는 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.
• 문제 유형을 바로 파악하기 어렵다면 Greedy를 의심해보고 그래도 해결 방법을 찾을 수 없다면 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 재차 고민해보자

아래는 Greedy 알고리즘을 사용하는 기본적인 문제 몇 개이다.

큰 수의 법칙

'''
배열에 주어진 수들을 m번 더해 가장 큰 수를 만듦
n 개의 자연수
m 번 더함
k : 특정 인덱스 연속 덧셈 가능 횟수

'''
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)

# 입력 예시
5 8 3
2 4 5 4 6

# 출력 예시
46

배열이 입력으로 주어지면 배열을 sort()함수를 이용해 정렬한다. 조건 없이 가장 큰 수를 만들어야 한다면 마지막 인덱스인 배열 중 가장 큰 수만 계속 더하면 된다. 하지만 최대 k번 까지만 연속 가능하니 가장 큰 수와 두번째로 큰 수만 더하면 된다.

배열이 [2 4 5 4 6] 일 때, 가장 큰 수 6과 두번째로 큰 수 5

6 6 6 5 6 6 6 5 이런식으로 덧셈 가능 -> 6 6 6 5 로 반복되는 수열이다. 그렇다면 반복되는 수열의 길이는 (K+1)이 된다.

• 수열이 반복되는 횟수 : M 을 (K+1)로 나눈 몫. M // (K+1)
• 가장 큰 수가 등장하는 횟수 : (M // (K+1) * K) + (M % (K+1))

숫자 카드 게임

'''
Rule
N x M -> 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)


# 2
'''
for i in range(n):
    data = list(map(int, input().split()))
    min_value = 10001
    for a in data:
        min_value = min(min_value, a)

    result = max(result, min_value)

print(result)
'''

# 입력 예시
3 3
1 5 4
3 5 8
9 10 11

# 출력 예시
9

n번(행 수)만큼 반복하는 for문 안에서 카드를 한 줄씩 입력받아 확인한다. min()을 사용하여 현재 줄에서 가장 작은 수를 찾은 뒤에 max()를 이용해 각 행 마다 가장 작은 수들 중 가장 큰 수를 찾는다.

1이 될 때 까지

'''
n을 1로 만드는 최소 횟수
1. n에서 1을 뺌
2. n을 k로 나눔 (n이 k로 나누어 떨어질 때만 가능)
'''

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

cnt = 0

# my
while True:

    if n % k == 0:
        n /= k
        cnt += 1
    elif n % k != 0:
        n -= 1
        cnt += 1
    if n == 1:
        break

print(cnt)

'''
# solution
# N이 K 이상이라면 K로 계속 나눔
while n >= k:
    # N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기
    while n % k != 0:
        n -= 1
        cnt += 1
    # K로 나누기
    n //= k
    cnt += 1

# 마지막 남은 수에 대하여 1씩 뺌    
while n > 1:
    n -= 1
    cnt += 1
    
print(cnt)
'''

위 코드는 내가 작성한 코드,

아래 코드는 정답 코드이다.