프로그래머스 - 요격 시스템 [Python]

https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스

안녕하세요, 오늘은 프로그래머스 '요격 시스템' 문제에 대한 Python 풀이를 하겠습니다.

 

문제 이해

이 문제는 폭격 미사일을 최소한의 요격 미사일로 모두 요격하는 문제입니다. 각 폭격 미사일은 x축에 평행한 직선으로 표현되며, 요격 미사일은 이 직선을 관통하여 한 번에 여러 폭격 미사일을 요격할 수 있습니다. 문제에서 주어진 정보는 각 폭격 미사일의 시작점(s)와 끝점(e)입니다. 이 정보를 바탕으로 요격 미사일을 어디에서 발사할지 결정해야 합니다. 문제의 목표는 모든 폭격 미사일을 요격하는 데 필요한 최소한의 요격 미사일 개수를 찾는 것입니다.

 

문제 접근 방식

이 문제를 해결하기 위한 접근 방식은 그리디 알고리즘을 사용하는 것입니다. 그리디 알고리즘은 현재 상황에서 가장 최선의 선택을 하는 알고리즘입니다. 이 문제에서는 각 단계에서 끝점이 가장 작은 폭격 미사일을 먼저 요격하는 것이 최선의 선택입니다. 이렇게 하면 다음 폭격 미사일의 시작점이 이전에 요격한 폭격 미사일의 끝점보다 클 확률이 높아지므로, 가능한 많은 폭격 미사일을 한 번에 요격할 수 있게 됩니다. 

 

코드 작성

def solution(targets):
    targets.sort(key=lambda x: x[1])

    cnt, end = 0, 0
    for s, e in targets:
        if s >= end:
            cnt += 1
            end = e
    return cnt

 

코드 해설

코드는 다음과 같은 순서로 실행됩니다:

1. 주어진 폭격 미사일의 범위를 끝나는 지점에 대해 오름차순으로 정렬합니다.
2. 각 폭격 미사일을 순회하면서 해당 폭격 미사일의 시작점이 이전에 요격한 폭격 미사일의 끝점보다 크거나 같으면 요격 미사일을 발사합니다. 이때 요격 미사일의 개수를 하나 증가시킵니다.

 

마치며

이 문제는 그리디 알고리즘을 이해하고 사용하는 데 도움이 되는 문제 였습니다. 그리디 알고리즘은 간단하면서도 효과적인 해결책을 제공할 수 있는 알고리즘입니다.

하지만 그리디 알고리즘이 항상 최적의 해결책을 제공하는 것은 아니므로, 각 문제의 특성을 잘 파악하고 알고리즘을 선택해야 합니다.

 

이 문제를 통해 그리디 알고리즘은 너무 난해하다는 것을 느꼈습니다. 딱히 알고리즘 공식이 있는것도 아니고 내가 스스로 생각해서 최적의 해결책을 도출해야한다는게 어려웠습니다.  지금까지 알고리즘 문제를 풀어보며 느낀점은 그리디 알고리즘은 문제 이해하기 너무 어렵다는 것.. 예시에 있는 그림이 많은 도움이 되었습니다.