부트캠프(44일차)

오늘은 부트캠프 44일차이다. 오늘은 오전에 알고리즘 1문제를 풀고, 내일 본격적인 프로젝트를 진행하기 전 메모장 프로젝트를 다시한번 만들어 보았다. 결과적으로는 반만 만들어졌다. 아직까지도 많이 부족하다는 생각이 들었고, 이것을 극복을 하려면 자주 만들어보면서 익혀야 겠다는 생각이 들었다. 아마 내일 프로젝트를 시작으로 내가 알았던 부분과 몰랐던 부분이 명확하게 나눠질 거 같다. 만약 모르는 부분이 있다면 벨로그에 기록하면 될 것이고, 아는 부분이 있다면 복습을 하면 될 것이다. 내일 프로젝트의 목표는 전체적인 흐름을 생각하면서 진행하면 될 것 같다.

오늘 배운 것

1. 구간 합(Interval Sum)

-구간 합 문제:연속적으로 나열된 N개의 수가 있을 대 특정 구간의 모든 수를 합한 값을 계산하는 문제

2. 구간 합 빠르게 계산하기 : 문제 설명

-N개의 정수로 구성된 수열이 있다.
-M개의 쿼리(Query)정보가 주어진다.
-각 쿼리는 Left와 Right으로 구성된다.
-각 쿼리에 대하여 [Left, Right] 구간에 포함된 데이터들의 합을 출력해야 한다.
-수행 시간 제한은 O(N + M)이다.

3. 구간 합 빠르게 계산하기 : 문제 해결 아이디어

-접두사 합(Prefix Sum): 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓은 것
-접두사 합을 활용한 알고리즘은 다음과 같다
-𝑁개의 수 위치 각각에 대하여 접두사 합을 계산하여 𝑃에 저장한다
-매 𝑀개의 쿼리 정보를 확인할 때 구간 합은 𝑃[Right] - 𝑃[Left - 1]이다

4. 구간 합 빠르게 계산하기 : 코드 예시 (Python)

//데이터의 개수 N과 전체 데이터 선언
n = 5
data = [10, 20, 30, 40, 50]

//접두사 합(Prefix Sum) 배열 계산
sum_value = 0
prefix_sum = [0]
for i in data:
    sum_value += i
    prefix_sum.append(sum_value)

//구간 합 계산 (세 번째 수부터 네 번째 수까지)
left = 3
right = 4
print(prefix_sum[right] - prefix_sum[left - 1])

실행 결과
70