728x90 알고리즘/[python] 백준 BOJ330 [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] 백준 2641 다각형그리기 https://www.acmicpc.net/problem/2641 문제 해결같다고 판정되는 다각형은 오직 시작점의 차이와 역방향 이동 두개의 차이만 허락된다. CODEimport sysinput = sys.stdin.readlinefrom collections import dequeconvert = lambda x: (x+2)%4 if x!=2 else 4n = int(input())sample = deque(map(int, input().split()))rev_sample = deque(map(convert, sample))rev_sample.reverse()cnt = 0result = list()for _ in range(int(input())): x = deque(map(int,input().sp.. 2025. 1. 27. [python] 백준 2352 반도체 설계 문제 해결가장 길게 오름차순 수열을 만들수 있는 LIS (Longest Increasing Subsequence) 문제원소 하나씩 살펴보면서 가장 최근 이은 값도가 크면 하나 더해주고 작은 값이 나오면 이분탐색 통해 이전 값들에서 하나에 예약 연결한다 생각하고 value값을 바꿔놔도 문제 없다CODEimport sysinput = sys.stdin.readlinefrom bisect import bisect_leftif __name__ == "__main__": n = int(input()) A = list(map(int, input().split())) link = [] for d in A: if not link or link[-1] 2024. 8. 15. 이전 1 2 3 4 ··· 83 다음 728x90
