728x90 codility2 [Python] Codility ArrayInversionCount An array A consisting of N integers is given. An inversion is a pair of indexes (P, Q) such that P Write an efficient algorithm for the following assumptions:N is an integer within the range [0..100,000];each element of array A is an integer within the range [−2,147,483,648..2,147,483,647]. 당연히 하나씩 비교했을 시 O($N^{2}$)이 되므로 이를 개선할 필요성이 있다.이 때 보통 병합정렬(merge sort)을 사용한다. 병합정렬은 분할(divide), 정복(conquer.. 2025. 4. 15. [Python] Codility FloodDepth 이 문제는 "Trapping Rain Water" 문제를 변형하여 최대 물 깊이를 구하는 문제 먼저 빗물이 고이기 위해서는 왼쪽 오른쪽에 현재 위치보다 높은 땅이 있어야한다.따라서 각 인덱스에서 왼쪽 기둥 오른쪽 기둥을 구해야한다.left_max = [0 for _ in range(n)]right_max = [0 for _ in range(n)]left_max[0] = A[0]for i in range(1,n): left_max[i] = max(left_max[i-1], A[i])right_max[n-1] = A[n-1]for i in range(n-2,-1,-1): right_max[i] = max(right_max[i+1], A[i]) 그 후에 빗물의 깊이를 구해야한다. 이를 water.. 2025. 4. 14. 이전 1 다음 728x90
