[독서] 이것이 취업을 위한 코딩테스트다. (그리디)

1. 그리디 알고리즘 (Greedy Algorithm)

1.1 개념

• 정의: 매 순간 현재 상황에서 가장 좋은 선택을 반복하여 최적의 해를 구하는 알고리즘.
• 특징:
  • 이후의 상황은 고려하지 않음.
  • 문제 해결을 위한 최소한의 아이디어가 중요.
  • 정렬과 함께 자주 출제.

---

1.2 예제: 거스름돈 문제

문제

손님에게 거슬러 줘야 할 돈 N원을 최소 개수의 동전으로 거슬러 주기.
(500원, 100원, 50원, 10원 동전만 사용. N은 10의 배수.)

해결 방법

1. 가장 큰 단위의 동전부터 최대한 사용.
2. 차례로 작은 단위로 이동하며 최소 개수 계산.

파이썬 코드 예시

n = 1260
coins = [500, 100, 50, 10]
count = 0

for coin in coins:
    count += n // coin  # 해당 동전으로 최대 개수 계산
    n %= coin           # 남은 금액 계산

print(count)  # 출력: 6

• 설명:
  • 500원 → 2개, 100원 → 2개, 50원 → 1개, 10원 → 1개.
  • 총 6개 동전으로 해결.
• 핵심 아이디어:
  • 큰 단위의 동전이 작은 단위의 배수일 때, 그리디 방법으로 항상 최적해 보장.
  • 배수 형태가 아닐 경우, 다이나믹 프로그래밍 활용 필요.

---

1.3 예제: 큰 수의 법칙

문제

• 여러 숫자 중 가장 큰 수를 M번 더하여 최대 합 구하기.
• 특정 숫자는 K번 연속 사용 가능.

해결 방법

1. 가장 큰 수와 두 번째 큰 수 선택.
2. 반복 패턴 이용해 수열 생성.

파이썬 코드 예시

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort(reverse=True)

count = 0
total = 0
back_to_first = False
index = 0

for i in range(M):
    total += arr[index]
    count += 1

    if back_to_first:
        index = 0
        back_to_first = False

    if count == K:
        index = (index + 1) % len(arr)
        back_to_first = True
        count = 0

print(total)

---

1.4 예제: 숫자 카드 게임

문제

N × M 크기의 숫자 카드 배열에서 각 행의 최소값 중 최댓값 찾기.

해결 방법

1. 각 행에서 가장 작은 숫자 찾기.
2. 찾은 숫자들 중 최댓값 선택.

파이썬 코드 예시

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
arr_min_list = []

for i in range(N):
    arr_min_list.append(min(arr[i]))

print(max(arr_min_list))

 

• 설명:
  • 행별 최소값 구하기 → 최댓값 선택.
  • 핵심 아이디어: 최소값 중 최대값을 선택하여 안정적인 결과 보장.

---

1.5 예제: 1이 될 때까지

문제

N이 1이 될 때까지, N이 K로 나누어 떨어지면 나누고, 그렇지 않으면 1을 빼는 방식으로 연산을 수행.

최소 연산 횟수를 구하기.

해결 방법

1. N을 K로 나눌 수 있으면 나눔.
2. 그렇지 않으면 1을 빼고 반복.

파이썬 코드 예시

import sys
input = sys.stdin.readline

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

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

print(count)

설명

• N이 1이 될 때까지 나누거나 빼는 연산을 수행.
• 핵심 아이디어: 최대한 나누는 연산을 먼저 수행하여 연산 횟수를 줄임.

---

2. 그리디 알고리즘 적용 시 고려사항

1. 배수 관계 확인:
   • 화폐나 요소들이 배수 관계일 경우, 그리디 접근 가능.
   • 배수 관계가 아니라면 다이나믹 프로그래밍 활용.
2. 반복 수열 패턴 활용:
   • 특정 규칙 반복 시 효율적 접근 가능.
   • 예: 큰 수의 법칙 문제에서 패턴 반복으로 효율적 계산.
3. 코드 구현 효율성:
   • 입력 크기 및 시간 복잡도 고려 필수.
   • O(N) 또는 O(NlogN) 수준 유지 필요.