코딩고치

1. 문제 주소: https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 문제 유형: BFS, 이진 탐색 중량 제한이 1,000,000,000이므로 일반적인 탐색으로 풀 수 없음 log나 $\sqrt{}$를 이용하는 방식으로 풀여야 함 (약 3,000,000개로 연산이 줄어듦) 각 노드와 간선을 입력받은 후 중량의 최댓값과 최솟값을 찾음 BFS로 간선을 확인하면서 현재 중량으로 다리를 건널 수 있는지 확..

1. 문제 주소: https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 � www.acmicpc.net 문제 유형: 2진 탐색 집의 좌표가 1,000,000,000이므로 이진 탐색을 이용해야 함 시간 복잡도: O(NlogX) 공유기 사이의 거리의 최솟값과 최댓값을 계산 최솟값과 최댓값을 이용하여 중간값을 계산 중간값을 이용하여 c개만큼의 공유기를 설치할 수 있는지 확인 설치할 수 있으면 최솟값 = 중간값 + 1, 설치할 수 없..

이진 탐색 (Binary Search) 자료를 둘로 나누어 탐색하는 방법이다. 숫자가 정렬되어있는 상태여야 한다. 중간부터 시작하여 그 수보다 큰 쪽에 있는지 작은 쪽에 있는지 확인한다. 이를 반복하여 찾아 나간다. 분할 정복과 이진 탐색 분할 정복 알고리즘 (Divide and Conquer) Divide: 문제를 나눈다. Conquer: 문제가 작고 해결 가능하면 해결하고 아니면 다시 나눈다. 이진 탐색 Divde: 리스트를 두개로 나눈다. Conquer 중간값 보다 크면 큰 부분에서 검색할 숫자를 찾는다. 중간값보다 작으면 작은 부분에서 검색할 숫자를 찾는다. 알고리즘 구현 def binary_search(num_list, value): print(num_list) if len(num_list) =..