[Python] SQRT Decomposition(제곱근 분할법) 설명 및 구현 (백준14438, 2042)
이번 포스팅에서는 SQRT Decomposition(제곱근 분할법)의 개념과 Python Code를 설명합니다. Code만 참고하실 분은 포스팅 가장 아랫부분으로 내려가시면 됩니다. SQRT Decomposition(제곱근 분할법, 평방분할법) 알고리즘 SQRT Decomposition은 구간에서 최소값, 최대값, 구간합 등을 구할 때 가장 기본적으로 사용되는 알고리즘입니다. 전체 크기가 N인 구간에서 N을 전부 다 탐색하는 것이 아니라, ROOT(N) 번만 탐색하여 시간을 줄일 수 있습니다. 크기가 N인 배열이 주어졌을때, 아래와 같은 연산을 수행하는 문제를 생각해 보겠습니다. - 1) 구간 l,r ( l ≤ r )을 주고 l ~ r 사이 배열의 최소값(min( A[l], A[l+1],... , A[r..
2023. 9. 26.
[Python] 이분탐색 bisect 라이브러리 사용법 코드
bisect 라이브러리는 파이썬에서 이진탐색을 쉽게 구현하게 해 주는 라이브러리입니다. 알고리즘 시험에서 탐색 문제를 해결하기위해 이분탐색을 사용하는 경우가 많은데, 이분 탐색을 직접 구현하지 않고 라이브러리 만으로 수행할 수 있습니다. bisect 라이브러리 ✔️ bisect_left( x, i ) : 정렬된 배열 x에서 정렬 순서를 유지한 상태로 값 i를 삽입할 가장 왼쪽 인덱스 반환 ✔️ bisect_right( x, i ) : 정렬된 배열 x에서 정렬 순서를 유지한 상태로 값 i를 삽입할 가장 오른쪽 인덱스 반환 예제 1 x = [1, 2, 3, 3, 3, 4, 5, 6]인 정렬된 배열이 있습니다. 이때 배열 x에 정렬된 상태 그대로 3이라는 숫자를 삽입하는 문제를 생각해 보겠습니다. 이분 탐색 ..
2023. 6. 6.