03. 배열

정의와 성질

---

• 정의 메모리 상에 원소를 연속하게 배치한 자료구조
  
• 성질

  동작	시간복잡도
  k번째(임의 위치) 원소 확인 및 변경	O(1)
  원소를 마지막에 추가	O(1)
  마지막 원소 제거	O(1)
  임의 위치에 원소 추가	O(N)
  임의 위치의 원소 제거	O(N)

  • 추가적으로 소모되는 메모리의 양(=오버헤드)가 거의 없음
  • Cache Hit Rate가 높음
  • 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림

기능과 구현

---

• 배열 선언

  int test[5];

  → 배열 요소가 5개인 배열 선언
  
• 배열 값 접근

  test[1] 

  → [] 안에 첨자(인덱스;index)를 넣어 특정 요소를 참조할 수 있다. → 배열의 인덱스는 0에서 시작해서 마지막 첨자는 요소 수 - 1 이 된다.
  
• 값 대입 및 출력

  배열명[첨자] = 식;

• 전체를 특정 값으로 초기화할 때

  int a[21];
  int b[21][21];
  
  // 1. memset
  memset(a, 0, sizeof a);
  memset(b, 0, sizeof b);
  
  // 2. for
  for(int i = 0; i < 21; i++)
  	a[i] = 0;
  for(int i = 0; i < 21; i++)
  	for(int j = 0; j < 21; j++)
  		a[i][j] = 0;
  
  // 3. fill
  fill(a, a+21, 0);
  for(int i = 0; i < 21; i++)
  	fill(b[i], b[i] + 21, 0)

• 동적 배열 배열의 크기를 나타내는 값은 const로 선언된 상수 변수 혹은 리터럴 상수만 들어갈 수 있다.

  int n;
  cin >> n;
  int* arr = new int[n]

  배열의 크기를 미리 알지 못할때는 배열의 크기를 너무 크게 잡기에도 메모리 낭비이고 너무 작게 잡아도 나중에 indexOutOfRange 예외가 발생해 쓰레기 값에 접근하게 된다. (→ vector 로 이 한계를 극복)
  

STL vector

---

• 배열과 거의 동일한 기능을 수행하는 자료구조로 배열과 마찬가지로 원소가 메모리에 연속하게 저장되어 있다.
• 동적으로 크기를 확장/축소 할 수 있다는 장점이 있다.