[Greedy, Activation Selection Problem] 단속 카메라 - 프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/42884?language=python3 

코딩테스트 연습 - 단속카메라

 

[ 이 문제는 복습을 꼭 해보자 ]

 

첫 번째 시도

• 차량 이동 시간의 폭이 좁은 얘를 기준으로 정렬해서 접근
• 해당 시간대에 카메라를 위치시킴으로서 카메라의 갯수 최소화
• 어느 구간이 포함되는 지에 따라 routes 갱신

구현 코드

def check(route1, route2) : 
    if route1[0] > route2[1] or route1[1] < route2[0] : 
        return False
    return True

def solution(routes) : 
    answer = 0
    routes = sorted(routes, key=lambda x : abs(x[1]-x[0]))
    while routes : 
        answer += 1
        if len(routes) == 1 :break
        for i in routes[1:] : 
            if check(routes[0], i) : 
                routes.remove(i)
        routes.remove(routes[0])
    return answer

하지만 효율성 부분에서 통과를 못했는데 그 이유가 바로 시간 복잡도가 매우 크기 때문이다..!

 

이 알고리즘의 경우 최악의 경우 O(n^2)의 시간 복잡도를 가진다..!

 

이 문제는

Activity Selection Problem

유형과 유사하다고 한다.

 

이게 뭘까?

다음 포스팅을 참고해보고 추후에 공부하도록 하자.

https://www.zerocho.com/category/Algorithm/post/584ba5c9580277001862f188

 

 

이 활동 선택과 관련한 문제가 백준에 있다.

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

유명한 회의실 배정 문제다.

 

이 문제의 경우 다음과 같이 풀리게 된다...!

## 자체 input 제작
N = int(input())
routes = []
for i in range(N) : 
	car = [int(x) for x in input().split()]
	routes.append(car)

## Algortithm Start
## 우선 정렬, 끝나는 시간을 기점으로 정렬
routes = sorted(routes, key = lambda x : (x[1], x[0]))
## 같은 배정을 할 수 있는 지 여부 판단 기준 
criteria = routes[0][1]
## 첫 번째 배정 
routes.pop(0)
answer = 1

## greedy 
for route in routes :
	## 회의실을 추가 배정해야 하는 경우..! 
	if criteria <= route[0] : 
		answer += 1
		criteria = route[1]

print(answer)

 

시간 복잡도의 경우

정렬(nlogn) + route search(n) = O(nlogn)이 된다!!

 

이 유형화된 패턴을 가지고 단속 카메라 문제를 봐보자

 

비슷한 format으로 진행

 

구현 코드 by Activity Selection

def solution(routes) : 
    answer = 1
    routes = sorted(routes, key = lambda x : (x[0], x[1])) ## 시작점이 가장 작은 것 기준 정렬
    
    criteria = routes[0][1]
    
    routes.pop(0)
    
    for i in routes : 
        if i[0] <= criteria : criteria = min(i[1], criteria) ## 이 부분을 통해 점차 줄어듦을 구현 
            ## 보다 base한 경우로 내려감
            ## 그리고 이 때 기준 변환을 해둠..!
        ## 그리고 이 경우는 포함 관계에 속해지지 않는 경우..!
        else : 
            answer += 1
            criteria = i[1]
    
    return answer

Greedy 문제에서 이와 같이 정렬 기준으로 풀어내는 유사한 유형들이 있다!

무엇을 기준으로 정렬을 하고 어떻게 기준값을 바꾸어가며 greedy하게 최적해를 산출하는 지를 구하는 것이 중요!!