본문 바로가기

이분 탐색4

[백준] 1300번 K번째 수 (Python) 정답 코드 및 풀이는 맨 아래에 있습니다. https://www.acmicpc.net/problem/1300 '의외로 이분 탐색으로 풀 수 있는 놀라운 문제 1'라고 설명되는 문제이다. 실제로 그랬다. 구상이 상당히 어려웠다. 처음 보았을 땐 이분탐색 알고리즘으로 푸는 방법이 전혀 생각나지 않았다. 구상이 어려워 다른 풀이를 조금 참고하여 풀었다. [문제] 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B의 인덱스는 1부터 시작한다. [입력] 첫째 줄에 배열의 크기 N이 주어진다. N은 10^5보다 작거나 같은 자.. 2023. 2. 16.
[백준] 2110번 공유기 설치 (Python) 정답 코드 및 풀이는 맨 아래에 있습니다. https://www.acmicpc.net/problem/2110 이분 탐색 문제인 것을 알고 푸니까 쉽게 보였지만, 모르고 푼다면 구상하기에 꽤 어려울 것 같은 문제이다. [문제] 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x_1, ..., x_N이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이.. 2023. 2. 15.
[백준] 1654번 랜선 자르기 (Python) 정답 코드 및 풀이는 맨 아래에 있습니다. https://www.acmicpc.net/problem/1654 어렵지 않은 이분 탐색 문제였다. [문제] 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되.. 2023. 2. 15.
[백준] 1920번 수 찾기 (Python) 정답 코드 및 풀이는 맨 아래에 있습니다. https://www.acmicpc.net/problem/1920 쉬운 이분 탐색 문제였다. [문제] N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. [입력] 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다. [출력] M개의 줄에 답을 출력한다. 존재하면 1을, 존재하.. 2023. 2. 14.

티스토리툴바