728x90 분류 전체보기432 [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] &, bit_length() &비교 연산자 (명제가 둘다 참인지)Bitwise Example# 비교 연산자print(1&0) -> True & False -> False# Bitwiseprint(24&-24) -> 0b11000 & 0b01000 -> 8 여기서 보수를 알아야하는데 이진법에는 음수를 표현하는 방법이 없다.따라서 N과 -N의 차이는 N의 이진법 수에서 0과 1의 숫자를 바꾼 뒤 1을 추가하는 방법으로 반대 되는 수를 계산한다. Bit_lengthpython에는 bit_length라는 함수가 있다.이는 오른쪽에서부터 계산할 때, 즉 2의 몇제곱에서 처음으로 이진수가 1이 나오는지 확인하는 함수이다.즉 0b1000의 bit_length값은 4이다.print((24&-24).bit_length()) # 4 2025. 4. 14. [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. 재귀와 반복의 차이 코드 비교 다음 두개 코드의 차이점을 확인해보자 재귀import syssys.setrecursionlimit(10000)def solution(A): # Implement your solution here visited = [0 for _ in range(len(A))] def recursion(idx, num): if idx == -1 or visited[idx]==1: return num visited[idx] = 1 return recursion(A[idx],num+1) return recursion(0,0) 반복def solution(A): visited = [0 for _ in range(len(A))] i.. 2025. 4. 14. 이전 1 2 3 4 ··· 108 다음 728x90
