개념

• 모든 원소를 단일 메모리 청크(chunk)에 저장
• 모든 원소가 같은 타입이면, 같은 크기의 메모리를 사용하고, 이는 sizeof(type)으로 표시됨
• 첫 번째 원소의 메모리 주소를 시작 주소(BA, Base Address)라고 함
• i번째 원소에 접근하려면 BA + i * sizeof(type)
• 배열의 전체 크기에 상관없이 모든 원소에 곧바로 접근 가능
• 데이터 접근 시간이 항상 일정함
• 빅오(Big-O) 표기법으로 O(1)
• 배열의 유형
  • 정적 배열(static array)
    • 스택(stack) 메모리 영역에 할당
    • 선언된 블록이 끝나면 소멸
    • int arr[size];
  • 동적 배열(dynamic array)
    • 힙(heap) 영역에 할당, 사용자 직접 해제 전까지 유지
    • 프로그래머가 생성 시점과 해제 시점을 자유롭게 결정
    • int* arr = new int[size];
  • 두 가지 유형 모두 다양한 연산에서 동일한 성능을 나타냄
  • C언어에서 도입되었기 때문에 C스타일 배열이라고도 함
• 캐시 지역성(cache locality)
  • 첫 번째 원소를 가져온 후 다음 원소는 캐시에서 바로 참조할 수 있으므로 배열은 캐시 지역성이 좋다고 말할 수 있다.

백준 1337번

#include <iostream>
#include <algorithm>

using namespace std;

#define endl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N;
    cin >> N;
    int* A = new int[N];
    for (int i = 0; i < N; i++)
        cin >> A[i];

    sort(A, A + N);
    int ans = 4;
    for (int i = 0; i < N; i++) {
        int* it = lower_bound(A + i, A + N, A[i] + 5);
        ans = min(ans, 5 - static_cast<int>(distance(A + i, it)));
    }

    delete[] A;
    
    cout << ans << endl;
}

• 동적 배열을 new로 할당하고 delete로 해제
• lower_bound: 찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위함 (이 함수를 사용하려면 정렬되어 있어야 하므로 먼저 sort)
  • A[i] + 5와 일치하는 값이 있다면 A[i] + 5의 반복자 리턴
  • 일치하는 게 없다면 A[i] + 5를 초과하는 것 중 가장 작은 반복자 리턴
• 5에서 A + i와 it 사이의 distance를 뺀 값과 4를 비교하여 더 작은 값을 ans로 리턴 (연속되는 숫자가 하나도 없을 경우 추가되어야 하는 숫자의 갯수는 4개)
• distance 함수의 리턴 타입과 관련하여 컴파일 에러 발생 -> int로 static cast 처리