시간복잡도2 Prefix sum(누적합) 누적합이란 미리 요소들의 합을 저장해 두는 누적된 수의 합 앞에서 부터 더하는 prefix sum 뒤에서 부터 더하는 suffix sum 구간에 대한 많은 쿼리가 나올때 생각해야 할 것이 트리와 누적합 구간 내의 요소가 변하지 않는 정적요소인 경우 누적합을 사용한다. A 1 2 3 4 psum[1] O psum[2] O O psum[3] O O O psum[4] O O O O 1 3 6 10 예제) N개의 카드를 주고 M개의 경우의 관하여 A번째부터 B번째까지의 합을 구하라 입력 수의 개수 N, 합을 구해야하는 횟수 M, 그 이후에 N개의 숫자가 주어진다. 수는 100이하의 자연수 그 이후 M개의 줄에 합을 구해야하는 구간 A,B가 주어진다. 출력 M개의 줄에 A부터 B까지의 합을 구하라 범위 1 b >.. 2022. 6. 20. Time Complexity(시간 복잡도) 시간복잡도 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계 알고리즘의 로직이 얼마나 오랜 시간 걸리는지 나타내는데 사용 보통 빅-오 표기법으로 표시 ex) 입력크기 n에 대하여 모든 입력에 대한 알고리즘에 필요한 시간이 "8n^2 + 2n" 이라면 다음과 같은 코드로 표현 가능 for(int i = 0; i O(2^n) > O(n!) 자료구조에서의 시간복잡도 STL에서의 시간 복잡도 sort() : nlogn find() : n fill() : n unique() : n lower_bound(), upper_bound() : nlogn 2022. 6. 20. 이전 1 다음