03-2 구간 합
구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘
구간 합의 핵심 이론
합 배열 S 정의
S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]
합 배열 S를 만드는 공식
S[i] = S[i-1] + A[i]
구간 합을 구하는 공식
S[j] - S[i-1]
반응형
'ALGORITHM' 카테고리의 다른 글
알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - 나머지 합 구하기 (0) | 2023.12.03 |
---|---|
알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - 스택과 큐 (0) | 2023.12.03 |
알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - 배열과 리스트 (0) | 2023.12.02 |
알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - 디버깅 (0) | 2023.12.02 |
알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - 시간복잡도 (0) | 2023.12.01 |