PART02 - CHAPTER 03. 그리디

1. 당장 좋은 것만 선택하는 그리디

- 그리디 알고리즘은 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다.

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

- 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며,  현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

 

- 정렬, 최단 경로 등의 알고리즘 유형은 이미 알고리즘의 사용 방법을 정확히 알고 있어야만 해결 가능한 경우가 많다.

- 예를 들어 여러 개의 데이터를 빠르게 정렬해야 하는 문제는 정렬 라이브러리의 사용 방법을 알고 있어야한다.

    또 다른 예시로 최단 경로를 빠르게 찾아야 하는 문제는 플로이드 워셜 혹은 다익스트라 알고리즘과 같은 특정 알고리즘을 미리 알고 있어야한다.

 

- 그리디 알고리즘은 사전 지식 없이도 풀 수 있는 문제이지만, 많은 유형을 접해보고 문제를 풀어보며 훈련을 해야한다.

- 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다.

- 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

 

예제 3-1 거스르돈

n = 1260
count = 0

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

for coin in coin_types:
	count += n//coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin
    
print(count)

그리디 알고리즘의 정당성

- 대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

- 어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보자.

- 만약 오랜 시간을 고민해도 그리디 알고리즘으로 해결 방법을 찾을 수 없다면, 그때는 이후의 장에서 다루게 될 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지를 재차 고민해보는 것도 한 방법이다.

 

* 기업의 코딩 테스트를 안정적으로 통과하려면 다음에 소개되는 문제 각각에 대해 문제별 아이디어를 떠올리고 코드로 작성하기까지 시간이 30분 이내로 소요되어야 한다.

 

2. [실전문제] 큰 수의 법칙

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

# N, M, K를 공백으로 구분하여 입력받기
n, m, k = map(int, input().split())
# N개의 수를 공백으로 구분하여 입력받기
data = list(map(int, input().split()))

data.sort()	# 입력받은 수 정렬
first = data[n-1]	# 가장 큰 수
second = data[n-2]	# 두 번째로 큰 수

# 가장 큰 수가 더해지는 횟수 계산
count = int(m / (k+1)) * k
count += m % (k+1)

result = 0
result += (count) * first	# 가장 큰 수 더하기
result += (m - count) * second	# 두 번째로 큰 수 더하기

print(result)	# 최종 답안 출력

- m : 더해지는 횟수  , k : 반복가능한 횟수 , m/(k+1) : 한 사이클의 횟수 , m/(k+1) * k :  한 사이클의 횟수 x 반복횟수

   m%(k+1) : 사이클의 남은 횟수

 

3. [실전문제] 숫자 카드 게임

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

# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

result = 0
# 한 줄씩 입력받아 확인
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)

4. [실전문제] 1이 될 때까지

- 과정이 아니라 결과에 집중하자!

- '최대한 많이 나누기'

- 단순하게 푸는 답안 예시

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

# N이 K이상이라면 K로 계속 나누기
while n >= k:
    # N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기
    while n % k != 0:
        n -= 1
        result += 1
    # K로 나누기
    n //= k
    result += 1
    
# 마지막으로 남은 수에 대하여 1씩 빼기
while n > 1:
    n -= 1
    result += 1
    
print(result)

    ㆍ문제에서 N의 범위가 10만 이하이므로, 이처럼 일일이 1씩빼도 문제를 해결할 수 있다.

    ㆍ하지만 N이 100억 이상의 큰 수가 되는 경우를 가정했을 때에도 빠르게 동작할려면, N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식으로 소스 코드를 작성할 수 있다.

# N, K를 공백으로 구분하여 입력받기
n, k = map(int, input().split())
result = 0

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

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