🥇 Problem Solving/Binary Search

[Python] BOJ / 3020번 / 개똥벌레

3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 📝 풀이 장애물(석순과 종유석)로 가득찬 동굴을 개똥벌레가 통과하고자 할 때, 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간의 총 개수를 구하는 프로그램 이분 탐색 알고리즘을 통해 각각의 장애물(석순과 종유석)과 높이에 따라 파괴해야 하는 장애물의 첫 번째 인덱스를 구한 뒤 해당 인덱스를 통해 파괴해야 하는 장애물의 수를 구할 수 있음 석순(down)을 파괴하는 경우는 개똥벌레가 날아가는 높이(target)를 (i - 0.5)로 설정하여 구할 수 있으며 종..

[Python] BOJ / 12738번 / 가장 긴 증가하는 부분 수열 3

12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 📝 풀이 LIS 알고리즘 사용 DP 배열을 사용하여 구현할 경우 시간초과가 발생하므로 이분 탐색 알고리즘으로 구현 다만 배열을 정렬하면 안 됨 배열을 따로 생성한 뒤 해당 배열에 오름차순으로 값을 순서대로 추가하여주는 식으로 구현 문제에서 물어보는 건 '가장 긴 증가하는 수열의 길이'이므로 수열의 값과 순서는 상관 없으며 우리는 result 배열의 가장 끝 요소(수열에서 현재까지 찾은 가장 큰 수)만 비교해가며 값을 추가해주면 된다...

[Python] BOJ / 1939번 / 중량제한

1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 문제 N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다. 영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다...

[Python] BOJ / 2470번 / 두 용액

2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연..