binary search

[백준(BOJ)] #1561- 놀이 공원 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net 문제 풀이 해당 문제는 이분 탐색으로 해결할 수 있습니다. 2022.08.11 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 이분 탐색(Binary Search) [파이썬으로 배우는 알고리즘] 이분 탐색(Binary Search) 이분 탐색(Binary Search)이란? 이분 탐색(Binary Search)이란 탐색 범위를 절반으로 나눠가..

[백준(BOJ)] #1300- K번째 수 (파이썬, PyPy3)

문제 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 문제 풀이 배열의 크기 N이 10^5보다 작거나 같은 자연수이기 때문에 일차원 배열로 변환하고 정렬해서 구하기는 불가능합니다. 이분 탐색을 사용하여 이 문제를 해결할 수 있습니다. 2022.08.11 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 이분 탐색(Binary Search) [파이썬으로 배우는 알고리즘] 이분 탐색(Binary Search..

[파이썬으로 배우는 알고리즘] 이분 탐색(Binary Search)

이분 탐색(Binary Search)이란? 이분 탐색(Binary Search)이란 탐색 범위를 절반으로 나눠가며 데이터를 탐색하는 방법입니다. 우리가 흔히 알고 있는 순차 탐색(Linear Search)은 데이터를 앞에서부터 하나씩 탐색하여 시간 복잡도가 O(N)(N은 데이터의 개수)으로 그렇게 효율적인 탐색 방법은 아닙니다. 하지만 이분 탐색은 데이터의 범위를 절반씩 계속 나눠 탐색하기 때문에 시간 복잡도가 O(logN)으로 순차 탐색보다는 훨씬 효율적인 탐색 알고리즘이라고 볼 수 있습니다. 하지만 데이터가 속해 있는 범위를 알아야 하기 때문에 정렬되어 있는 데이터에서만 이분 탐색을 사용할 수 있습니다. 그러면 이분 탐색이 어떻게 사용되는지 순차 탐색과 어떻게 다른지 과정을 보며 확인해보겠습니다. 이..