0. 한 줄 요약 같은 배열에서 구간 합을 여러 번 물을 때, 앞에서부터 합을 미리 쌓아 두고 **뺄셈 한 번(O(1))**으로 답한다. 단, 배열이 중간에 바뀌지 않아야 한다. 1. 누적합(Prefix sum)누적합이란?누적합(prefix sum)은 배열의 맨 앞부터 각 위치까지의 합을 미리 계산해서 저장해 둔 배열이다.원본 배열 a에 대해, 누적합 배열 psum의 i번째 값은 a[1] + a[2] + ... + a[i]다. 원본 a와 누적합 psum을 나란히 놓으면 이렇다.위치i12345원본 a[i]25134누적합 psum[i]2781115psum[3] = 8은 “1번부터 3번까지 더한 값 (2+5+1)”이다. 앞의 값에 현재 원소를 더해서 만든다.psum[i] = psum[i - 1] + a[i]..
0. 한 줄 요약 정렬은 STL이 해준다. 코테에서 중요한 건 "어떤 기준으로 줄 세울지"를 비교 함수로 정의하는 것과 정렬한 뒤 무엇이 쉬워지는지 아는 것이다. 1. 정렬(Sort) 정렬이란?정렬(sorting)은 원소들을 정해진 기준에 따라 순서대로 다시 배치하는 것이다. 기준은 오름차순, 내림차순처럼 기본적인 것도 있고, "점수는 내림차순, 같으면 이름 오름차순"처럼 직접 정의할 수도 있다.정렬 전: [3, 1, 4, 1, 5]오름차순: [1, 1, 3, 4, 5]내림차순: [5, 4, 3, 1, 1] C++에서는 sort(begin, end)가 이 일을 하고, 비교 기반 정렬이라 O(N log N)이다. 원본 배열을 그 자리에서 바꾼다. 기준을 직접 정의할 때는 비교 함수를 넘기는데, cmp(..
0. 한 줄 요약스택은 가장 최근 것부터, 큐는 가장 오래된 것부터 꺼낸다. 둘 다 새로운 구조가 아니라, 배열에 "넣고 빼는 규칙"을 붙인 것이다. 1. 스택 (Stack, LIFO) 스택이란?스택(stack)은 데이터를 한쪽 끝에서만 넣고 뺄 수 있는 자료구조다. 가장 나중에 넣은 것이 가장 먼저 나오는 후입선출(LIFO, Last In First Out) 규칙을 따른다. 접시를 쌓고 맨 위에서부터 집는 것과 같다.push(1) → push(2) → push(3) 스택: [1, 2, 3] (3이 맨 위)pop() 3이 나온다 스택은 독립적인 구조라기보다 배열이나 연결리스트에 "한쪽 끝에서만 접근한다"는 규칙을 붙인 것이다. 핵심 연산은 push, ..
1일차: 시간복잡도 + 해시 1. 시간복잡도 계산법반복문이 몇 번 도는지 센다. 중첩이면 곱하고, 나란히면 더한다. 가장 큰 항만 남긴다.매번 절반(또는 2배)으로 변하면 log N.상수배는 Big-O에서 버린다. (2N과 3N은 둘 다 O(N))기준: 1초 ≈ 1억 연산. N=10⁵에서 N²(10¹⁰)은 불가, N log N은 가능.for (int i = 1; i 2. C++ 함정: size()와 unsignedvector v = {1,2,3};cout size()는 size_t(부호 없는 정수)를 반환한다.타입이 다르면 컴파일러가 한쪽으로 맞춘 뒤 계산한다. unsigned가 한쪽이라도 섞이면 signed가 unsigned로 끌려간다.unsigned 언더플로는 2⁶⁴을 더해 보정되는 정의된 동작이다..
1. 이터레이터이터레이터란 컨테이너에 저장되어 있는 요소의 주소를 가리키는 객체로, 포인터를 일반화한 것이다.vector, map 등 각각 다르게 구현된 컨테이너들을 일반화된 이터레이터를 통해 쉽게 순회할 수 있게 만든 것이다. 컨테이너의 데이터를 순회하려면 주소를 알아야 한다. 이 주소를 가리키는 개체가 이터레이터이다. 1.1 주소값 가져오기c++의 cout은 int, string, 혹은 포인터 타입에 대해서는 vector::iterator타입에 대해서는 #include using namespace std;vector v;int main(){ for(int i = 1; i 이렇게 iterator에 직접 접근해서 출력하면 오류가 난다.이럴 땐 역참조 연산자 *를 이용하여 값으로 돌아가 주고, 다시..
