메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조
- 인덱스를 사용하여 값에 바로 접근할 수 있다
- 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다
- 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다
- 구조가 간단하므로 코딩 테스트에서 많이 사용한다
값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조
- 인덱스가 없으므로 접근하려면 Head 포인터부터 순서대로 접근해야 한다. 다시 말해 값에 접근하는 속도가 느리다
- 포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도가 빠르다
- 선언할 때 크기를 별도로 지정하지 않아도 된다. 다시 말해 리스트의 크기는 정해져 있지 않으며, 크기가 변하기 쉬운 데이터를 다룰 때 적절하다.
- 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다.
C++ STL에 있는 자료구조 컨테이너 중 하나로 사용자가 손쉽게 사용하기 위해 정의된 클래스이다. 기존의 배열과 같은 특징을 가지면서 배열의 단점을 보완한
동적 배열의 형태
- 동적으로 원소를 추가할 수 있다. 즉, 크기가 자동으로 늘어난다
- 맨 마지막 위치에 데이터를 삽입하거나 삭제할 때는 문제가 없지만 중간 데이터의 삽입 삭제는 배열과 같은 메커니즘으로 동작한다
- 배열과 마찬가지로 인덱스를 이용하여 각 데이터에 직접 접근할 수 있다.
// 선언
vector<int> A; // vector<자료형> 변수 이름; 형태로 선언
// 삽입 연산
A.push_back(1); // 마지막에 1 추가
A.insert(A.begin(), 7); // 맨 앞에 7 삽입
A.insert(A.begin()+2, 10); // index 2 위치에 10 삽입
// 값 변경
A[4] = -5; // index 4 위치의 값을 -5로 변경
// 삭제 연산
A.pop_back(); // 마지막 값 삭제
A.erase(A.begin()+3); // index 3에 해당하는 원소 삭제
A.clear(); // 모든 값 삭제
// 정보 가져오기
A.size(); // 데이터 개수
A.front(); // 처음 값
A.back(); // 마지막 값
A[3]; // index 3에 해당하는 값
A.at(5); // index 5에 해당하는 값
A.begin(); // 첫 번째 데이터의 iterator
A.end(); // 마지막 데이터의 iterator
구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘
- 합 배열 S의 정의
$S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]$
- 합 배열은 기존의 배열을 전처리한 배열이라 생각하면 된다
- 합 배열을 미리 구해두면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다
- 합 배열 S를 만드는 공식
$S[i] = S[i-1] + A[i]$
- 구간 합을 구하는 공식
$S[j] - S[i-1]$ // i번째는 포함해야하기 때문
- 투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화합니다.
- 슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하여 문제를 해결합니다. 투 포인터 알고리즘과 비슷하고 원리도 간단합니다
- 스택은 삽입과 삭제 연산이 후입선출(LIFO: Last In Firt Out)로 이뤄지는 자료구조이다.
- 삽입과 삭제는 한쪽에서만 진행된다
- top: top 위치에 현재 있는 데이터를 단순 확인하는 연산
- push: top 위치에 새로운 데이터를 삽입하는 연산
- pop: top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
- 큐는 삽입과 삭제 연산이 선입선출(FIFO: First In First Out)로 이뤄지는 자료구조이다.
- 삽입과 삭제가 back, front에서 각각 진행된다
- push: back 부분에 새로운 데이터를 삽입하는 연산
- pop: front 부분에 있는 데이터를 삭제하고 확인하는 연산