728x90 알고리즘322 [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. 재귀와 반복의 차이 코드 비교 다음 두개 코드의 차이점을 확인해보자 재귀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. [python] XOR 문제 해결 XOR이란 무엇인가?음이 아닌 정수는 항상 이진법으로 유일하게 표현할 수 있다. 이때, 각 자리 숫자는 0 또는 1이며, 2의 k승 숫자를 k번째 비트라고 한다. XOR은 기호로 '^'방식으로 나타내며 임의의 두 수 x, y가 이진수로 나타냈을 때 k번 비트가 같다면 0, 다르면 1을 부여해서 결과를 얻는다. 예시로xor = 0nums = [3, 5, 2]for num in nums: xor ^= num다음과 같은 코드를 짜게 된다면 아래와 같이 동작한다.xor = 0 ^ 3 = 3 # 00(2) ^ 11(2) = 11(2) 모든 자리 숫자가 다르므로 모든 자리 숫자 1xor = 3 ^ 5 = 6 # 011(2) ^ 101(2) = 110(2) 1번,2번 비트 숫자가 다른 반면 3번 비트 숫자가 같.. 2025. 4. 12. 이전 1 2 3 4 ··· 81 다음 728x90
