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

Greedy 알고리즘

 

각 단계에서 최선이라고 생각되는 방법을 선택하는 알고리즘을 의미한다.

매 단계에서 local optimum를 선택하고 그 선택들이 모여서 global optimum이 되기를 기대하는 것이다.

 

Greedy 알고리즘이 global optimum을 도출하기 위해서는 앞 단계의 최선의 선택이 나중에 보았을 때도 최선이어야하는 탐욕적 선택 속성과 문제를 작은 부분 문제로 나눌수 있는 부분 최적 구조화가 이루어져야 한다.

 

1. 동전 0

 

앞선 문제보다 기본적인 문제여서 먼저 접근했다.

동전들을 조합해서 목표 금액을 맞추는 문제인데 못 맞추는 경우는 생각할 필요가 없는 문제인것 같아서 다소 쉬웠던것 같다.

 

time, total = map(int, input().split())
price_list = []
result_time = 0

for _ in range(time):
    price = int(input())
    price_list.append(price)
    
price_list.reverse()
# 금액이 낮은 순으로 입력되는데 큰 금액부터 생각하려고 뒤집음
# 최소 선택을 구하는 문제이기 때문에 빼줄 수 있는 가장 큰 수 부터 빼면서 진행

while (total != 0):
    for i in range(time):
        if price_list[i] > total:
            pass
        else:
            total -= price_list[i]
            result_time += 1
            break

print(result_time)

 

첫번째 시도에는 시간초과가 발생했다. 

아마도 같은 금액을 중복해서 빼주는 과정에서 시간이 많이 소모 된거 같다고 예상했고 그 부분을 수정했더니 문제가 풀렸다.

 

time, total = map(int, input().split())
price_list = []
result_time = 0

for _ in range(time):
    price = int(input())
    price_list.append(price)
    
price_list.reverse()    
while (total != 0):
    for i in range(time):
        if price_list[i] > total:
            pass
        else:
            t = total // price_list[i]
            total -= price_list[i]*t
            result_time += t
            break

print(result_time)

 

 Greedy 알고리즘을 공부하기 전에 문제를 풀었는데 어떨결에 greedy를 사용했다.

내가 사용한 코드에서는 total 금액을 낮춰가는 과정에 for 문을 도는데 같은 금액에 대해서 t번 도는 것을 수정한 코드에서는 한번만 도는 것으로 해결되었다.

 

time, total = map(int, input().split())
price_list = [int(input()) for _ in range(time)]
price_list.reverse()

result_time = 0

for price in price_list:
    if total >= price:
        count = total // price
        result_time += count
        total -= price * count

print(result_time)

 

필요없는 부분은 없애고 간결하게 만들었다.

 

2. 잃어버린 괄호

 

예를 들어 입력값이 55-50+40 이면은 값이 최소가 되어야하기 때문에 55-(50+40)이기 때문에 출력이 -35가 되어야한다.

이 문제를 푸는데 조금 까다로운 부분이 입력에 숫자와 문자가 한거번에 입력되고 숫자 009같은 숫자도 들어온다는 점이었다.

그나마 다행인점은 식의 길이가 최대 50이라는 점에서 시간오류는 왠만하면 안날 것 같았다.

line = input()
f_num = 0
num = ""
type_bool = False

for i in line:    

    if i == "+":
        num = int(num)
        if type_bool == True:
            f_num -= num
        else:
            f_num += num
        num = ""

    elif i == "-":
        num = int(num)
        if type_bool == True:
            f_num -= num
        else:
            f_num += num
        num = ""
        type_bool = True       

    else:
        num += i


if type_bool == True:
    f_num -= int(num)
else:
    f_num += int(num)

print(f_num)

 

부호가 나오기전까지 숫자는 num이라는 변수에 문자열로 더해진다.

부호가 나오는 시점에 int(num)을 통해 정수형으로 바꾸어준다.(이때 009같은 값은 9로 바뀜)

- 부호가 한번이라도 나온다면 그뒤에 숫자들은 모두 빼주어야한다.

그부분을 type_bool로 표현했고 그 외에는 더해주려고 하였다.

 

Greedy 방법을 사용해서도 문제를 풀어보았다.

- 기호 뒤에 모든 숫자와 덧셈을 하나의 그룹으로 묶어 한거번에 계산 할 수 있다.

예를 들어 1 + 2 - 3 + 4 + 5 - 6 + 7의 경우 1 + 2 - ( 3 +4 + 5 ) - ( 6 + 7 )로 바꾸어주는 것이다.

line = input()
# '-'로 쪼개기
parts = line.split('-')

# 첫 덩어리는 무조건 더함
result = sum(map(int, parts[0].split('+')))

# 나머지는 괄호로 묶어서 뺌
for part in parts[1:]:
    result -= sum(map(int, part.split('+')))

print(result)

 

- 를 기준으로 나눈뒤 map과 sum을 사용하면 다음과 같이 간단히 나눌수 있다.

 

3. 회의실 배정

 

이 문제를 풀려면 다음과 같은 생각을 지녀야 할 거 같다.

기준을 시작시점이 아니라 끝나는 시점으로 잡을 것 -> 회의가 끝나는 시점으로 기준을 잡으면 가능한 회의 시작가능한  시간을 중에서 최선의 방법을 택할 수 있다. 시작하는 시간을 기점으로 방법을 구하면 너무 많은 경우의 수를 구해야한다.(왜냐하면 선택한 경우가 최선의 방법이 아닐 수 있기 때문에 모든 방법 다 해봐야함, 그렇다면 회의 개수가 100,000인 시점에서 시간오류가 날 수 있음)

 

입력되는 회의 시작시간과 끝나는 시간에 대한 정보를 끝나는 시간에 맞추어 정렬하는게 이 문제를 푸는 첫 단추인 것 같다.

 

time = int(input())
t_list = []

for _ in range(time):
    start, end = map(int, input().split())
    t_list.append([start, end])

t_list.sort(key=lambda x: (x[1], x[0]))

count = 0
last_end = 0

for start, end in t_list:
    if start >= last_end:
        count += 1
        last_end = end


print(count)

 

 

t_list.sort(key=lambda x: (x[1], x[0]))x[1]이 부분을 통해 회의 끝나는 시간을 우선으로 정렬하고 x[0]이 부분으로 끝나는 시간이 같다면 시작시점으로 정렬한다.

 

 

마치며

Greedy 알고리즘을 공부하면서 느꼈던것은 다른 알고리즘과는 다르게 딱 정해져 있지 않는 느낌이었다. 위의 3문제를 풀때도 전혀 연관성을 찾지 못했고 그저 매 순간순간 선택 과정에서 최선의 결과를 찾아야만 했다. dp와 정렬 알고리즘과 달리 풀이법 보다는 사고방식이라는 생각이 들었고 더 열심히 공부해야겠다. 

 

끝