이진탐색 문제https://www.acmicpc.net/problem/17266💡 풀이코드 (성공) import sys import math N = int(sys.stdin.readline())M = int(sys.stdin.readline())light = list(map(int, sys.stdin.readline().split()))def binary_search(maxNum): left = 0 right = N answer = 0 while left mid = 길을 모두 비추기 위한 가로등의 최소 높이 주요 로직가로등이 비춰야 하는 거리 확인1 (시작-가로등, 가로등-끝)입력으로 배열에 가로등의 위치(x)만 들어간다. 그런데, 가로등-가로등 사이의 간격보다 길의 시작 위치-가..

MST / BFS + 이진탐색 문제https://www.acmicpc.net/problem/1939최소 신장 트리(MST)란?개념connected, weighted, undirected(양방향 가중 그래프)에서 정의되며, 신장 트리 중에서 가중치의 합이 최소가 되는 신장 트리이다.즉, 그래프에서 모든 정점을 포함하면서, 간선들의 가중치 합이 최소가 되는 트리를 의미한다. 최소 신장 트리 (가중치 합 : 8) 구현 방식MST를 구현하기 위해선 두개의 그리디 알고리즘을 사용할 수 있다. 1) Prim's Algorithm다엑스트라와 비슷한 방식이다.Dijkstra는 최단 경로를 찾는 알고리즘Prim은 최소 신장 트리를 찾는 알고리즘 (MST)자료구조 heap을 활용하여 최소 신장이 되도록 노드를 방문하는 식..

이분 탐색 문제https://www.acmicpc.net/problem/2512💡 풀이 코드 (성공)import sys n = int(sys.stdin.readline())arr = list(map(int, sys.stdin.readline().split()))amounts = int(sys.stdin.readline())def binary_search(n, arr, amounts): start = 1 end = max(arr) answer = 0 while start

이분 탐색 문제https://www.acmicpc.net/problem/2110문제 이해1. 요점문제의 요점은 다음과 같다.각 공유기 사이의 거리 및 간격이 최대가 되게끔 공유기 C개를 배치하라.즉, 공유기 C개를 각각 최대한 멀리 떨어뜨려라.이때 공유기 사이의 거리 및 간격이 각각 달라도 된다. 최대가 되게 공유기를 배치 후 이 중에서 최소값을 출력한다.결론적으로는 공유기들이 각각 최대한 멀리 떨어져 있어야 한다. 2. 예시9 31 2 3 4 5 6 7 8 100정답 : 7 (1 8 100)9 410 20 30 40 48 60 70 80 81정답 : 20 (10 30 60 80)9 41 2 3 4 5 6 7 15 100정답 : 6 (1 7 15 100)10 41 2 3 4 5 6 7 8 9 10정답 :..

이분 탐색 문제https://www.acmicpc.net/problem/1654💡 풀이코드 (성공)import sys K, N = map(int, sys.stdin.readline().split())lans = []for _ in range(K): lan = int(sys.stdin.readline()) lans.append(lan)def binary_search(K, N, lans): start = 1 end = max(lans) answer = 0 while start = N: start = mid + 1 answer = mid else: end = mid - 1 return answer..