목록Algorithms/Greedy (2)
- 포함 관계에 대한 이해 필요 # return 최소 카메라 설치 갯수 # 차량: 1~ 10000 # [진입, 진출] # 진입, 진출 지점에 카메라 설치도 만난 것 # -30000 ~ 진입, 진출 ~ 30000 # 교점이 많은 부분에 설치하는게 이득 from copy import deepcopy def solution(routes): answer = 0 n = len(routes) check = [0] * n start = sorted(routes, key=lambda x: x[0])[0][0] end = sorted(routes, key=lambda x: x[1])[-1][1] checked = set() # 전체 구간 for idx in range(start, end+1): new_checked = ..
Kruskal 알고리즘 탐욕적인 방법을 이용해서 그래프의 모든 정점을 최소 비용으로 연결하는 방법 처음 시작하는 노드로 부터 하나의 간선을 선택해 간다. # 최소 비용으로 모든 섬 통행 # A -> B -> C # 오류 def solution(n, costs): total = 0 island = set() roots = [] costs = sorted(costs, key=lambda x: -x[2]) # 경로 리스트 while len(island) < n: r1, r2, c = costs.pop() if r1 in island and r2 in island: continue island.add(r1) island.add(r2) roots.append((r1,r2,c)) return total # 방문 리..