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 ** 문제 유형 이진 탐색 ** 풀이 다리의 개수 M은 최대 100,000이며, 중량 제한 C는 최대 1,000,000,000 이진 탐색을 이용하여 O(M * logC)에 문제 해결 100,000 * 30 = 3,000,000 한번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 이진 탐색으로 찾음 반복적으로 중량을 설정하여, 이동이 가능한 경로를 찾음 최대 중량과 최소 중량 설정 중간값은 초기화할 때 최소 중량..

2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net ** 문제 유형 이진 탐색 ** 풀이 집의 개수 N은 최대 200,0000이면, 집의 좌표 X는 최대 1,000,000,000 이진 탐색을 이용하여 O(N*logX) 안에 문제 해결 200,000 * 30 ≒ 6,000,000 가장 인접한 두 공유기 사이의 최대 Gap을 이진 탐색으로 찾음 반복적으로 Gap을 설정하며, C개 이상의 공유기를 설치할 수 있는 경우를 찾음 최대 Gap = max / 최소 Gap =..

** 대표적인 탐색 알고리즘 - 순차 탐색, 해시, 이진 탐색 트리, 이진 탐색, ... ** 이진 탐색(Binary Search) 탐색할 자료를 둘로 나누어 해당 데이터가 있을 만한 곳을 탐색하는 방법 순차 탐색과 비교 ** 분할 정복 알고리즘과 이진 탐색 분할 정복 알고리즘 (Divide and Conquer) Divide: 문제를 하나 또는 둘 이상으로 나눈다. Conquer: 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다. 이진 탐색 Divide: 리스트를 두 개의 서브 리스트로 나눈다. Comquer 검색할 숫자 (search) > 중간값 이면, 뒷부분의 서브 리스트에서 검색할 숫자를 찾는다. 검색할 숫자 (search) < 중간값 이면, 앞부분의 서브 리스..