1️⃣ 배열의 정의
프로그래밍에서 가장 자주 사용되는 자료구조중 하나인 배열은 번호(인덱스)와 번호에 대응하는 데이터들로 이루어져 있습니다. 일반적으로 배열에는 같은 종류의 데이터들이 순차적으로 저장되어, 값의 번호가 곧 배열의 시작점으로부터 값이 저장되어 있는 상대적인 위치가 됩니다.
그림으로 보면 다음과 같은 자료구조가 배열이라고 할 수 있습니다.
안에 있는 번호가 배열의 인덱스를 나타낸 것입니다.
기본적으로 인덱스는 0부터 시작합니다.
2️⃣ 파이썬에서의 배열의 선언
파이썬에서는 아래와 같이 기본적으로 배열을 선언할 수 있습니다.
1
2
3
arr = [] # 기본적인 배열의 선언
arr = [0] * 100 # 0으로 기본값이 들어간 크기 100 의 배열 선언
3️⃣ 배열의 시간복잡도
배열에 값을 넣을 땐 인덱스로 배열의 원소에 접근이 가능합니다.
배열의 원하는 원소를 탐색하는 것은 O(1)의 시간이 소요됩니다.
하지만 배열의 중간에 원소를 삽입하거나 삭제할 때는 O(n)의 시간이 소요됩니다.
삽입할 때는 뒤의 배열원소들을 한칸씩 밀어주고, 삭제할때또한 뒤의 배열원소들을 한칸씩 앞으로 당겨줘야하기 때문입니다.
마지막으로 배열의 끝에 원소를 추가하거나 삭제하는 것은 당겨주거나 밀어줄필요가 없기때문에 O(1)의 시간이 소요됩니다.
이를 표로 정리하면 다음과 같습니다.
| 연산 | 시간복잡도 |
|---|---|
| 탐색 | O(1) |
| 삽입 | O(n) |
| 삭제 | O(n) |
| 맨 끝 원소 삽입 | O(1) |
| 맨 끝 원소 삭제 | O(1) |
4️⃣ 장점과 단점
이를 토대로 배열의 장점과 단점을 정리해보자면 다음과 같습니다.
장점
- 인덱스로 바로 접근이 가능합니다.
- 구현이 쉽습니다.
- 배열은 하나의 연속된 메모리에 할당이 되기 때문에 빠른 성능을 보여줍니다.
단점
- 데이터의 삽입과 삭제에 비효율적입니다.
- 배열의 크기를 한번 생성하면 크기를 바꿀 수 없기 때문에 배열을 다사용하지 않으면 메모리의 낭비를 유발할 수 있습니다.
5️⃣ 배열은 어떤 곳에 쓰일까?
보통 배열은 스택에 많이 사용됩니다.
스택은 간단하게 말하면 LIFO(Last In First Out) 구조를 말하는데요.
자세한 것은 다음 포스팅에서 알아보도록 하겠습니다.
6️⃣ 마치며
오늘은 CS 복습을 하며 기본적인 배열에 대하여 알아보았습니다. 항상 알고리즘을 구현할때 배열은 거의 빠지지 않고 쓰이는데요.
다시한번 배열의 특징에 대해 상기해 볼 수 있는 좋은 시간이었던 것 같습니다.
궁금하거나 틀린점이 있다면 아래 댓글 부탁드립니다.
다음 시간엔 연결리스트에 대해 알아보도록 하겠습니다.
읽어주셔서 감사합니다.
