C++2 누적합(Prefix Sum) 누적합(Prefix Sum)누적합은 요소들의 누적된 합의 의미를 얘기합니다.배열의 첫 번째 0번째 배열의 요소부터 누적시키면서 더한 배열을 활용합니다. 일부 구간에 대한 합을 구하는 문제에서 사용이 됩니다. 단, 배열의 값들이 변하지 않는다는 전제가 필요합니다. $ N = 5 $ 인 N 크기의 정수 배열 arr이 있을 때 여러 개의 구간 [a, b]에 대해 합을 구하려고 합니다. $ 1\leq a\leq b\leq N $$$ arr[a]+arr[a+1]+\cdots+arr[b] $$Index i01234arr[i]16425 간단하게 생각할 수 있는 방법은 반복문을 돌려서 각 요소를 더하는 것입니다. 이 방법은 각 쿼리에 대해 최대 $ O(N) $ 시간 복잡도를 가지고, 만약 M개의 쿼리가 주어지면 시간 .. 2025. 1. 19. 큐(Queue) ✔ 큐(Queue) 큐도 스택과 마찬가지로 알고리즘보단 자료 구조에 해당하고 컴퓨터에서 많이 사용되는 자료 구조이다. 큐는 먼저 집어넣은 데이터가 먼저 나오는 선입선출(FIFO: First In First Out) 구조로 저장하는 형식을 말한다. 즉, 가장 처음에 넣은 값이 먼저 나오는 것을 FIFO 구조라고 한다. 나중에 넣은 값이 먼저 나오는 스택과는 반대되는 개념이다. 쉬운 예시로 파이프 혹은 드라이브 스루를 생각하면 된다. 드라이브 스루는 가장 먼저 들어가는 사람이 먼저 주문을 하게 되고 그 뒤로 차례로 줄을 서게 된다. 먼저 들어간 사람이 주문을 끝내고 가지 않는 이상 그 뒤로는 계속 기다려야 하는 구조이다. 이 구조가 큐 자료 구조에 해당한다. ✔ 큐의 연산 큐는 양쪽이 뚫려 있는 구조로 한쪽.. 2023. 5. 2. 이전 1 다음
