1. (정적) 배열

1-1 특징

• 배열은 값을 가지는 원소의 집합으로 구성된 구조로, 하나 이상의 인덱스 또는 키로 식별됩니다.
• 같은 자료형끼리만 배열에 저장 할 수 있고, 크기가 고정된다는 특징이 있습니다.
  • int Arr[4]
    
• 대부분의 동적 프로그래밍 언어들은 정적 배열 자체가 없다. 파이썬에서도 정적 배열은 따로 없고 동적 배열인 리스트만 제공합니다.

1-2 장점

• 장점은 같은 자료형의 원소들을 하나의 변수를 선언 함으로써 여러 원소에 쉽게 접근할 수 있다는 것입니다.
• 메모리의 주소를 알면 (조금 더 간단하게는 그냥 인덱스만 알면) 어디에 있는 원소에도 한 번에 접근(O(1)) (임의접근)할 수 있습니다.

2. 동적 배열

2-1 특징

• 정적 배열로 만들어진 자료구조 입니다.
• 정적 배열은 크기가 고정되어 할당된 메모리에 공간이 더이상 없으면 값을 추가할 수 없지만, 동적 배열은 메모리에 공간이 꽉 찰 경우 값을 추가하기 위해 더 큰 메모리가 있는 곳으로 이사를 가서 공간을 확보합니다. (Doubling)

2-2 장점

• 정적 배열과 마찬가지로 배열 안에 있는 원소에 한 번에 접근(O(1)) (임의접근)할 수 있습니다.
• 또한 값을 추가하거나 삭제하는 것이 가능하기 때문에 파이썬에서 리스트 라는 (추상)자료구조를 만들 때 동적배열을 사용합니다.

2-3 파이썬 List

• 파이썬에서 리스트는 동적 배열로 구현된 대표적인 자료형입니다.
• 동적배열(메모리 크기 제한X, 임의접근) + 타입제한X

2-4 시간 복잡도

연산	시간 복잡도
접근	O(1)
탐색	O(n)
삽입	맨 앞: O(n) 임의: O(n) 맨 뒤: O(1)
삭제	맨 앞: O(n) 임의: O(n) 맨 뒤: O(1)

• 접근 은 주소만 알면 한 번에 접근 가능하므로 O(1)이다.
• 탐색 은 배열 안에 원소들이 정렬되어 있지 않기 때문에 선형탐색(일일이 하나씩 확인하는 알고리즘)으로 탐색해야 한다. O(n)
• 삽입 은 맨 앞의 경우 기존에 원소들을 뒤로 한 칸씩 옮겨야해서 O(n), 임의의 경우도 최악의 경우(맨 앞에서 두번째) O(n-1)이므로 O(n), 맨 뒤는 O(1)
  (삽입의 경우 배열의 메모리에 공간이 없는 경우 새로운 공간에 값을 옮겨야 해서 O(n)이 추가되어야 한다고 생각할 수 있지만 이는 자주 일어나는 일은 아니기 때문에 최악의 경우가 아닌 분할 상환 분석으로 시간 복잡도를 계산할 것이므로 보통 고려하지 않는다.) (분할 상환 분석이란 말은 메모리가 꽉차서 새롭게 공간에 모두 옮기는 일이 자주 일어나는 것이 아니라 n번 추가할 때 1번 옮기는 일이 일어나기 때문에 O(n)/n => O(1)으로 시간 복잡도를 계산한다는 개념이다.)
• 삭제 는 삽입과 비슷하다. 다른 점은 뒤로 한 칸씩 옮기는게 아니라 앞으로 한 칸씩 옮긴다는 것이다.