[크래프톤 정글] TIL 18일차-그리디

그리디

<aside> 💡

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

</aside>

• 최단 경로, 다익스트라 알고리즘은 암기가 필요한 부분이다.
• 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’ 같은 기준을 알게 모르게 제시해준다.

예제 3-1 거스름돈

# 거슬러 줘야 할 돈 N원
N = int(input())

# 거스름돈 종류의 타입
coin_types = [500, 100, 50, 10]
result = 0

for coin in coin_types:
    result += N // coin 
    N %= coin

print(result)

• 가장 큰 화폐 단위부터 돈을 거슬러 주는 것.
• 화폐의 종류가 K개 라고 할 때 위 소스코드의 시간복잡도는 O(K)
• 즉, 동전의 총 종류에만 영향, 거슬러 줘야 하는 금액의 크기는 무관하다.
• 위 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

<aside> 💡

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

</aside>

실전 문제. 큰 수의 법칙

# 배열의 크기 N, 숫자가 더해지는 횟수 M, K+1번 초과할 수 없음.
N, M, K = map(int,input().split())

arr = list(map(int,input().split()))
arr.sort(reverse=True)
#print(arr)
# K가 1이여도 2개만 필요하다. (0,1 번째 인덱스)
# 만약에 M < K 이면 제일 큰 수 x K 하면 된다. 
result = 0 

if M <= K:
    result = arr[0] * M
else:
    # M // K 만큼 (큰 수 * K 번) 반복됨. + (M % K)번 만큼 두 번째 인덱스를 더함.
    result = (arr[0] * K) * (M//K) + (M % K) * arr[1]

print(result)

• 책에는 다른 풀이 1 가지와 유사한 풀이 1가지 총 2가지가 있다.
• 여기서 포인트는 3가지 정도 있다.

1. K가 M 크거나 같을 때와 그 외로 나눌 수 있다.
   • K ≥ M 이라면 큰 수를 더하는 횟수만큼 반복할 수 있기 때문이다.
   • 크다면 중간 중간 숫자를 섞어줘야 한다.
2. max() 를 사용하지 않은 이유는 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주하기 때문이다.
   • 따라서 정렬을 한 뒤 인덱스를 사용해 해결했다.
3. 수학적 수식으로 표현할 줄 알아야 했다. 어떻게 이 과정이 이루어질까 고민을 하면 충분히 가능했을 것이다.

실전 문제. 숫자 카드 게임

N, M = map(int, input().split())
result = 0

for _ in range(N):
    data = list(map(int, input().split()))  # 1
    min_value = min(data)                   # 2
    result = max(result, min_value)         # 3

print(result)

• 처음 든 생각은 리스트컨프리헨션을 사용해 2차원 배열을 초기화 해야될 까 생각했지만, 굳이 그럴 필요까지는 없다고 생각이 들었다. 그 이유는 각 행을 반복하며 가장 작은 수를 찾고, 찾은 수들 중 가장 큰 값만 반환하면 되기 때문이다.
• 여기서 포인트는 result = max(result, min_value) 문장을 이해했느냐이다.
• 설명을 하자면,
• 1 번째 문장은 각 행의 숫자 카드를 넣어주는 것이다.
• 2 번째 문장은 각 행에서 가장 작은 수를 찾는 것.
• 3 번쨰 문장은 result 값에 그 전의 숫자와 비교해 더 큰 값을 넣어주는 것이다.

실전 문제. 1이 될 때까지

# 어떤 수 N과 나눌 수 K
N, K = map(int,input().split())
count = 0

while True:
    if N == 1:
        break
    
    if N % K == 0:
        N //= K
    else:
        N -= 1
    
    count += 1

print(count)

• 여기서 파이썬에서 무언갈 종료하는 함수가 3가지 있다.
  1. break
     • 루프 내에서 사용: break는 루프(반복문)를 중단하고 루프 밖으로 빠져나올 때 사용됩니다.
     • 역할: 루프를 강제로 종료합니다. 조건에 맞을 때 반복을 멈추고 다음 코드를 실행할 수 있게 합니다.
     • 사용 예시

     for i in range(10):
         if i == 5:
             break  # i가 5일 때 루프를 종료합니다.
         print(i)  # 0부터 4까지만 출력됩니다.
     

  2. exit
     • 프로그램 종료: exit()는 Python 프로그램을 완전히 종료할 때 사용됩니다.
     • 역할: 프로그램 실행을 즉시 중단하고 시스템에 종료 신호를 보냅니다.
     • 사용 예시

     import sys
     if some_condition:
         sys.exit()  # 프로그램이 종료됩니다.
     

  3. return
     • 함수 내에서 사용: return은 함수에서 값을 반환하고 함수를 종료합니다.
     • 역할: 함수의 실행을 중단하고, 호출된 지점으로 값을 돌려줍니다.
     • 사용 예시

     def add(a, b):
         return a + b  # 함수 실행을 종료하고 결과를 반환
     result = add(3, 5)  # result는 8이 됩니다.
     

• 몇 번 반복할지 모르니 while 문을 사용해주었다.
• N 과 K 의 초기 값은 항상 2 이상 이므로 N == 1 일 때 break 해주어 영원히 반복되지 않게 하였다. (base case)
• 재귀 함수로도 구현 가능할 거 같아 시도해보겠다.

N, K = map(int,input().split())
count = 0

def find(num):
    global count 
    # base case 
    if num == 1:
        return count
    elif num % K == 0:
        find(num // K)
    else:
        find(num-1)
    
    count += 1

print(find(N))

• 출력 결과로 None 값이 나온다.
• return 을 해주어야 재귀 호출이 끝나면 그 값을 상위 함수로 전달하여 계속해서 값을 반환하도록 하기 위함이다. return 을 하지 않으면 재귀 호출의 결과가 상위 함수로 전달 되지 않는다.
• 그리고 조건마다 count += 1 을 해주어야 된다. 그 이유는 조건이 실행될 때 마다 그 수를 계산하기 위해서 이다.
• 소스 코드를 아래와 같이 수정해야 된다.

N, K = map(int,input().split())
count = 0

def find(num):
    global count 
    # base case 
    if num == 1:
        return count
    if num % K == 0:
        count += 1
        return find(num // K)
    else:
        count += 1
        return find(num-1)
    

print(find(N))

• 2가지 방법의 소스 코드들의 핵심은 최대한 많이 나누기이다. 그 이유는 문제에서 N이 1이 될 때까지 최소 횟수를 구하는 프로그램을 작성하도록 되어 있기 때문이다.
• 특정 양의 정수에서 최대한 많이 나누어야 최소 횟수가 되기 때문이다.
  • N과 K가 2 이상의 자연수이기 때문.

본문의 내용은 아래 책에서 더 자세하게 보실 수 있습니다. 

https://www.yes24.com/Product/Goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 예스24