[2025 1학기 알고리즘 스터디] 박현빈 #3주차

Greedy Algorithm

그리디 알고리즘(탐욕법, Greedy Algorithm)은 최적해를 구하기 위해 매 순간 최선의 선택을 하는 알고리즘입니다. 간단하게 현재 상황에서 가장 좋은 선택을 하는 방식으로 동작하며, 선택의 순간적인 최적해들이 전체적인 최적해가 되는 경우에 사용할 수 있습니다.

---

그리디 알고리즘의 특성

💡 그리디 알고리즘의 일반적인 특징은 "최적 부분 구조"와 "탐욕 선택 속성"입니다. 이 두 가지 특징이 성립하는 경우, 그리디 알고리즘을 이용해 최적해를 구할 수 있습니다.

 

탐욕적 선택 속성 (Greedy Choice Property): 현재 상황에서 가장 좋은 선택을 한다면 이후의 선택들이 어떻든 상관없이 전체적으로 최적해를 찾을 수 있는 성질을 말합니다. 즉, 당장의 최적 선택을 계속 반복하면 전체적인 최적해를 찾을 수 있다는 것입니다.

예를 들어, 다익스트라 알고리즘에서는 현재까지의 최단 거리를 기준으로 가장 짧은 거리를 가진 정점을 선택하면 전체적인 최단 경로를 찾을 수 있습니다.

최적 부분 구조 (Optimal Substructure): 전체 문제를 작은 부분 문제로 나눌 수 있으며, 작은 부분 문제들의 최적해를 조합하여 전체적인 최적해를 구할 수 있는 성질을 가지고 있습니다.

예를 들어, 다이나믹 프로그래밍에서는 최적 부분 구조를 이용해 큰 문제를 작은 문제로 쪼개어 해결할 수 있습니다.

---

우선순위 큐와의 관계

• 그리디 알고리즘은 문제를 풀다 보면 매순간 최선의 선택을 해야 한다. 이때 최선의 선택이 반복적으로 최대값, 최솟값을 찾는 연산이라면 이러한 연산은 우선순위 큐를 활용해야지만 데이터의 크기가 클 때 효율적일 수 있다. 그리디 알고리즘 관련 문제에서 우선순위 큐를 활용하는 문제가 자주 출제 된다는 점에서 중요하다.

---

그리디 알고리즘의 종류에 대해 (with Chat Gpt)

Q. 정렬 알고리즘에는 여러 종류가 있었잖아? 그리디 알고리즘에도 여러 종류가 있어?

A. 정렬 알고리즘과는 달리, 그리디 알고리즘은 정형화된 여러 종류가 있는 것은 아닙니다. 그리디 알고리즘은 각각의 문제에 대해 최적해를 구하는 방법이므로, 문제의 성격에 따라 적절한 알고리즘을 선택하거나, 새로운 그리디 알고리즘을 개발해야 할 수도 있습니다. 하지만, 그리디 알고리즘의 일반적인 특징은 "최적 부분 구조"와 "탐욕 선택 속성"입니다. 이 두 가지 특징이 성립하는 경우, 그리디 알고리즘을 이용해 최적해를 구할 수 있습니다.

Q. 그니까 그리디 알고리즘은 하나의 방법론으로 종류가 있는것이 아니라 문제에 따라 새로운 방법을 적용해야 한다는거지?

A. 맞습니다. 그리디 알고리즘은 각 상황에 맞게 최적의 선택을 하는 알고리즘이므로, 문제에 따라서 그리디 알고리즘을 적용하는 방법이 다를 수 있습니다. 따라서 그리디 알고리즘은 "어떻게 선택을 하는가"보다는 "어떤 선택을 하는가"가 중요한 것입니다.

 

1931 회의실 배정

import sys
import heapq

n = int(sys.stdin.readline().strip())   # 전체 회의실의 개수
min_heap = []

for _ in range(n):

    # 강의 종료, 시작시간으로 분활
    start, end = map(int, sys.stdin.readline().split())

    heapq.heappush(min_heap, (end, start))

now_time = 0
cnt = 0
while min_heap:

    # 현재 가장 빨리 끝나는 강의 시간
    end, start = heapq.heappop(min_heap)

    # 강의를 시작 가능할때
    if start >= now_time:
        now_time = end
        cnt += 1

print(cnt)

---

 

• 코드 설명
  • 본 문제는 최대한 많은 회의를 참가하는 것이 목표다.
  • 시작 할 수 있는 강의중에서 가장 빨리 끝나는 강의를 찾는 과정을 반복하면 쉽게 문제를 해결할 수 있다. 
  • 강의 종료 시간을 최솟값으로 반복적으로 구할때 효율적인 자료구조인 최소힙을 사용하였다. 

 

1541 잃어버린 괄호

import sys

# 그리디 알고리즘

formula_list = sys.stdin.readline().strip()
formula_list = formula_list.split("-")
number_list = []

index = 0
all_sum = 0
# -를 기준 으로 식 전체를 나눈다.
for formula in formula_list:   

    # 받아온 식은 문자열 임으로 값을 더하기 위해 다시 +를 기준으로 나눈다.
    number_list = formula.split("+")   
    number_sum = 0
    
    for number in number_list:
        number_sum += int(number)

    if index == 0:  # 첫번째 인 경우 더 합니다.
        all_sum += number_sum
    else:           # 그를 재외한 모든 경우는 뺍니다.
        all_sum -= number_sum
    index += 1

print(all_sum)

• 코드 설명
  • 수식이 주어지고 수식에 임의 가로를 작성해서 최솟값이 되도록 해야한다.
  • 최소가 되기 위해서는 -1 * (연산식) 형태여야 한다. 연산식은 항상 더하기만 가지고 있어야 최솟값을 출력할 수 있으므로 -뒤에 있는 수를 모두 합한뒤 -가 곱해지는 형태로 가야 한다는 것이다.
  • 그러기 위해서는 - 를 기준으로 split을 하여 합이 되는 모든 부분을 구한다.이렇게 나누게 되면 첫 번째 인덱스의 값만 앞에 -가 없기에 제외하고 모든 값을 더한뒤 -1 을 곱하면 최솟값을 구할 수 있다.
  • formula_list = [55-50+40] formula_list = formula_list.split("-") # ['55', '50+40']\

동전 0

import sys


number_case_count, target_cost = map(int, sys.stdin.readline().split())
number_list = []
counter = 0

for count in range(number_case_count):
    carrier = int(sys.stdin.readline().strip())
    if carrier > target_cost:
        break
    else:
        number_list.append(carrier)

index = len(number_list) - 1
while target_cost != 0:
    if number_list[index] > target_cost:
        index -= 1
    else:
        share = target_cost//number_list[index]
        target_cost -= number_list[index] * share
        counter += share


print(counter)

• 코드 설명
  • 문제의 목적은 동전의 개수를 최소로 사용하고자 한다. 이를 위해서는 가치가 큰 동전 부터 우선적으로 사용하면 된다.