배열

정적배열(Array)

int a[10]; // c스타일
array<int, 10> a; // std스타일

int a[10];
int a2[3] = {1, 2, 3};
int a3[] = {1, 2, 3, 4}; // int a3[4] 와 같다.

• 연속된 메모리 공간에 위치한다. → 숫자 인덱스를 기반으로 랜덤접근이 가능하다.
  • ↔ 연결리스트
• 같은 타입만 저장이 가능하다.
• 중복을 허용한다.
• vector 와 달리 메서드가 없다.

동적배열(Vector)

#include <bits/stdc++.h>
using namespace std;
// 선언
vector<int> v;
int main() {
    // 맨 끝에 요소 추가
    for(int i = 1; i <= 10; i++) v.push_back(i);
    for(int a : v) cout << a << " ";
    cout << "\n"

    // 주소값 출력(&) -> 연속된 메모리에 위치한다.
    for(int i = 0; i < v.size(); i++) {
        cout << &v[i] << '\n';
    }

    // 맨 끝의 요소 삭제 O(1)
    v.pop_back();

    // 중간 요소 삭제 O(n)
    e.erase(v.begin(), v.begin() + 3); // (from, to] 

    // 100 탐색 O(n)
    auto a = find(v.begin(), v.end(), 100); // STL
    if(a == v.end()) cout << "not found" << "\n";

    // 모든 요소 초기화
    fill(v.begin(), v.end(), 10);

    // 모든 요소 삭제
    v.clear();
}

• 컴파일 시점에서 사용해야 할 요소들의 개수를 모를때 사용
• 연속된 메모리 공간에 같은 타입의 요소들을 저장(중복 허용) → 숫자 인덱스로 랜덤 접근 가능
• 메서드 지원
  • Python/Java append() , JS push() , C++ push_back()

• 참조 O(1)
  • 숫자 인덱스로 랜덤 접근 가능
• 탐색 O(n)
  • 특정 요소를 찾을 때 배열의 첫번째 요소부터 순차적으로 탐색한다.
• 맨 끝, 앞에 삽입/삭제 O(1)
• 중간에 삽입/삭제 O(n)
• 벡터도 정적 할당이 가능하다. vector<int> v(5, 100);