728x90 반응형 백준 알고리즘/이진 탐색3 [백준 1654 랜선 자르기][파이썬] Parametric Search (이분 탐색) 접근 방법 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 백준 1654번 문제는 이분 탐색을 이용하는 Parametric Search의 기본적인 문제이다. Parametric Search를 사용하기 위해서는 문제를 결정 문제로 바꿀 수 있어야 한다. 위 문제의 경우 자를 랜선의 길이를 임의로 x라고 했을 때 랜선 N개를 만들 수 있다면 True를, 없다면 False를 반환하는 문제로 바뀌게 된다. 그러면 이제 x의 최대 길이.. 2023. 3. 11. [백준 1300][파이썬] K번째 수 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 이진 탐색으로 해결할 수 있다. 1. 배열의 가장 작은 값(low)과 가장 큰 값(high)의 중간 값(mid)부터 탐색을 시작한다. 2. 해당 값보다 작은 값의 개수와 같은 값의 개수를 구한다. 3. k가 mid 값보다 작은 값의 개수와 해당 값과 같은 값의 개수 사이에 존재한다면 mid를 출력하고 끝낸다. 4. k가 mid 값보다 작은 값의 개수보다 작거나 같다면.. 2023. 3. 3. [백준 2110][파이썬] 공유기 설치 https://www.acmicpc.net/status?user_id=sungmin123&problem_id=2110&from_mine=1 채점 현황 www.acmicpc.net 이진 탐색으로 푸는 문제이다. 먼저 좌표를 정렬한다. 거리의 최솟값(low)은 1이고 거리의 최댓값(high)은 첫 번째 집부터 마지막 집까지의 거리이다. 두 값이 인자로 들어오면 그 중간값(mid)을 구하고 중간값이 조건에 부합하는지 확인한다. 부합한다면 첫 번째 인자로 mid+1, 두 번째 인자로 high를 넣어주고 다시 한 번 이진 탐색을 수행한다. low>high가 되는 순간 멈춘다. 이 문제에서 조금 까다로운 부분이 중간값이 조건에 부합하는지 확인하는 방법이다. 가장 인접한 두 공유기 사이의 거리가 중간값보다 크거나 같.. 2023. 3. 2. 이전 1 다음 728x90 반응형
