BOJ/🏅3

★Divide & Conquer Expert(Easy) I - 1 Solved★ ★ 11440 피보나치 수의 제곱의 합 ★n=int(input())BIG=1_000_000_007def get_power(a,b,c): if b 🙉 F1부터 Fn까지의 모든 피보나치 수의 제곱의 합은 아래와 같이 Fn*Fn+1 결과로 표현할 수 있다.🙉 이 때 Fn에서의 n이 매우 큰 수이므로 Fn을 구하기 위해 분할정복을 이용한 행렬 거듭제곱으로 O(logn)만에 구해야 한다. Fn과 Fn+1을 각각 O(logn)만에 구한 뒤, modulo multiplication property에 의해 ((Fn%BIG) * (Fn+1%BIG))%BIG를 최종 답으로 출력! BOJ/🏅 2024. 6. 30.

★DP Expert(Easy) I - 4 Solved★ ★ 14003 가장 긴 증가하는 부분 수열 5 ★ import sysinput=sys.stdin.readlineN=int(input())A=list(map(int,input().split()))#binary searchdef binary_search(l, i, x): start,end=0,len(l)-1 while start ⛹️ LIS의 길이와 내용을 O(nlogn) 시간 복잡도 이내로 구하는 교과서 문제. LIS의 길이는 ans_num list에서 binary search로 update하며 내용 추가. LIS의 내용은 ans_i list에서 앞선 binary search로 삽입되는 원소의 index를 update하며 거꾸로 최댓값부터 1이 될때까지 해당 되는 inde.. BOJ/🏅 2024. 1. 7.

★정렬 최상급1 - 1문제()★ 🏅 플래티넘 이상의 난이도는 각 문제의 접근방향 뿐만 아니라, 사고과정 흐름까지 최대한 리마인드하는 방식으로 기억하자! 🏅 정렬관련 포스팅 하단 참조 🏅 정렬에는 정말 많은 알고리즘이 있다. 플래이상의 난이도급 문제에서 정렬을 어떤 방식으로 접근하는 지 알아보자 ★ 2220 힙 정렬 ★ import math n = int(input()) if n==1:print(1) elif n==2:print(2,1) elif n==3:print(3,2,1) else: arr = [3,2,1] for i in range(n-3): end=int(math.log(i+3,2)) idx=len(arr)-1 for _ in range(end): arr[idx],arr[(idx-1)//2]=arr[(idx-1)//2],arr[.. BOJ/🏅 2023. 2. 7.

이전 1 다음

티스토리툴바