[개념] 구간 합 (Prefix Sum)

2023. 6. 10. 02:21· 알고리즘/개념
목차
  1. # 구간 합
  2. #  합 배열
  3. # 관련 문제

# 구간 합

  • 구간 합 : i ~ j 인덱스 값들의 합 => 특정 구간 인덱스의 합
  • 부분 합 : 0 ~ k 인덱스 값들의 합 => 처음부터 특정 인덱스까지의 합
  • 시간 복잡도
    • 반복문을 통해 i ~ j 인덱스 값들의 합을 구하는 경우) O(N) (i=0, j=N)
    • 시간 복잡도를 줄이기 위해서는 합 배열을 이용해야 함 => O(1)으로 감소

 

#  합 배열

합 배열 S, 배열 A
S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]
  • 합 배열 : 기존의 배열을 전처리한 배열합 배열 만드는 공식
S[i] = S[i-1] + A[i]
  • 합 배열을 이용해 구간 합 구하는 공식
S[j] - S[i-1]

# 관련 문제

 

[JAVA] 백준 q11659 - 구간 합 구하기 4

11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을

monicajo074.tistory.com

 


# 참고 글

  • Do it 알고리즘 코딩테스트 자바편

'알고리즘 > 개념' 카테고리의 다른 글

[개념] 위상 정렬(Topological Sort)  (0) 2024.02.20
[개념] 최소 공통 조상 (LCA, Lowest Common Ancestor)  (0) 2023.08.02
[개념] 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)  (2) 2023.08.01
  1. # 구간 합
  2. #  합 배열
  3. # 관련 문제
'알고리즘/개념' 카테고리의 다른 글
  • [개념] 위상 정렬(Topological Sort)
  • [개념] 최소 공통 조상 (LCA, Lowest Common Ancestor)
  • [개념] 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)
하얀 돌덩이
하얀 돌덩이
하얀 돌덩이
돌덩이
하얀 돌덩이
전체
오늘
어제
  • 분류 전체보기 (59)
    • 개발 일지 (2)
    • 스프링 (1)
    • JAVA (2)
    • 딥러닝 (10)
    • 알고리즘 (43)
      • 개념 (4)
      • 프로그래머스 (5)
      • 백준 (34)
    • 후기 (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
하얀 돌덩이
[개념] 구간 합 (Prefix Sum)
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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