구간합(Prefix Sum)

2024. 7. 8.·CS & 알고리즘/알고리즘
목차
  1. 구간합
  2. 합배열 S
  3. 합배열 만드는 법
  4. 합배열에서 특정 구간 내의 합 구하는 법
반응형

구간합

__💡 구간합이란?__
합배열을 이용해 시간복잡도를 줄이는 목적의 알고리즘__

합배열 S

S[i] = A[0] + a[1] + ... + A[i-1] + A[i]

기존의 배열을 전처리한 배열

기존 일정 범위의 합을 구하는 시간복잡도가 $O(N)$ 에서 $O(1)$ 로 감소

합배열 만드는 법

S[i] = S[i-1] + A[i];

합배열에서 특정 구간 내의 합 구하는 법

[부분합] j~i 사이 구간 구할때

result = S[i] - S[j-1];

 

j 가 아닌 j-1

2~4 까지의 구간합을 구하고 싶으면 

 

 

💡
연관문제

[G3] 10986 나머지 합
[S1] 11660 구간합 5
[S3] 11659 구간합 4

 

반응형
저작자표시 (새창열림)

'CS & 알고리즘 > 알고리즘' 카테고리의 다른 글

[알고리즘] 소수 & 에라토스테네스의 체  (1) 2024.07.05
  1. 구간합
  2. 합배열 S
  3. 합배열 만드는 법
  4. 합배열에서 특정 구간 내의 합 구하는 법
'CS & 알고리즘/알고리즘' 카테고리의 다른 글
  • [알고리즘] 소수 & 에라토스테네스의 체
keartt
keartt
shalpha_2@naver.com
주니어 탈출일기 🐽
shalpha_2@naver.com
  • keartt
전체
오늘
어제
  • 전체보기
    • CS & 알고리즘
      • CS (컴과학)
      • 알고리즘
      • 백준
    • Spring
      • SpringBoot (JPA)
      • Spring (Legacy)
    • Server
      • Linux
      • Docker
    • Java
      • Design Pattern
    • PostgreSQL
    • GIS (공간정보)
    • 오류정리
    • Git
    • JavaScript
      • Node.js
      • React
    • Tool
      • IntelliJ
      • MacOS
      • VSCode
      • Eclipse
      • Other
    • 강의정리들
      • [2023] FullStack
      • [2022] Spring Boot
      • [2021] Spring Boot

인기 글

태그

이분탐색
코딩애플
브루트포스
구간합
반응형
hELLO· Designed By정상우.v4.6.1
keartt
구간합(Prefix Sum)

개인정보

kearttshalpha_2@naver.com계정관리

운영중인 블로그

주니어 탈출일기쓰기블로그 관리

이동링크목록

  • 티스토리 홈
  • 피드
  • 로그아웃
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.