1. 배열이란(Array)
연관된 데이터를 하나의 변수에 그룹핑하여 관리하기 위한 자료구조로 하나의 변수에 여러 정보를 담을 수 있다. 변수가 하나의 데이터를 저장한다면,
배열은 여러 개의 데이터를 저장하는 차이가 있다.
1.1. 배열 선언 예시
- js기준
student = new Array();
student[0] = "정재민";
student[1] = "조은미"Value와 Index를 합쳐 Element라 부른다.
1.2. C 배열 특징
배열은 선언할 때부터 자료형과 크기가 지정된다. 또한 같은 타입의 데이터만 저장 및 수정이 가능하고 요소의 삭제는 불가하다. 만약 중간에 위치한 요소를 삭제 시 해당 인덱스는 Null 상태로 유지된다.
배열 선언 시 연속적인 메모리칸을 예약한 뒤 데이터가 나란히 연속적으로 저장된다.
C에서 하나의 정수를 저장하기 위해서는 4byte가 필요하며, 위 배열은 4개의 정수를 저장해야하므로 16byte 메모리를 할당받았다.
1.3. 파이썬 리스트 특징
파이썬의 리스트는 내부적으로 C 배열을 이용하여 만들어진 자료형이다.
append 메소드를 통해 언제든지 새로운 값을 추가할 수 있고, 배열과 달리 크기 및 자료형 지정이 필요없다.
리스트에 할당된 공간에는 변수의 값이 아닌 각 변수의 레퍼런스가 연속적으로 저장되어 있다.
* 각 메모리 공간에 실제값이 아닌 레퍼런스가 저장되어 있어 다양한 자료형을 저장할 수 있다.
2. 배열의 저장 방법 및 인덱스 접근에 관하여
C 언어 예시
int numArr[4]; //사용하고 있지 않고 연속적인 16칸 예약 numArr[0] = 2; numArr[1] = 3 numArr[2] = 5; numArr[3] = 7;
- 배열의 요소들이 메모리에 순서대로, 연속적으로 저장됨
- C 컴파일 시 배열명(numArr)은 배열이 시작되는 메모리 주소값을 가르킨다.
=> 배열의 값이 연속적으로 저장되어 있는 점을 이용하여, 아래와 같은 식이 성립된다.// 3번 인덱스 접근 numArr배열의 시작주소: 1000 1000 + 4 * 3 = 1012
- 배열의 값을 받아오기 위해선 그 값의 주소를 알아야하고, 주소는 간단한 계산식으로 구할 수 있다.
=> 어떤 인덱스에 접근하든 시간복잡도는 O(1)로 접근이 가능
=> RAM의 특성을 잘 이용한 자료 구조
3. 배열 탐색
- 탐색이란 특정 조건을 만족하는 값만 찾는 것으로 인덱스를 통해 값을 찾는 접근과 다른 개념
- 선형탐색 : 순서대로 데이터를 하나씩 찾는 탐색법
=> 특정 조건값을 찾기위해 배열의 0번 인덱스부터 마지막 인덱스까지 순차적으로 접근해야하기에 탐색은 접근보다 비효울적인 개념
(추가) 시간복잡도 정리
- 배열 접근 연산: O(1)
- 배열 탐색 연산: O(n)
- 배열에 값을 저장하고 접근하는 방식은 시간복잡도 O(1)로 효울적이지만,
특정 조건을 만족하는 값을 탐색할 경우 시간복잡도 O(n)으로 배열의 크기에 비례한다.
4. 정적 배열, 동적 배열 비교
정적 배열
- C의 배열에 해당하며 크기가 고정되어있다.
- 낭비되는 메모리 공간을 최소하 할 수 있다.
동적 배열
- 파이썬의 리스트에 해당하며 개발자 입장에서는 배열의 크기를 고민하지 않게된다.
- 상황에 맞게 크기가 바뀌는 유연성을 가지지만 동적 배열 자체는 정적 배열로 만들어진 자료구조.
5. 동적 배열의 추가 연산
배열의 끝에 새로운 값을 넣는 작업을 추가 연산(append operatoin)이라 정의.
동적 배열은 내부적으로 정적 배열을 통해 만들어진 자료형으로, 추가 연산 시 아래 2가지 경우의 수가 발생한다.
- 정적 배열에 남은 메모리 공간이 남아있을 경우
- 비어있는 공간 가장 앞 쪽 인덱스에 값을 저장
- 시간 복잡도: O(1)
- 정적 배열에 남은 메모리 공간이 없어 메모리 추가하는 경우
- 새로운 값을 추가하기 위해 현재 사용 중인 배열보다 더 큰 메모리 공간을 가진 새 배열 생성
- 기존 배열에서 새 배열로 값을 전부 복사한 뒤 마지막으로 새 값을 추가
- 시간 복잡도
=> 배열의 모든 인덱스를 접근해서 복사 O(n) + 새로운 값 추가 O(1) : O(n+1)
6. 삽입 연산
배열의 끝에 데이터를 추가하는 의미로 사용되는 append operation과 달리 배열 내 위치와 상관없이 요소를 추가할 때 Insert Operation이라 칭함.
삽입 연산에도 추가 연산과 같이 정적 배열에 공간있는 경우와 없는 경우 두 가지 경우의 수로 나뉜다.
- 배열 중간 데이터 삽입 연산
정적 배열 공간 비어 있을 때
- n번째 인덱스 뒤에 있는 데이터를 모두 한 칸씩 뒤로 밀어 n번 인덱스 칸에 공간을 만든다. n번 인덱스 칸에 새로운 데이터 삽입
- 시간 복잡도: 한 칸씩 뒤로 밀어주는 과정 O(n) + 데이터 삽입 O(1)
정적 배열 공간 없을 때
- 값을 추가하기 위해 현재 사용중인 배열보다 더 큰 메모리 공간을 가진 새 배열 생성
- 기존값을 새 배열에 복사
- n번째 인덱스 뒤에 있는 데이터를 모두 한 칸씩 뒤로 밀어 n번 인덱스 칸에 공간을 만든 후 새로운 데이터 삽입
- 시간 복잡도: 새 배열 생성 후 기존 값 복사 O(n)+ 한 칸씩 뒤로 밀어주는 과정 O(n) + 해당 인덱스 칸 데이터 삽입 O(1)
6. 삭제 연산
- 맨 앞 데이터를 지울 때
=> 시간복잡도: O(n)- 맨 뒤 데이터를 지울 때
=> 시간복잡도: O(1)
배열 연산 비교
- 추가(append): 마지막 인덱스 뒤 주소에 데이터 추가
- 삽입(insert): 임의 인덱스 주소에 데이터 추가
- 삭제(delete): 기존 배열 삭제 후 메모리 낭비 방지위해 내부적으로 새로운 배열(정적 배열) 생성 후 기존 요소 욺김
- 배열은 크기가 고정되어 있어 삽입, 삭제를 할 수 없다.
