1. 배열이란
C 배열(Array)
- 데이터가 메모리에 연속적으로 저장된다.
- 크기가 고정되어 있다.
- 각 요소를 다른 값으로 수정할 수는 있지만 삭제할 수는 없다.
- 같은 타입의 데이터만 담을 수 있다.
Python 리스트(List)
- 각 데이터를 가리키는 레퍼런스를 저장한다.
- 데이터의 크기에 상관 없이 데이터의 레퍼런스를 요소에 저장한다.
- 다양한 타입의 데이터를 담을 수 있다.
2. 배열 인덱스를 이용한 데이터 저장/접근법
- 배열은 배열이 시작되는 지점의 주소를 가리킨다.
- 배열의 요소들은 시작 지점을 기준으로 메모리에 순서대로, 그리고 연속적으로 저장된다.
- 해당 인덱스에 해당하는 요소의 주소를 세 값(시작 주소, 요소의 크기, 인덱스)의 연산으로 바로 구할 수 있다.한다
- 배열 접근 연산 Time complexity: O(1)
3. 배열 탐색
탐색
- 특정 조건을 만족하는 값을 찾는 것
배열 탐색
- 배열은 특정 순서로 정렬되어 있지 않는 이상, 순서대로 데이터를 하나씩 찾는 선형 탐색(Linear search)을 해야 한다
- 배열 탐색 연산 Time complexity: O(n)
4. 정적 배열과 동적 배열
정적 배열(Static array)
- 처음 정의할 때 크기(length)를 정해 놓고 정해진 크기 이상 값을 추가할 수 없다.
- 정적 배열은 메모리를 배열의 크기만큼 차지하고, 마지막 요소의 다음 메모리 셀을 사용할 수 없기 때문이다.
- C 배열이 정적 배열이다.
동적 배열(Dynamic Array)
- 처음 정의한 크기에 요소가 가득 차도 계속해서 값을 추가할 수 있다.
- 정적 배열을 사용하여 만든다.
- 배열에 요소가 가득 찼을 때 새로운 요소를 추가하려고 하면, 배열에 더 큰 메모리를 할당하고 배열의 요소들을 복사하는 방식으로 작동한다.
- 복사 후에 기존 배열을 참조하고 있는 값이 더이상 없다면 기존 배열이 차지하던 공간은 메모리에서 가비지 컬렉터에 의해 자동으로 삭제된다.
- Python 리스트가 동적 배열이다.
파이썬 리스트(동적 배열)의 비밀
- 리스트가 내부적으로 사용하고 있는 크기는 리스트의 length와 다를 수 있다.
len()함수로 리스트의 길이를 출력하면 실제 사용하고 있는 메모리 공간이 더 많을지라도, 가리키고 있는 값이 있는 공간에 대해서만 출력된다.- 채워지지 않은 공간을 접근하려고 하면 오류가 난다.
- 파이썬뿐만 아니라, 동적 배열을 자료형으로 제공하는 대부분의 언어들은 이렇게 실제 사용하는 배열의 크기와 상관없이 저장해 놓은 공간만 사용할 수 있게 처리를 해 준다.
5. 동적 배열 추가 연산 시간 복잡도
추가 연산(append operation)
- 배열의 끝에 새 값을 넣는 연산
정적 배열에 남는 공간이 있을 때
- 인덱스를 이용해서 접근할 수 있다.
- Time complexity: O(1)
정적 배열에 남는 공간이 없을 때
- 배열의 요소들을 새롭게 할당된 메모리에 복사한 후 새 값을 추가해야 한다.
- Time complexity: O(n)
추가 연산의 시간 복잡도
- Worst-case time complexity: O(n)
- Best-case time complexity: O(1)
- Average-case time complexity: O(1)
6. 동적 배열 삽입 연산 시간 복잡도
삽입 연산(insert operation)
- 배열의 원하는 위치에 새 값을 넣는 연산
정적 배열에 남는 공간이 있을 때
- 삽입할 위치 뒤에 요소가 있다면, 한 칸씩 뒤로 이동시켜야 한다.
- Worst-case time complexity: O(n)
- Best-case time complexity: O(1)
- Average-case time complexity: O(n)
정적 배열에 남는 공간이 없을 때
- 새로운 메모리를 할당한 후 원래 배열을 복사하고, 삽입 연산을 수행한다.
- Worst-case time complexity: O(n)
- Best-case time complexity: O(n)
- Average-case time complexity: O(n)
삽입 연산의 시간 복잡도
- Worst-case time complexity: O(n)
- Best-case time complexity: O(1)
- Average-case time complexity: O(n)
7. 동적 배열 삭제 연산 시간 복잡도
삭제 연산(delete operation)
- 배열의 특정 위치에 있는 데이터를 지우는 연산
- 삭제하고 싶은 데이터 뒤에 있는 모든 데이터 요소들을 한 칸씩 앞으로 밀어서 저장하면 된다.
- 파이썬에서는 마지막 인덱스에 해당하던 값을 지우는 대신 접근할 수 없게 만든다.
삭제 연산의 시간 복잡도
- Worst-case time complexity: O(n)
- Best-case time complexity: O(1)
- Average-case time complexity: O(n)
8. 동적 배열 크기 줄이기
동적 배열의 크기를 줄이는 방법
- 크기가 작은 새로운 배열을 만들고 기존 배열의 요소들을 새로운 배열로 옮겨서 저장한다.
- 배열의 크기에 비해 사용 비율이 작을 때, 프로그래밍 언어가 정한 비율을 넘어가면 자동으로 배열의 크기를 줄이곤 한다.
- 맨 끝 데이터를 삭제하더라도 자동으로 배열의 메모리 크기가 줄어드는 경우에는 시간 복잡도가 O(n)이다.
맨 끝 데이터 삭제의 시간 복잡도
- Worst-case time complexity: O(n)
- Best-case time complexity: O(1)
- Average-case time complexity: O(1)
9. 배열과 동적 배열 정리/비교
배열(정적 배열)이 동적 배열과 다른 점
- 동적 배열과 달리 배열에는 삽입과 삭제 연산을 할 수 없다.
배열이 낭비하는 공간
- 크기가 고정되어 있기 때문에 낭비하는 공간이 없다.
동적 배열이 낭비하는 공간
- 동적 배열이 사용하는 정적 배열의 메모리 크기가 기존 배열의 배수로 늘어나는 상황에서 space complexity O(n)을 갖는다.
Feedback
- Java, JavaScript 등 다른 언어의 배열 구조간의 공통점과 차이점도 공부해보자.
참고 자료
job's done