문제
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.
제한사항
- 차량의 대수는 1대 이상 10,000대 이하입니다.
- routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
- 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
- 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.
문제를 보고 든 생각
도대체 이걸 어떻게 풀라는 건지.
너무 분했다. 진짜 뭘 어떻게 해야 할지 감도 안 왔다.
나의 아이디어
문제와 문제의 조건들을 계속 쳐다보며 생각을 거듭했고 문제의 예제를 전개해보며 겹치는 지점이 있다면(존재하기만 한다면) count를 해줘야 한다는 것은 알 수 있었다.
하지만, 그 정보만 가지고는 코드를 짤 수가 없었다.
중요한 건, 모든 차량이 감시카메라에 나올 수 있도록 해야 하는데 그걸 어떻게 체크해야 할지 모르겠어서 작성을 하지 못했다.
결과
부끄럽게도 어떠한 코드도 제출하지 못했다.
검색을 통해 알게 된 내용
탐욕법 문제에서 중요한 것은 최적의 해를 찾아내는 방법을 떠올리는 것이다. 그래서 문제를 푸는 데 필요한 어떤 정해진 흐름이랄 게 없이 최적의 알고리즘을 떠올리는 것이 탐욕법 문제에 대응하는 방법이다.
난 생각지도 못한 풀이들이 있는 것을 보았고 생각보다 너무나도 단순하게 문제를 푼 것을 목격할 수 있었다.
탐욕법에 대응하려면 진짜 그냥 많이 풀어보면 될까.
문제를 마주할 때마다, 방법이 도저히 생각이 나지가 않는다. 머리가 진짜 나쁜 거 같다.
반복이라도 해야지...
검색을 통해 알게 된 풀이
1. 첫 번째 O(n^2) 풀이
routes.sort(key=lambda x : x[1])
answer = 0
checked = [False] * len(routes)
for i in range(len(routes)):
if checked[i] == False:
answer += 1
camera = routes[i][1]
for j in range(i + 1, len(routes)):
if routes[j][0] <= camera <= routes[j][1] and checked[j] == False:
checked[j] = True
print(answer)그나마 내가 생각했던 방식과 비슷한 풀이다.
흐름은 아래와 같다.
a. 가장 먼저 진출 도로를 기준으로 정렬해줘야 한다. 이렇게 해야 겹치는 경로가 존재하는지 더 쉽게 체크할 수 있다.
b. 체크 배열은 차량의 수만큼 만들어준 후, for문을 진입할 때 아직 체크가 되지 않은 차량들만 for문에 진입할 수 있도록 한다.
c. 아직 체크하지 않은 차량이라면 감시카메라의 개수(answer)을 더해준다. 그리고 카메라는 현재 차량의 진출 지점에 설치해준다.
d. 위에서 설치해둔 감시카메라의 영향권에 들어가는 차량이 있는지 확인한다. 위에서 설치해둔 감시카메라의 영향권에 들어가는 차량이 존재한다면 그 차량을 체크한 것으로 한다.
e. b ~ d를 반복한다.
2. 선형 시간 풀이
routes.sort(key=lambda x : x[1])
answer = 0
camera = -30001
for route in routes:
if route[0] > camera:
camera = route[1]
answer += 1
print(answer)어이가 없어서 말도 안 나오는 풀이다.
이런 방식이 머릿속에 떠올랐어도 너무 간단한 나머지 나를 못 믿었을 것 같다.
이 방식이 통한다는 게 너무나도 놀랍다.
나도 이런 알고리즘을 떠올릴 수 있는 사람이 됐으면 좋겠다.
제발 탐욕법 잘하고 싶다.
코드의 흐름은 아래와 같다.
a. 첫 번째 코드와 동일하게, 동일한 이유로 진출 지점을 기준으로 정렬해준다.
b. camera를 -30001 지점으로 초기화한다. 이 이유는 조건상 최소 도로가 -30000인 점을 이용한 것이다.
아무리 작은 수의 도로 지점이 나와도 -30000이 최소이기 때문에 카메라 설치 지점이 나중에 인풋에 의해 무조건적으로 바뀔 수밖에 없게끔 변수를 초기화해준다.
c. for문 안에서, 현재 카메라가 설치된 지점과 현재 차량의 진입 시점의 도로 중 진입 시점의 도로 번호가 더 크다면 카메라의 위치를 그 차량의 진출 시점에 놓는다.
d. 그리고 카메라의 설치 수를 더해준다.
e. c ~ d를 반복한다.
이 풀이는 너무나도 직관적이다.
현재 카메라가 다음 차량의 진입, 진출 시점 사이에 있다면 설치하지 않고 진입 시점의 바깥에 있다면 설치하는 것이다.
느낀 점
탐욕법 문제에 내가 이렇게 약하구나라는 생각이 정말 많이 들었다.
완전 탐색, 정렬, 경로 탐색, 스택 등은 대충 어떤 식으로 코드를 작성하는지 흐름이 정해져 있는 반면
그런 흐름이랄 게 없고 문제를 파악해서 최대한 최적의 해를 뽑아낼 수 있는 방법을 생각해내야 하는 탐욕법, dp 문제는 내게 너무나도 높은 산처럼 느껴진다.
그래서 더 잘하고 싶다.
검색을 해서 답을 보면 그리고 그걸로 복습을 하면 나아지는 건 맞을까.
그냥 붙잡고 계속 생각해야 되는 걸까.