[Python/파이썬] 백준 11659 - 구간 합 구하기 4

문제 설명 입출력 예제 풀이 코드 이 문제는 현대오토에버 코딩문제에 나온 문제라고 한다. 사실상 실버난이도인 만큼 접근만 한다면 쉽게 풀 수 있는 문제다. 제한 사항을 보면 N, M 입력값의 제한 범위가 100,000이다. 이중 반복문으로 풀면 쉽게 풀수는 있겠지만 2중 반복문은 O(n^2) 시간 복잡도를 갖기 때문에 시간초과가 발생한다. 따라서 O(N)이나 O(logN)의 시간 복잡도로 풀어야 하는데 문제에서도 이미 정답을 말해줬다."구간합" 문제를 푸는 방법은 다음과 같다. 주어진 값들의 누적합을 갖는 리스트를 만든다. PrefixSum 여기서 PrefixSum에 0을 넣어 놓은 이유는 주어지는 구간 i가 1부터 시작하기 때문에 인덱싱에러를 방지하기 위해서이다. 각 수들의 합을 갖는 변수 total을..

• format_list_bulleted ◼ 코딩테스트/구간합 (Prefix)
• · 2023. 6. 22.
• textsms

[알고리즘] 누적합, 구간합 구하기

누적합(Prefix Sum)과 구간합 누적합 누적합이란 나열 된 수들의 누적된 합을 뜻합니다. 즉, 이 배열의 누적합을 구하면 1 + 3 + 4 + 2 + 5 = 15가 됩니다. 누적합의 배열의 크기가 원본 배열보다 1더 큰데 이는 밑에서 설명하겠습니다. 구간합 말 그대로 나열 된 수 중에서 합을 구하고 싶은 구간의 합입니다. 만약 1번째 인덱스부터 ~ 3번째 인덱스까지의 구간합을 구한다면, 3 + 4 + 2 = 11이 됩니다. 구간합을 빠르게 구할 수 있는 공식이 있는데, 이 공식이 만들어지는 과정을 봅시다. 누적합 배열 prefixSum의 크기가 arr보다 1 더 큰 이유는 0번 인덱스 부터 n번 인덱스의 구간합을 구할 수 있게 하기 위함입니다. 이제 1번째 인덱스부터 ~ 3번째 인덱스까지의 구간합을..

• format_list_bulleted ◼ CS 기초 지식/[알고리즘]
• · 2023. 1. 12.
• textsms