배열
인덱스와 값을 일대일 대응해 관리하는 자료구조이다.
- 데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응하므로 어떤 위치에 있는 데이터든 한 번에 접근할 수 있다.
- 따라서 데이터가 어디에 있는지만 알면 빠르게 탐색할 수 있다.
배열 선언
일반적인 선언
basic_arr1 = [0, 0, 0, 0, 0, 0]
print(basic_arr1) # [0, 0, 0, 0, 0, 0]
basic_arr2 = [0] * 6
print(basic_arr2) # [0, 0, 0, 0, 0, 0]리스트 생성자를 사용하는 방법
numbers = list(range(6))
print(numbers) # [0, 1, 2, 3, 4, 5]리스트 컴프리헨션을 활용하는 방법
zeros = [0 for _ in range(6)]
print(zeros) # [0, 0, 0, 0, 0, 0]코딩테스트에서 기본값을 하나의 숫자로 선언할 때에는 일반적인 선언의
basic_arr2 = [0] * 6처럼 파이썬 곱셈 연산자 사용하여 선언하는게 더 권장된다.
배열과 차원
1차원 배열
가장 간단한 배열 형태이다.
배열이라 했을 때 가장 먼저 생각나는 형태가 1차원 배열이다.
2차원 배열
1차원 배열을 확장한 것이 2차원 배열이다.
two_d_arr = [[1, 2, 3, 4], [2, 4, 6, 8], [1, 3, 5, 7]]
print(two_d_arr) # [[1, 2, 3, 4], [2, 4, 6, 8], [1, 3, 5, 7]]
# two_d_arr[2][3]에 저장된 값을 9로 변경
two_d_arr[2][1] = 9
print(two_d_arr[2][1]) # 9
# 리스트 컴프리헨션을 활용하여 선언
# 크기가 3 * 4 리스트
two_d_arr = [[i] * 4 for i in range(3)]
print(two_d_arr) # [[0, 0, 0, 0], [1, 1, 1, 1], [2, 2, 2, 2]]배열의 효율
배열 연산의 시간 복잡도
배열은 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 한 번에 접근할 수 있다.
따라서 데이터에 접근하기 위한 시간 복잡도는 이다.
삽입, 삭제의 경우는 까지도 나올 수 있다.
맨 뒤의 데이터
맨 뒤에 삽입, 삭제할 때는 맨 뒤의 인덱스에 임의 접근을 바로 할 수 있으며 데이터를 삽입해도 다른 데이터 위치에 영향을 주지 않기 때문에 시간 복잡도는 이다.
맨 앞의 데이터
맨 앞에 삽일, 삭제할 때는 기존 데이터들을 뒤로 한 칸씩 미는 작업이 추가로 필요하므로 시간 복잡도는 이다.
중간의 데이터
중간에 삽입, 삭제할 때도 삽입하는 위치 이후의 기존 데이터들을 뒤로 한 칸씩 미는 작업이 추가로 필요하므로 시간 복잡도는 이다.
배열 선택 시 고려사항
1. 할당할 수 있는 메모리 크기를 확인해야 한다.
- 배열로 표현하려는 데이터가 너무 많으면 런타임에서 배열 할당에 실패할 수 있다.
- 보통 정수형 1차원 배열은 1,000만 개, 2차원 배열은 3,000 * 3,000 크기를 최대로 생각하자.
2. 중간에 데이터 삽입이 많은지 확인해야 한다.
- 배열은 선형 자료구조이기 때문에 중간이나 처음에 데이터를 빈번하게 삽입하면 시간 복잡도가 높아져 시간 초과가 발생할 수 있다.
