단속 카메라

송지용·2019년 4월 11일
0

algorithm

목록 보기
14/50

https://programmers.co.kr/learn/courses/30/lessons/42884

  • flow
    그리디 알고리즘? routes 리스트를 정렬한 후, 순서대로 겹치는 부분을 확인해 나아가면 될 듯함
    정렬 했을 때, 순서대로 A와 B가 겹치는 부분 존재하고, B와 C가 겹치는 부분 존재하면서 A와 C가 겹치지 않을 때, 그냥 A와 B가 겹치는 부분 아무곳이나 하나 카메라를 설치해도 최적화 해가 됨. C는 A와 B를 무시하고 그 다음 D, E 등등과 비교해 나아가면 됨.
    A와 B와 C가 모두 겹치는 부분이 있으면 그 부분을 D와 비교, 이런 식으로 정렬된 인덱스 순서대로 나아가면 부분해가 전체의 최적화 해가 되는 그리디 알고리즘 적용 가능한 문제
    시간 복잡도는 O(N) 이라 좋음

  • result
    https://github.com/songjy6565/alg-py/blob/master/programmers/level3/A7.py

0개의 댓글