본문 바로가기

매개 변수 탐색

 (6)
[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] 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] 2805번 나무 자르기 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 22/08/28 보자마자 날먹 문제라고 생각했다. 이 문제는 그제 풀었던 1654번 랜선 자르기 문제와 거의 동일한 문제였기 때문이다. 단지 약간의 조건만 달랐다. 문제 접근 방법: 랜선 자르기 문제와 동일한데, 나무를 일정 간격으로 계속 자르는 게 아니라, 일정 높이를 두고 일정 높이 이상인 나무만 한 번 자른다는 점만 다르다. 다시 말해, 나누기를 하는게..
[Python] 1654번 랜선 자르기 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 22/08/26 클래스 2 문제 중 안 푼 문제가 있길래 푼 문제이다. 전형적인 이분탐색 문제이고, 이분탐색 문제 특성상 범위나 종료 조건을 잘못 설정하면 맞왜틀을 하기 쉽기 때문에 나도 맞왜틀을 여러 번 했다. 당연히 이분탐색이 무엇인지 알고 있다는 전제 하에서 글이 쓰여있으므로, 풀이를 참고할 생각이 있다면 이분 탐색기법을 알아야 할 것이다. 문제 접근 방법: 기존..

티스토리툴바