💁♀️ 탐욕 알고리즘?
-
여러 가지 선택지 중에서 어떤 선택이 최적의 해에 가까운지를 순차적으로 선택해 ( 전체적인 그림을 보지 않고 당장 눈앞에 있는 최적의 상황을 선택 ) 나가는 알고리즘이다.
-
순간마다 하는 선택은 그 순간에 대해서는 최적이지만, 최종적인 해답이 최적이라는 보장은 없다.
💁♀️ 어떤 문제를 탐욕 알고리즘으로 푸는 것이 적절한지 판단 ?
어떤 문제를 탐욕 알고리즘으로 푸는 것이 적절한지를 판단하는 것은 어렵습니다. 하지만, 일반적으로 다음과 같은 경우에는 탐욕 알고리즘이 적용될 가능성이 높습니다.
- 각 선택이 서로 영향을 주지 않는 경우
- 문제의 부분해가 전체해를 구하기 위한 최적해와 같은 구조를 가지는 경우
- 최적해를 구하기 위한 모든 가능성을 탐색하는 것이 현실적으로 불가능한 경우
📍 그러나 탐욕 알고리즘이 항상 최적해를 보장하는 것은 아니므로, 각 문제의 특성에 맞게 다양한 알고리즘을 고려하여 적절한 알고리즘을 선택해야 합니다.
💁♀️ 예시 문제
백준 1931: 회의실 문제
( 아래 코드는 백문 1931: 회의실 문제를 푼 코드는 아닙니다. )
T = int(input())
for tc in range(1, T + 1):
# 신청한 화물차 수
N = int(input())
# 화물차의 작업시간 s 종료시간 e
arr = [list(map(int, input().split())) for _ in range(N)]
# 오름차순 정렬
arr.sort(key=lambda x: x[1])
# end는 작업이 끝나는 시간
# arr[0][1]은 가장 먼저 종료되는 화물차의 종료시간.
end = arr[0][1]
# cnt : 운송할 수 있는 화물차의 수
cnt = 1
for i in range(1, N):
# 만약 다음 화물차의 시작시각이 가장 최근에 종료된 화물차의 종료시각에 같거나 클때
if arr[i][0] >= end:
# 작업이 끝난 시각은 arr[i][1] (for문으로 돌린 가장 최근 처리된 화물차의 종료시각)이 된다.
end = arr[i][1]
cnt += 1
print(f'#{tc}', cnt)📍 이 코드는 '화물차 운송' 문제를 해결하는 코드입니다.
-
주어진 N 대의 화물차가 각각 특정 작업 시간 s와 작업 종료 시간 e가 주어집니다. 이 때 가능한 한 많은 수의 화물차를 운송하기 위해서는 어떤 화물차를 먼저 운송해야 할지 결정해야 합니다.
-
이 코드는 그리디 알고리즘을 이용해 문제를 해결합니다. 먼저 주어진 화물차들을 종료 시간 e를 기준으로 정렬합니다. 그리고 가장 먼저 종료되는 화물차의 종료 시간을 end 변수에 저장합니다.
-
그리고 나머지 화물차들에 대해서, 현재 운송 중인 화물차가 종료된 후에 작업을 시작할 수 있는 화물차들 중에서 가장 먼저 종료되는 화물차를 선택합니다. 이 과정을 반복하면서, 선택된 화물차의 종료 시간을 end 변수에 저장하고, 운송할 수 있는 화물차의 수(cnt)를 1씩 증가시킵니다.
-
마지막으로, 운송할 수 있는 화물차의 수(cnt)를 출력합니다. 이 코드는 입력으로 여러 개의 테스트 케이스를 받아서 처리할 수 있도록 되어 있습니다. 각 테스트 케이스마다 '#'과 테스트 케이스 번호(tc)를 출력하고, 운송할 수 있는 화물차의 수(cnt)를 출력합니다.
💁 몰랐던 부분
arr.sort(key=lambda x: x[1])
- 정렬 기준을 지정하기 위해 'sort()'함수의 'key' 매개변수를 이용합니다.
- 'key' 매개변수에는 정렬 기준을 지정하는 함수를 전달할 수 있는데, 여기서는 람다(lambda) 함수를 이용하여 각 원소의 두 번째 값( 화물차 작업이 끝나는 시각 )을 반환하는 함수를 만들어서 정렬 기준으로 지정하였습니다.
- 즉, 'key=lambda x: x[1]'은 리스트 'arr'의 각 원소 'x'를 입력받아 그 중 두 번째 원소 'x[1]'를 반환하는 함수를 의미한다.
- 이 함수를 'sort()' 함수의 'key'매개변수로 전달하면, 'sort()'함수는 리스트 'arr'의 각 원소를 이 함수에 입력하여 반환된 값에 따라 오름차순으로 정렬된다.
