목록구간합구하기 (1)

병아리의 코딩 일기

Java 알고리즘 :: 구간 합 구하기 (핵심 이론)

본 글은 Do IT 알고리즘 코딩 테스트 자바 편을 정리한 글입니다! 구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘입니다. 코딩 테스트에서 사용 빈도가 높으니 꼭 알아두시기 바랍니다. 구간 합의 핵심 이론 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 합니다. 배열 A가 있을 때 합 배열 S는 다음과 같이 정의합니다. 합 배열 S 정의 S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합 합 배열은 기존의 배열을 전처리한 배열이라 생각하면 됩니다. 이렇게 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소합니다. A[i]부터 A[..
알고리즘 Algorithms 2023. 7. 28. 00:28
이전 Prev 1 Next 다음