[코딩테스트] 요격 시스템

프로그래머스 lv.2 요격 시스템 문제를 풀어보았다.

 

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

프로그래머스

 

 

코딩테스트 준비를 시작한지 얼마 안된 상태에서 이런 문제를 보니 상당히 심란했다....

힌트를 보니 해당 문제는 그리디 알고리즘을 사용하면 굉장히 쉽게 풀리는 문제라고 한다. 

 

일단 정답으로 제출한 코드이다.

def solution(targets):
    answer = 0
    
    targets = sorted(targets)

    ran = targets[0][1]
    answer += 1
    
    for i in range(1, len(targets)):
        if ran <= targets[i][0]:
            ran = targets[i][1]
            answer += 1
        else:
            ran = min(ran, targets[i][1])
            
    return answer

 

targets 으로는 [시작점, 끝점]을 갖는 배열이 주어진다. (1) targets 을 시작점에 대해 오름차순으로 정렬해준다. 이때 삽입정렬 직접 구현해서 채점하니까 시간초과 나오더라...내장함수를 적극 활용하도록 하자. (2) 반복문을 타기 전 격추 미사일의 상한선을 정해준다. 첫 target의 끝점이 이에 해당한다. 그리고 필요한 미사일 개수 (answer) 를 +1 해주자. (3) 반복문에 들어가서 현재 범위 내에 미사일이 지나가면 범위 업데이트, 지나가지 않는다면 새로운 상한선을 설정해주고 answer +1 해주자.

 

 

그리디 알고리즘

 

최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

 

쉽게 말해 당장에 눈에 보이는 최적의 해만을 쫒아가는 방식이다. 이 알고리즘은 눈앞의 쉬운 문제에만 집중하기 때문에 큰 문제의 해를 쉽게 구할 수 있으나, 그게 전체 문제의 최적해라고 장담할 수는 없다. 

 

그리디 알고리즘으로 문제를 해결하기 위해서는 다음의 조건을 만족해야 한다. (만족하지 않는 경우, 근사해를 구하는 방법론도 존재한다.)

1. 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
2. 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

위 문제는 두가지 조건을 만족한다.

1. 이 문제에서는 각 단계에서 미사일이 최대한 많은 폭격 미사일을 요격할 수 있는 가장 왼쪽 끝 지점을 선택한다. 이 선택은 이후의 선택에 영향을 주지 않는다. 왜냐하면 한 번 미사일을 발사하면 해당 지점의 모든 폭격 미사일은 요격되고, 다음 단계에서는 새로운 구간에서 미사일을 발사하기 때문에 앞선 선택이 이후의 선택에 영향을 주지 않는다.

 

2. 각 단계에서 최적의 선택을 하면, 이는 전체 문제의 최적해를 이룬다. 즉, 각 단계에서 가장 오른쪽 끝에 있는 미사일을 제거하면, 이는 최소한의 미사일로 모든 폭격 미사일을 제거하는 최적해이다. 

 

따라서 그리디 알고리즘을 사용하여 풀 수 있는 문제이다.

(이 증명을 코테때마다 해야하는건가...?)