[Algorithm] 배열

* Python을 기준으로 합니다

---

배열 (Array)

- 개념

• 배열 : 값 또는 변수들의 집합으로 구성된 구조, index와 값을 일대일 대응해 관리
  
  • `list()`, `[ ]`로 선언되고, 크기 지정 없이 자동으로 resizing 되는 동적 구조
  • 배열 내의 값을 자주 조회하는 경우 효율적이지만, 메모리 크기가 제한되거나 삽입이 많은 경우 비효율적
    - 일반적으로 배열의 값 조회와 `append()`를 통한 배열 끝 삽입은 $O(1)$을 소모함
    - 배열의 첫 번째나 중간 위치 삽입은, 해당 위치로부터 모든 기존 값들을 뒤로 shift 하므로 $O(n)$이 소모됨
  • 배열의 차원
    - 1차원 배열 : 기본적인 배열 형태
    - 2차원 배열 : 1차원 배열의 확장, `arr = [[1,2],[3,4]]`와 같이 선언
• Time Complexity
  
  • $O(1)$ : 조회, `len()`, `append()`, `pop()`, `clear()`
  • $O(n)$ : 슬라이싱, 특정 값 제거 `pop(1)`, `in`을 통한 비교, 최대/최솟값, `extend()`, `reverse()`, `copy()`
  • $O(n \log n)$ : 정렬 `sort()` / `sorted(list)`

1차원 배열과 2차원 배열

- 구현

1. 데이터 추가

• `append()`를 통해 배열의 끝에 값을 추가

arr = [1,2,3]
arr.append(4) #[1,2,3,4]

2. 데이터 삽입

• `insert(위치, 값)`를 통해 배열의 특정 위치에 값을 추가

arr = [1,2,3]
arr.insert(2,4) #[1,2,4,3]

3. 데이터 삭제

• `pop()` : 배열 맨 끝의 값을 pop 하거나, 특정 index에 해당하는 값을 pop

arr = [1,2,3,4,5]
arr.pop(3) #4

• `remove(삭제할 값)` : 배열 내에서 처음 등장하는 해당 데이터를 삭제

arr = [1,2,3,2,1]
arr.remove(2)
print(arr) #[1,3,2,1]

4. 데이터 빈도

• `count()` : 해당 데이터의 개수를 반환

arr = [1,2,2,2,2,2,2,3]
arr.count(2) #6

5. 정렬

• `sort()` : 배열 정렬 / `reverse=True`를 주면 내림차순

arr = [5,2,3,4,1]

arr.sort()
print(arr) #[1,2,3,4,5]

arr.sort(reverse=True)
print(arr) #[5,4,3,2,1]