1. 배열 (Array)
1. 배열 (Array)
개념
배열은 동일한 타입의 데이터를 연속된 메모리 공간에 저장하는 가장 기본적인 자료구조이다.
- 인덱스를 통해 임의 접근(Random Access)이 가능하다
- 메모리상에서 연속적으로 배치되어 캐시 효율이 좋다
- 정적 배열은 크기가 컴파일 타임에 고정된다
- 삽입/삭제 시 요소들을 이동시켜야 하므로 비효율적이다
핵심 연산 & 시간복잡도
| 연산 | 시간복잡도 | 설명 |
|---|---|---|
| 접근 | O(1) | 인덱스로 직접 접근 |
| 탐색 | O(N) | 순차 탐색 기준 |
| 삽입 | O(N) | 요소 이동 필요 |
| 삭제 | O(N) | 요소 이동 필요 |
| 맨 뒤 삽입 | O(1) | 이동 없음 |
| 맨 뒤 삭제 | O(1) | 이동 없음 |
구현 (No-STL)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 정적 배열 선언
int arr[100];
int arr2[100] = {0}; // 0으로 초기화
int arr3[] = {1, 2, 3, 4, 5}; // 크기 자동 추론
// 2차원 배열
int matrix[100][100];
int matrix2[3][3] = { {1,2,3}, {4,5,6}, {7,8,9} };
// 배열 크기 구하기 (정적 배열만 가능)
int size = sizeof(arr3) / sizeof(arr3[0]); // 5
// 배열 복사
int src[5] = {1, 2, 3, 4, 5};
int dst[5];
for (int i = 0; i < 5; i++) {
dst[i] = src[i];
}
// 또는 memcpy 사용
#include <cstring>
memcpy(dst, src, sizeof(src));
// 배열 초기화
memset(arr, 0, sizeof(arr)); // 0으로 초기화
memset(arr, -1, sizeof(arr)); // -1로 초기화 (주의: 바이트 단위)
fill(arr, arr + 100, 0); // fill 사용
// 동적 배열 (malloc)
int* dynamicArr = (int*)malloc(sizeof(int) * n);
free(dynamicArr);
// 동적 배열 (new)
int* dynamicArr2 = new int[n];
delete[] dynamicArr2;
STL
std::array (C++11, 고정 크기)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <array>
// 선언 및 초기화
std::array<int, 5> arr = {1, 2, 3, 4, 5};
std::array<int, 5> arr2{}; // 0으로 초기화
std::array<int, 5> arr3; // 초기화되지 않음
// 주요 메서드
arr.size(); // 크기 반환: 5
arr.empty(); // 비어있는지 확인
arr.front(); // 첫 번째 요소
arr.back(); // 마지막 요소
arr.at(2); // 인덱스 2 접근 (범위 체크 O)
arr[2]; // 인덱스 2 접근 (범위 체크 X, 더 빠름)
arr.fill(0); // 모든 요소를 0으로 채움
arr.data(); // 내부 배열 포인터 반환
// 정렬
std::sort(arr.begin(), arr.end());
std::vector (동적 배열)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <vector>
// 선언 및 초기화
std::vector<int> v; // 빈 벡터
std::vector<int> v1(5); // 크기 5, 0으로 초기화
std::vector<int> v2(5, 10); // 크기 5, 10으로 초기화
std::vector<int> v3 = {1, 2, 3, 4, 5}; // 초기화 리스트
std::vector<int> v4(v3); // 복사 생성
std::vector<int> v5(v3.begin(), v3.end()); // 범위로 생성
// 2차원 벡터
std::vector<std::vector<int>> matrix(n, std::vector<int>(m, 0));
// 주요 메서드
v.size(); // 요소 개수
v.capacity(); // 할당된 공간 크기
v.empty(); // 비어있는지 확인
v.clear(); // 모든 요소 삭제
v.resize(10); // 크기 변경
v.resize(10, 5); // 크기 변경, 새 요소는 5로 초기화
v.reserve(100); // 메모리 미리 할당 (재할당 방지)
// 요소 접근
v.front(); // 첫 번째 요소
v.back(); // 마지막 요소
v[i]; // 인덱스 접근 (범위 체크 X)
v.at(i); // 인덱스 접근 (범위 체크 O)
// 삽입
v.push_back(10); // 맨 뒤에 삽입 O(1) amortized
v.emplace_back(10); // 맨 뒤에 삽입 (생성자 직접 호출, 더 효율적)
v.insert(v.begin(), 5); // 맨 앞에 5 삽입 O(N)
v.insert(v.begin() + 2, 5); // 인덱스 2에 5 삽입
v.insert(v.end(), {1,2,3}); // 맨 뒤에 여러 요소 삽입
// 삭제
v.pop_back(); // 맨 뒤 삭제 O(1)
v.erase(v.begin()); // 맨 앞 삭제 O(N)
v.erase(v.begin() + 2); // 인덱스 2 삭제
v.erase(v.begin(), v.begin() + 3); // 범위 삭제
// 정렬 및 탐색
std::sort(v.begin(), v.end()); // 오름차순 정렬
std::sort(v.begin(), v.end(), std::greater<>()); // 내림차순 정렬
std::reverse(v.begin(), v.end()); // 뒤집기
auto it = std::find(v.begin(), v.end(), 5); // 5 찾기
bool found = std::binary_search(v.begin(), v.end(), 5); // 이진 탐색 (정렬 필요)
사용 예시
누적합 (Prefix Sum)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 1차원 누적합
int arr[N], prefix[N+1];
prefix[0] = 0;
for (int i = 1; i <= N; i++) {
prefix[i] = prefix[i-1] + arr[i-1];
}
// 구간 [l, r] 합 = prefix[r+1] - prefix[l]
// 2차원 누적합
int matrix[N][M], prefix[N+1][M+1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
prefix[i][j] = matrix[i-1][j-1]
+ prefix[i-1][j]
+ prefix[i][j-1]
- prefix[i-1][j-1];
}
}
// 구간 (r1,c1) ~ (r2,c2) 합
// = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]
투 포인터
1
2
3
4
5
6
7
8
9
10
11
12
13
// 정렬된 배열에서 합이 target인 두 수 찾기
int left = 0, right = n - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
// 찾음
break;
} else if (sum < target) {
left++;
} else {
right--;
}
}
슬라이딩 윈도우
1
2
3
4
5
6
7
8
9
10
// 크기 K인 연속 부분 배열의 최대 합
int windowSum = 0;
for (int i = 0; i < K; i++) {
windowSum += arr[i];
}
int maxSum = windowSum;
for (int i = K; i < n; i++) {
windowSum += arr[i] - arr[i - K];
maxSum = std::max(maxSum, windowSum);
}
주의사항 / Edge Cases
배열 범위 초과
1
2
int arr[10];
arr[10] = 5; // 인덱스는 0~9까지, 런타임 에러 또는 정의되지 않은 동작
memset 주의
1
2
3
4
5
6
int arr[10];
memset(arr, 1, sizeof(arr)); // 각 요소가 1이 아님! 0x01010101이 됨
memset(arr, 0, sizeof(arr)); // OK
memset(arr, -1, sizeof(arr)); // OK (0xFFFFFFFF)
// 다른 값으로 초기화하려면 fill 사용
std::fill(arr, arr + 10, 1);
전역 vs 지역 배열
1
2
3
4
5
6
int globalArr[1000000]; // OK, BSS 영역 (0으로 초기화됨)
int main() {
int localArr[1000000]; // Stack Overflow 위험! (스택은 보통 1MB)
static int staticArr[1000000]; // OK, 정적 영역
}
vector 재할당
1
2
3
4
5
6
7
8
9
10
11
std::vector<int> v;
for (int i = 0; i < 1000000; i++) {
v.push_back(i); // 내부적으로 여러 번 재할당 발생
}
// 개선: reserve로 미리 공간 확보
std::vector<int> v;
v.reserve(1000000);
for (int i = 0; i < 1000000; i++) {
v.push_back(i); // 재할당 없음
}
빈 배열 체크
1
2
3
4
5
6
std::vector<int> v;
// v[0]; // 런타임 에러
// v.front(); // 런타임 에러
if (!v.empty()) {
// 안전하게 접근
}
추천 문제
This post is licensed under CC BY 4.0 by the author.