이분탐색 검색 결과

해당 글 3건

[BOJ 1654] 랜선 자르기 (C++)

랜선 자르기(Silver 3) 문제 전체 문제 보기 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 접근법 문제에서 주어진 랜선을 몇 센티미터로 잘라야 필요한 N개의 랜선(모든 랜선은 같은 길이를 가져야 함.)을 만들면서 낭비 없이 가장 긴 랜선을 만들 수 있는지 묻고 있습니다. 그런데 문제는 랜선의 길이가 너무 크다는 점입니다. 랜선의 길이는 \(2^{31}-1 = 2,147,483,647\) 이기 때문에 모든 경우를 완전 탐색을 하기에는 시간이 너무나 오래 걸립니다. 그래서 이..
Algorithms/Binary Search 2021. 9. 14. 22:35

[프로그래머스] (이분탐색) 징검다리(C++)

징검다리 (Level 4) 문제 전체 문제 보기 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 접근법 이 문제에서 요구하는 것은 전체 징검다리 바위들 중에서 n개의 바위를 제거했을 때 "바위들 간격의 최솟값이 가장 큰 값"이다. 어떤 바위를 제거하냐에 따라서 간격의 최솟값이 변할 수 있는데 이중 최솟값이 가장 큰 값을 구하는 것이다. 이 문제는 이분 탐색으로 접근하면 쉽게 해결할 수 있다. 이분 탐색을 활용할 경우, 바위를 제거하는 효율적인 방법이 무엇인지는 신경 쓰지 않아도 된다. 이분 탐색을..
Algorithms/Binary Search 2021. 7. 21. 12:04

[프로그래머스] (이분탐색) 입국심사(C++)

입국심사 (Level 3) 문제 전체 문제 보기 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 접근법 이 문제에서 요구하는 바는 가장 효율적인 입국심사 방식을 적용했을 때 모든 사람이 심사를 받는데 걸리는 시간의 최솟값이다. 이 문제를 풀기 위해서 두 가지 방법을 접근해볼 수 있을 것이다. 첫 번째로는 가장 효율적인 입국심사 방식의 메커니즘을 구현하는 방법이다. 방법은 의외로 간단하다. 우선순위 큐를 활용하여서, 모든 심사관들을 우선순위 큐에 "심사가 끝나는 시간을 기준"으로 삽입을 한다. 그리고 다음 사람이..
Algorithms/Binary Search 2021. 7. 20. 12:12