자료구조와 알고리즘 - 배열과 문자열 정리
1. 배열(Array)이란?
배열은 같은 자료형의 데이터를 여러 개 연속된 메모리 공간에 저장하는 자료구조입니다.
int Numbers[5] = {10, 20, 30, 40, 50};메모리에서는 개념적으로 다음과 같이 저장됩니다.
[10][20][30][40][50]각 요소에는 인덱스(Index)가 존재합니다.
Numbers[0] → 10
Numbers[1] → 20
Numbers[2] → 30
Numbers[3] → 40
Numbers[4] → 50C++ 배열의 인덱스는 0부터 시작합니다.
배열에서 가장 중요한 특징은 데이터가 메모리상 연속적으로 저장된다는 것입니다.
2. 인덱스(Index)
인덱스는 배열에서 특정 요소의 위치를 나타내는 번호입니다.
int Numbers[5] = {10, 20, 30, 40, 50};
int Value = Numbers[2];위 코드에서 Numbers[2]는 세 번째 요소인 30을 의미합니다.
Index
0 1 2 3 4
↓ ↓ ↓ ↓ ↓
[10] [20] [30] [40] [50]따라서 배열의 요소에 접근할 때:
Numbers[0];
Numbers[1];
Numbers[2];처럼 인덱스를 이용합니다.
3. 배열의 메모리 구조
배열의 핵심은 메모리가 연속적으로 배치된다는 것입니다.
예를 들어 int가 4바이트라고 가정하면:
주소
1000 → [10]
1004 → [20]
1008 → [30]
1012 → [40]
1016 → [50]각 요소가 일정한 간격으로 배치되어 있습니다.
컴퓨터는 배열의 시작 주소와 인덱스를 이용하여 원하는 요소의 위치를 계산할 수 있습니다.
개념적으로는 다음과 같습니다.
요소의 주소
= 시작 주소 + (인덱스 × 자료형의 크기)예를 들어 Numbers[3]에 접근한다면:
시작 주소 + (3 × sizeof(int))와 같은 방식으로 위치를 계산할 수 있습니다.
그래서 배열은 인덱스를 알고 있다면 많은 데이터를 처음부터 하나씩 확인하지 않고 원하는 위치에 바로 접근할 수 있습니다.
4. 배열의 인덱스 접근은 왜 O(1)인가?
예를 들어 데이터가 10개인 배열에서:
Numbers[5];에 접근하는 것과 데이터가 100만 개 있는 배열에서:
Numbers[500000];에 접근하는 것은 기본적으로 같은 방식으로 처리됩니다.
데이터가 몇 개 있는지와 관계없이 시작 주소와 인덱스를 이용하여 해당 위치를 바로 계산하기 때문입니다.
따라서 배열의 인덱스를 이용한 접근은:
O(1)입니다.
여기서 주의해야 할 점이 있습니다.
인덱스를 알고 특정 위치에 접근
→ O(1)
특정 값을 찾아야 함
→ O(N)둘은 다른 작업입니다.
5. 배열에서 탐색
배열에서 값을 찾는다고 생각해보겠습니다.
int Numbers[5] = {10, 20, 30, 40, 50};여기에서 40을 찾으려고 합니다.
40이 세 번째 인덱스라는 것을 미리 알고 있다면:
Numbers[3];으로 바로 접근할 수 있습니다.
하지만 실제로는 보통 40이 몇 번째에 있는지 모릅니다.
따라서 처음부터 확인해야 할 수 있습니다.
10 → 20 → 30 → 40최악의 경우 마지막 요소까지 확인해야 합니다.
따라서 배열에서 값을 순차적으로 탐색하는 경우 시간 복잡도는:
O(N)입니다.
6. 배열의 삽입
배열에서 삽입은 위치에 따라 차이가 있습니다.
예를 들어 다음 배열이 있습니다.
[10][20][30][40][50]여기에 30 앞에 25를 추가한다고 생각해보겠습니다.
원하는 결과는:
[10][20][25][30][40][50]입니다.
그런데 기존 배열에는 이미 공간이 차 있습니다.
따라서 기존 데이터를 이동해야 합니다.
기존
[10][20][30][40][50]
30, 40, 50을 뒤로 이동
[10][20][ ][30][40][50]
25 삽입
[10][20][25][30][40][50]여러 데이터를 이동해야 하기 때문에 중간 삽입은 일반적으로:
O(N)입니다.
7. 배열의 삭제
삭제도 삽입과 비슷합니다.
[10][20][30][40][50]여기서 30을 삭제한다고 가정합니다.
결과는:
[10][20][40][50]가 되어야 합니다.
그런데 30이 빠지면 뒤에 있던 40, 50을 앞으로 이동해야 합니다.
[10][20][30][40][50]
30 삭제
[10][20][40][50]따라서 중간 요소의 삭제 역시 데이터를 이동해야 하므로 일반적으로:
O(N)입니다.
8. 배열의 시간 복잡도
배열에서 기본적으로 알아야 할 시간 복잡도는 다음과 같습니다.
작업시간 복잡도
| 인덱스 접근 | O(1) |
| 값 탐색 | O(N) |
| 중간 삽입 | O(N) |
| 중간 삭제 | O(N) |
다만 맨 끝에 데이터를 추가하는 경우는 사용하는 배열의 종류에 따라 다릅니다.
고정 크기의 C-style 배열:
int Numbers[5];은 크기를 변경할 수 없기 때문에 데이터를 추가한다는 개념을 직접 적용하기 어렵습니다.
반면 std::vector와 같은 동적 배열에서는 맨 뒤에 데이터를 추가할 수 있습니다.
9. 배열의 장점
1. 인덱스 접근이 빠르다
Numbers[100];처럼 원하는 위치에 바로 접근할 수 있습니다.
시간 복잡도는:
O(1)입니다.
2. 메모리가 연속적이다
배열의 데이터가 메모리에 붙어서 저장되기 때문에 CPU가 데이터를 처리할 때 효율적인 경우가 많습니다.
3. 구조가 단순하다
배열은 자료구조의 가장 기본적인 형태이기 때문에 다른 자료구조를 이해하는 데에도 중요한 기초가 됩니다.
10. 배열의 단점
1. 중간 삽입과 삭제가 느리다
중간에 데이터를 추가하거나 제거하면 다른 요소들을 이동시켜야 할 수 있습니다.
따라서 일반적으로:
삽입 → O(N)
삭제 → O(N)이 됩니다.
2. 고정 크기 배열은 크기를 변경할 수 없다
int Numbers[5];라고 선언하면 배열의 크기는 5개로 정해집니다.
나중에:
5개 → 10개처럼 직접 크기를 변경할 수 없습니다.
이러한 문제를 해결하기 위해 동적 배열이 등장합니다.
11. 정적 배열
정적 배열은 일반적으로 크기가 고정된 배열을 의미합니다.
대표적인 예가 C-style 배열입니다.
int Numbers[5];이 배열은 5개의 int를 저장할 수 있습니다.
[ ][ ][ ][ ][ ]배열의 크기는 선언할 때 결정됩니다.
int Numbers[5];에서 5라는 크기는 이후에 변경할 수 없습니다.
12. 동적 배열
동적 배열은 실행 중에 필요한 크기의 메모리를 확보하고 크기를 변경할 수 있는 배열 구조입니다.
C++에서는 직접 동적 메모리를 할당하는 것도 가능합니다.
int* Numbers = new int[5];하지만 직접 new[]와 delete[]를 이용하여 메모리를 관리하는 것은 실수하기 쉽습니다.
현대적인 C++에서는 일반적인 동적 배열이 필요하다면 보통:
std::vector를 사용하는 것이 좋습니다.
즉:
고정 크기 배열
→ C-style Array
→ std::array
동적으로 크기가 변하는 배열
→ std::vector라고 연결해서 생각하면 됩니다.
13. C-style Array
C++에서 가장 기본적인 배열 형태입니다.
int Numbers[5] = {10, 20, 30, 40, 50};특징은:
- 크기가 고정되어 있음
- 인덱스 접근 가능
- 메모리가 연속적으로 배치됨
- 인덱스 접근 O(1)
- 크기를 직접 변경할 수 없음
입니다.
기본적인 배열의 동작을 이해하기에는 매우 좋은 형태입니다.
14. std::array
C++에서는 C-style 배열과 별개로 std::array를 사용할 수 있습니다.
std::array<int, 5> Numbers = {10, 20, 30, 40, 50};std::array 역시 크기가 고정된 배열입니다.
[10][20][30][40][50]따라서:
std::array
→ 크기 변경 불가능
→ 인덱스 접근 가능
→ 연속적인 메모리이라는 특징을 가집니다.
C-style 배열보다 C++ 컨테이너답게 사용할 수 있는 다양한 기능을 제공합니다.
예를 들어:
Numbers.size();를 사용하면 배열의 크기를 확인할 수 있습니다.
15. std::vector
std::vector는 C++에서 매우 중요한 컨테이너입니다.
쉽게 말하면:
동적으로 크기가 변경되는 배열
입니다.
std::vector<int> Numbers;처음에는 요소가 없습니다.
[]여기에:
Numbers.push_back(10);
Numbers.push_back(20);
Numbers.push_back(30);을 실행하면:
[10][20][30]이 됩니다.
이후에도 계속 데이터를 추가할 수 있습니다.
Numbers.push_back(40);
Numbers.push_back(50);결과:
[10][20][30][40][50]즉, C-style 배열처럼 연속적인 메모리를 사용하는 배열의 특징을 유지하면서 필요에 따라 저장 공간을 늘릴 수 있는 자료구조입니다.
16. vector의 size와 capacity
std::vector를 제대로 이해하려면 반드시 알아야 하는 개념입니다.
예를 들어 vector에 데이터가 3개 들어 있다고 하겠습니다.
[10][20][30][ ][ ][ ]여기서:
size = 3
capacity = 6이라고 가정할 수 있습니다.
size
현재 실제로 들어 있는 요소의 개수입니다.
Numbers.size();예를 들어:
3을 반환합니다.
capacity
현재 vector가 추가적인 메모리 할당 없이 저장할 수 있도록 확보해 둔 공간의 크기입니다.
Numbers.capacity();예를 들어:
6을 반환할 수 있습니다.
따라서:
size
→ 실제 데이터 개수
capacity
→ 현재 확보한 저장 공간입니다.
17. vector는 왜 capacity를 사용하는가?
만약 데이터를 하나 추가할 때마다 메모리를 새로 할당한다고 생각해보겠습니다.
1개 추가
→ 메모리 할당
2개 추가
→ 메모리 할당
3개 추가
→ 메모리 할당
4개 추가
→ 메모리 할당이렇게 매번 메모리를 새로 확보하면 비효율적입니다.
그래서 vector는 여유 공간을 확보해 놓고 사용합니다.
예를 들어:
size = 3
capacity = 8이라면:
[10][20][30][ ][ ][ ][ ][ ]현재 데이터는 3개지만 추가 공간이 존재합니다.
따라서 새로운 데이터를 추가할 때 기존에 확보한 공간을 사용할 수 있습니다.
18. Vector의 재할당(Reallocation)
vector의 capacity가 모두 사용된 상태에서 새로운 데이터를 추가하면 더 큰 메모리 공간이 필요할 수 있습니다.
예를 들어:
capacity = 3
[10][20][30]여기서:
Numbers.push_back(40);을 실행한다고 생각해보겠습니다.
현재 공간에는 여유가 없습니다.
그러면 개념적으로:
기존 메모리
[10][20][30]↓
더 큰 메모리 확보
[ ][ ][ ][ ][ ][ ]↓
기존 데이터 이동
[10][20][30][ ][ ][ ]↓
새 데이터 추가
[10][20][30][40][ ][ ]와 같은 과정이 발생할 수 있습니다.
이때 기존 메모리에서 새로운 메모리로 데이터를 옮기는 과정을 재할당(Reallocation)이라고 합니다.
따라서 vector의 push_back()은 일반적으로 빠르지만, 재할당이 발생하는 순간에는 비용이 커질 수 있습니다.
19. reserve()
vector가 앞으로 많은 데이터를 저장할 것을 알고 있다면 미리 공간을 확보할 수 있습니다.
std::vector<int> Numbers;
Numbers.reserve(100);이 경우 최소 100개의 요소를 저장할 수 있는 capacity를 확보합니다.
중요한 것은:
Numbers.reserve(100);을 했다고 해서 데이터가 100개 생기는 것은 아니라는 점입니다.
즉:
size = 0
capacity >= 100입니다.
20. reserve()와 resize()의 차이
둘은 헷갈리기 쉬우므로 반드시 구분해야 합니다.
reserve()
저장 공간을 확보합니다.
Numbers.reserve(100);개념적으로:
size = 0
capacity >= 100입니다.
resize()
실제 요소의 개수를 변경합니다.
Numbers.resize(100);그러면:
size = 100이 됩니다.
따라서:
reserve
→ 공간을 미리 확보
resize
→ 실제 요소 개수를 변경이라고 기억하면 됩니다.
21. vector의 주요 기능
std::vector<int> Numbers;push_back()
맨 뒤에 요소를 추가합니다.
Numbers.push_back(10);결과:
[10]pop_back()
맨 뒤 요소를 제거합니다.
Numbers.pop_back();예:
[10][20][30]
↓ pop_back()
[10][20]size()
현재 요소 개수를 반환합니다.
Numbers.size();capacity()
현재 확보된 저장 공간의 크기를 확인합니다.
Numbers.capacity();empty()
vector가 비어 있는지 확인합니다.
Numbers.empty();비어 있다면:
true그렇지 않다면:
false를 반환합니다.
인덱스 접근
Numbers[0];처럼 배열과 동일하게 인덱스로 접근할 수 있습니다.
따라서:
vector의 인덱스 접근
→ O(1)입니다.
22. 문자열(String)이란?
문자열은 문자(Character)가 여러 개 연속해서 구성된 데이터라고 생각할 수 있습니다.
예를 들어:
"Hello"는 개념적으로:
[H][e][l][l][o]와 같은 형태입니다.
C++에서는 문자열을 여러 가지 방식으로 표현할 수 있지만, 일반적인 문자열 처리에서는:
std::string을 많이 사용합니다.
23. C-style 문자열
C에서는 문자열을 char 배열로 표현합니다.
char Name[] = "Hello";여기서 중요한 것이 있습니다.
문자열의 마지막에는 **널 문자 '\0'**가 들어갑니다.
실제로는:
[H][e][l][l][o][\0]와 같은 형태입니다.
'\0'은:
문자열이 여기서 끝났다는 것을 나타내는 특별한 문자
입니다.
따라서 "Hello"는 눈에 보이는 문자는 5개이지만 C-style 문자열을 저장하기 위해서는 '\0'까지 포함하여 6개의 char 공간이 필요합니다.
24. std::string
현대적인 C++에서는 일반적인 문자열을 다룰 때 std::string을 사용하는 것이 편리합니다.
std::string Name = "Hello";문자열의 길이를 확인할 수 있습니다.
Name.size();문자열의 특정 문자에도 인덱스로 접근할 수 있습니다.
Name[0];결과:
'H'문자열을 이어붙일 수도 있습니다.
Name += " World";결과:
"Hello World"즉:
std::string
→ 문자열을 편리하게 관리하기 위한 C++ 클래스라고 이해하면 됩니다.
25. 문자열과 배열의 관계
문자열도 결국 문자의 연속적인 데이터라는 점에서 배열과 연결됩니다.
예를 들어:
int 배열
[10][20][30][40]문자열:
[H][e][l][l][o][\0]둘 다 여러 개의 데이터를 연속적으로 저장한다는 공통점이 있습니다.
차이점은 문자열에서는 문자 데이터를 저장하고, C-style 문자열에서는 '\0'이라는 종료 문자를 사용한다는 것입니다.
26. C-style Array / std::array / std::vector 비교
특징C-style Arraystd::arraystd::vector
| 크기 | 고정 | 고정 | 동적 |
| 인덱스 접근 | O(1) | O(1) | O(1) |
| 연속적인 메모리 | O | O | O |
| 크기 변경 | X | X | O |
| C++ 컨테이너 기능 | 적음 | 많음 | 많음 |
| 동적 추가 | X | X | O |
정리하면:
C-style Array
→ 가장 기본적인 배열
std::array
→ C++ 방식의 고정 크기 배열
std::vector
→ 동적으로 크기를 변경할 수 있는 배열입니다.
27. 배열과 연결 리스트의 차이
다음 자료구조인 연결 리스트(Linked List)를 이해하기 위해 배열의 특징을 다시 비교해보겠습니다.
배열:
[10][20][30][40][50]메모리가 연속적으로 배치됩니다.
따라서:
인덱스 접근 → O(1)이라는 장점이 있습니다.
반면 중간에 데이터를 삽입하거나 삭제하면 데이터를 이동해야 할 수 있습니다.
중간 삽입/삭제 → O(N)연결 리스트는:
[10] → [20] → [30] → [40]처럼 각 노드가 연결되어 있는 구조입니다.
특정 위치를 찾아가는 것은 느릴 수 있지만, 이미 해당 위치에 접근해 있다는 조건에서는 노드의 연결을 변경하여 삽입/삭제를 수행할 수 있습니다.
따라서 이후 연결 리스트를 배울 때는 단순히 "연결 리스트를 외운다"가 아니라:
배열의 어떤 문제를 해결하기 위해 연결 리스트가 등장했는가?
라는 관점으로 보는 것이 중요합니다.
28. 배열과 vector의 핵심 시간 복잡도
작업배열vector
| 인덱스 접근 | O(1) | O(1) |
| 값 탐색 | O(N) | O(N) |
| 중간 삽입 | O(N) | O(N) |
| 중간 삭제 | O(N) | O(N) |
| 맨 뒤 추가 | 고정 배열은 불가 | 평균적으로 O(1) |
| 맨 뒤 삭제 | 고정 배열은 별도 처리 | O(1) |
vector의 맨 뒤 추가가 평균적으로 O(1)인 이유는 대부분의 push_back()이 이미 확보된 capacity 안에서 수행되기 때문입니다.
다만 capacity가 부족해서 재할당이 발생하면 해당 한 번의 삽입은 O(N)의 비용이 발생할 수 있습니다.
29. 언리얼 엔진과 연결하기
언리얼 엔진 C++을 공부한다면 이 개념은 실제 코드에서도 계속 등장합니다.
대표적으로 언리얼에서는:
TArray
TMap
TSet등의 컨테이너를 사용합니다.
그중 TArray는 지금 배우고 있는 배열과 동적 배열의 개념을 이해하는 데 특히 중요합니다.
예를 들어:
TArray<AActor*> Actors;라고 하면 여러 AActor*를 배열 형태로 관리할 수 있습니다.
따라서 지금 배우는:
배열
↓
연속적인 메모리
↓
인덱스 접근
↓
동적 배열
↓
vector
↓
TArray의 흐름을 이해해두면 나중에 언리얼의 TArray를 공부할 때 단순한 API 암기가 아니라 왜 이런 자료구조를 사용하는지까지 이해할 수 있습니다.
30. 이번 단원 핵심 정리
이번 단원에서 가장 중요한 내용을 다시 정리하면 다음과 같습니다.
배열
배열은 같은 자료형의 데이터를 연속적인 메모리에 저장하는 자료구조입니다.
인덱스 접근
Numbers[3];처럼 인덱스로 접근하면 원하는 위치를 직접 계산할 수 있기 때문에:
O(1)입니다.
탐색
값을 찾는 경우에는 처음부터 하나씩 확인해야 할 수 있기 때문에 일반적인 선형 탐색은:
O(N)입니다.
삽입
중간에 데이터를 삽입하면 뒤쪽 데이터를 이동해야 할 수 있으므로:
O(N)입니다.
삭제
중간 데이터를 삭제하면 뒤쪽 데이터를 앞으로 이동해야 할 수 있으므로:
O(N)입니다.
정적 배열
크기가 고정되어 있습니다.
int Numbers[5];std::array
C++에서 사용하는 고정 크기 배열입니다.
std::array<int, 5> Numbers;std::vector
동적으로 크기를 변경할 수 있는 배열 형태의 컨테이너입니다.
std::vector<int> Numbers;size
현재 실제로 들어 있는 요소의 개수입니다.
Numbers.size();capacity
현재 확보된 저장 공간입니다.
Numbers.capacity();reserve
미리 저장 공간을 확보합니다.
Numbers.reserve(100);resize
실제 요소의 개수를 변경합니다.
Numbers.resize(100);C-style 문자열
char 배열로 표현하며 문자열 끝에 '\0'이 들어갑니다.
char Name[] = "Hello";실제 개념:
[H][e][l][l][o][\0]std::string
C++에서 문자열을 편리하게 관리하기 위한 클래스입니다.
std::string Name = "Hello";최종적으로 기억할 구조
배열
│
├─ 연속적인 메모리
│
├─ 인덱스 접근 → O(1)
│
├─ 값 탐색 → O(N)
│
├─ 중간 삽입 → O(N)
│
└─ 중간 삭제 → O(N)
│
├── C-style Array
│ └─ 고정 크기
│
├── std::array
│ └─ 고정 크기 + C++ 컨테이너
│
└── std::vector
├─ 동적 크기
├─ size
├─ capacity
├─ reserve
├─ resize
└─ push_back / pop_back
문자열
│
├── C-style String
│ └─ char 배열 + '\0'
│
└── std::string
└─ C++ 문자열 클래스
언리얼
│
└── TArray
└─ 배열/동적 배열 개념과 연결
'자료구조와 알고리즘' 카테고리의 다른 글
| 탐색 알고리즘 (0) | 2026.08.27 |
|---|---|
| 재귀 (0) | 2026.08.26 |
| 스택과 큐 (0) | 2026.08.25 |
| 연결 리스트 (0) | 2026.08.24 |
| 시간 복잡도와 공간복잡도, Big-O (0) | 2026.08.20 |