목록코딩테스트 이론 (1)

Grusie 안드로이드 개발 기술 블로그

[알고리즘] 누적합(prefix sum) 이론 및 예제 (코틀린)

알고리즘 첫 번째, 누적합의 이론을 공부하고 예제들을 풀어보려고 한다. 누적 합 : 일정 구간의 누적 합을 구하는 문제이다. 일반적으로 사용되는 배열에 값을 저장하고 지정된 인덱스부터 하나씩 더해가는 방식은 최악의 경우 O(n^2)의 시간 복잡도를 갖기 때문에 입력의 범위가 클 때 사용할 수 없다. 하지만 Prefix sum 방식을 사용하면 O(N)으로 해결 할 수 있다. 누적합은 문제에서 수열이 주어지고 어떤 구간의 값의 합을 구해야 할 때 쓰일 수 있다. 예를 들어, 크기가 5인 arr배열에서 3번 index와 5번 index 구간의 구간합을 구한다고 가정하면, 누적합은 arr[0~b]까지의 누적합 - arr[0~a-1까지의 누적합]으로 표현 할 수 있다. b - a 구간의 누적합을 구하기 위해선 b..
코딩테스트/알고리즘 2024. 3. 21. 20:49
이전 Prev 1 Next 다음