문제
한 번의 요격으로 최대한 많은 미사일을 맞추면서, 모든 미사일을 요격할 수 있는 최소 발사 횟수는?
- A 나라가 발사한 폭격 미사일은 x축에 평행한 직선 형태의 모양이며, 개구간을 나타내는 정수 쌍 (s, e) 형태로 표현된다.
- B 나라는 특정 x 좌표에서 y축에 평행이 되도록 미사일을 발사하며, 발사된 미사일은 해당 x 좌표에 걸쳐있는 모든 폭격 미사일을 관통하여 한 번에 요격할 수 있다.
즉, 여러 폭격 미사일들의 구간이 겹치는 공통 범위 안에서
요격 미사일을 쏘면, 그 범위와 겹치는 미사일들을 한 번에 여러 개 잡을 수 있어 유리하다.사용한 알고리즘
그리디 알고리즘
이 알고리즘은, 매 순간마다 지금 당장 가장 좋아 보이는 선택을 하고, 그 선택을 절대 번복하지 않는다.
문제를 풀 수 있는 모든 방법을 고려하며 최적 조합을 찾아내는 DP와 다르게 미래를 고려하지 않고 "지금 이 순간" 가장 좋은 선택을 한다.
예시) 0-1 배낭 문제(KnapSack Problem)와 그리디알고리즘
배낭과 물건이 있고, 이 배낭에는 물건을 담거나 담지 않거나 두가지 선택만을 할 수 있다.
이때 배낭의 제한 용량 안에서 담은 물건들이 가장 무거워 지려면 어떻게 해야할까?
그리디 알고리즘으로 무게 대비 가치가 높은 물건부터 순서대로 배낭에 채워 최적해를 구한다고 가정해보자.
그리디 알고리즘은 선택을 번복하지 않기에 물건을 담은 이후 빼지 않는다.
그렇기 때문에 당장 가치가 높아 보이는 큰 물건 하나를 담느라, 무게가 작은 물건 여러 개를 조합하여 더 큰 가치를 만드는 최적해는 구할 수 없는 경우가 생기기도 한다.
그리디 알고리즘은 ㅇㅇ이다.
- '가장 OO한 것'이라는 명확한 선택 기준이 있어야 한다.
- 한 번 선택한 것을 되돌리지 않아도 되어야 한다.
- 답을 구하기 위한 주요 로직에서 최초의 선택이 이후의 선택에도 영향을 주며, 최종 답까지 이어져야 한다
풀이과정
미사일을 e(끝점) 기준으로 정렬한 뒤, 가장 먼저 끝나는 미사일부터 요격한다.
"""
targets: 폭격 미사일의 x 좌표 범위 목록
s: start. 폭격 미사일의 x좌표 첫 시작
e : end. 폭격 미사일의 x좌표 끝점
"""
# 미사일 1개의 끝점을 가지고 오는 함수 매개변수의 이름은 ms로 함..ㅋㅋㅋ mㅣ sㅏ 일
def get_end(ms):
return ms[1]
# 미사일들을 끝점 기준으로 정렬한 뒤,
# 그리디하게 순회하며 필요한 최소 요격 횟수를 구하는 함수
def solution(targets):
targets.sort(key=get_end) # get_end 함수가 반환하는 값을 key값으로 정렬 (= ms[1]. 즉, 미사일 끝점을 기준으로 정렬)
result = 0 # 요격횟수
last_pos = None # 마지막 요격 위치
for s, e in targets: # targets의 각 원소 [시작점, 끝점]을 s, e로 구조분해하여 전체 순회
if last_pos is None or s >= last_pos: # 첫 요격이거나, 시작점(s)이 이전 요격 위치 이상이면 요격되지 않은 미사일이므로
result += 1 # 요격횟수를 증가시키고
last_pos = e # 마지막 요격 위치를 현재 미사일의 끝점(e)으로 갱신
return result # 이후 결과 반환
생각한 것
None vs -float('inf') vs 0
None은 숫자의 범위(0, 음수, 무한대 등)와 무관하게 항상 안전하지만,
0이나 특정 숫자로 초기화하는 방식은 문제의 제약조건에 맞아 떨어지는지 확인할 필요가 있다.
요격 로직 초기값(last_pos)을 뭘로 잡을지 세 가지 방법에 대해 생각했다.
- None: 값이 완전히 존재하지 않음
- -float('inf'): 무한대의 음수인 실수
- 0: 숫자값 0
"없다는 것"과 "숫자값이 0인 것", 그리고 "정수가 아닌 0 이하의 실수(음의 무한대)"는 서로 전혀 다른 개념이기에,이 세 가지의 의미를 명확히 구분하여 이해하고 있어야, 문제의 조건에 따라 적절한 값을 선택할 수 있다.
예를 들어 이 문제에서 미사일 구간의 시작점 s가 음수를 포함할 수 있는 조건이었다면, last_pos의 초기값을 0으로 설정하는 방식은 부적절했다.
s >= last_pos 비교에서 s가 음수(예: s = -222)로 주어질 경우, 이미 요격된 것으로 잘못 처리되는 오류가 발생하기 때문이다.
