본문 바로가기

이분 탐색

 (18)
[Python] 9007번 카누 선수 https://www.acmicpc.net/problem/9007 9007번: 카누 선수 이 문제에서는 입력은 표준 입력을 사용한다. 입력의 첫 줄에는 T개의 테스트 케이스가 주어진다. 각 테스트 케이스에는 두 개의 정수 k와 n이 주어지며, k( 1 ≤ k ≤ 40,000,000)는 보트의 특정 값 그 www.acmicpc.net 23/12/27 중간에서 만나기(MITM) 연습 문제로 풀었던 문제이다. 문제 접근 방식: 전체적인 사고 방식은 이전에 풀었던 중간에서 만나기 기본 문제인 7453번 문제와 같다. 이 문제에 대한 해설은 아래와 같다. 2024.01.02 - [알고리즘/백준 문제 풀이] - [Python] 7453번 합이 0인 네 정수 [Python] 7453번 합이 0인 네 정수 https:..
[Python] 15573번 채굴 https://www.acmicpc.net/problem/15573 15573번: 채굴 첫째 줄에 N, M, K가 주어진다. (1 ≤ N, M ≤ 1000, 1 ≤ K ≤ N × M) 둘째 줄부터 맨 위의 광물들부터 순서대로 N줄 동안 M개의 광물의 강도 Si, j가 주어진다.(i = 1, 2, ..., www.acmicpc.net 23/12/31 2023년 마지막 날에 해결한 문제로, BFS와 이분 탐색을 섞은 파라메트릭 문제이다. 파라메트릭 서치 연습으로 아주 적절한 문제인 듯 하다. 문제 접근 방식: 문제에서 요구하는 것은 최솟값을 요구하고 있고, 이 값은 특정 값 이상을 넘어가는 최솟값이므로 파라메트릭 서치를 통해 구현할 수 있다. 채굴기의 성능 $D$와 광산의 모습을 입력으로 받아서 BFS를 통..
[Python] 7453번 합이 0인 네 정수 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 23/12/25 중간에서 만나기(Meet in the middle) 알고리즘 대표 문제이다. 그룹 연습문제를 풀기 위해서 기본 문제를 풀었다. 알고리즘 이름이 왜 중간에서 만나기인지 모르겠는데, 아직 문제를 덜 풀어서 그런가 그냥 분할 정복처럼 느껴진다. 문제 접근 방식: 1. 나이브한 접근 방식 나이브하게 저 조건을 만족하도록 $a, b, c, d$쌍을 찾기 위해선 $\math..
[Python] 20444번 색종이와 가위 https://www.acmicpc.net/problem/20444 20444번: 색종이와 가위 첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1) www.acmicpc.net 23/09/04 수학을 곁들인 이분 탐색 문제로, 이차방정식의 근의 공식을 떠올린다면 쉽게 해결할 수 있는 문제이다. 문제 접근 방식: 색종이를 잘라서 나오는 총 색종이 조각의 개수의 규칙을 먼저 관찰할 필요성이 있다. 색종이를 총 $N$번 자른다고 하면, 우리는 먼저 가로로만 $N$번 자를 수 있다. 그러면 조각이 $N+1$개가 나올 것이라는 사실을 충분히 알 수 있다. 마찬가지로, 가로로 $N-1$번, 세로로 $1$번을 자른다고 하면, 가로로 놓여진 $N$개의 조각이 $2$개로 나뉘므로,..
[Python] 25280번 Marathon https://www.acmicpc.net/problem/25280 25280번: Marathon Erik wants to run a marathon. Most of all, he wants to win the race. To plan his training, he has looked up how the other contestants performed in previous races and made a model to predict his chances of winning. The finishing time for each contestant is www.acmicpc.net 23/08/05 확률론적인 부분만 해결하면 쉽게 풀 수 있는 이분탐색 문제이다. 문제 접근 방식: 문제는 그렇게 길지 않으니 바..
[Python] 11973번 Angry Cows (Silver) https://www.acmicpc.net/problem/11973 11973번: Angry Cows (Silver) The first line of input contains \(N\) (\(1 \leq N \leq 50,000\)) and \(K\) (\(1 \leq K \leq 10\)). The remaining \(N\) lines all contain integers \(x_1 \ldots x_N\) (each in the range \(0 \ldots 1,000,000,000\)). www.acmicpc.net 22/11/05 전형적인 이분 탐색 문제로, 외국어 문제여서 문제를 해석하는 것이 어려운 문제이다. 문제 접근 방식: 먼저 외국어 문제이기에 문제 요약을 하자면 다음과 같다. 건초더미..
[Python] 2343번 기타 레슨 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 22/10/05 이분 탐색 문제로, 왜 이분 탐색으로 접근할 생각을 했냐고 묻는다면... 강의의 수가 최대 10만개이고, 강의의 길이는 최대 10000분이고, 블루레이 디스크의 최소 개수는 1개이기 때문에 가능한 블루레이의 크기는 최대 10만*10000 = 10억이다. 때문에 1분부터 10억분까지 일일이 선형으로 탐색하려면 시간이 너무 오래 걸릴 것 같아 이분 탐색으로 하기로 했다. 문제 접근 방식: 블..
[Python] 2022번 사다리 2022번: 사다리 (acmicpc.net) 2022번: 사다리 첫째 줄에 차례대로 x, y, c에 해당하는 양의 실수 세 개가 입력된다. 수는 소수점 여섯째 자리까지 주어질 수 있으며, 3,000,000,000보다 작거나 같다. www.acmicpc.net 22/09/02 은근히 어려웠던 문제이다. 요즘 태그를 보지 않고 문제를 푸는데, 이분 탐색을 활용하는 문제가 아니라 온전히 답안이 나오는 문제인 줄 알고 식 정리에만 시간을 온전히 쏟았다. 알고 보니 명확한 식으로 나오지 않는 문제임을 알고서 이분 탐색을 활용하여 문제를 풀었다. 식 정리가 제일 어려운 문제이다. 문제 접근 방식: 그냥 식 정리를 한 뒤에 이분 탐색으로 문제를 풀면 된다. 이 식 정리가 좀 어렵긴 하지만, 사진으로 나와있으니 참고하..

티스토리툴바