🤖 옌지니어의 IT 기록 🤖

배열

인덱스와 값을 일대일 대응해 관리하는 자료구조

• 데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응
• 어떤 위치에 있는 데이터든 한 번에 접근 가능 → 임의 접근 (random access)

배열을 선언하는 방법

# 1. 일반적인 방법
arr = [0,0,0,0,0,0]
arr = [0] * 6

# 2. 리스트 생성자를 사용하는 방법
arr = list(range(6))			# [0,1,2,3,4,5]

# 3. 리스트 컴프리헨션을 활용하는 방법
arr = [0 for _ in range(6)]		# [0,0,0,0,0,0]

※ 파이썬의 경우 배열 대신 리스트를 사용 ※

배열과 차원

• 배열은 2차원, 3차원과 같이 다차원 배열로도 사용
• 컴퓨터 메모리 구조는 1차원이므로 다차원 배열도 1차원 공간에 저장
• 배열은 차원과 무관하게 메모리에 연속 할당

1차원 배열

• 가장 간단한 배열 형태
• 배열의 모습 = 메모리에 할당된 실제 배열의 모습

2차원 배열

• 1차원 배열을 확장한 것

# 2차원 배열을 리스트로 표현
arr = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]

# 저장된 값 출력
print(arr[2][3])

# 저장된 값을 변경
arr[2][3] = 15

# 리스트 컴프리헨션을 활용
arr = [[i]*4 for i in range(3)]

배열 연산의 시간 복잡도

• 배열은 임의 접근이라는 방법으로 모든 위치에 있는 데이터에 단 한 번에 접근 가능
• 데이터에 접근하기 위한 시간복잡도는 O(1)

배열에 데이터를 추가하는 경우

(1) 맨 뒤에 삽입할 경우

• 다른 데이터 위치에 영향 X
• 시간복잡도 = O(1)

(2) 맨 앞에 삽입할 경우

• 기존 데이터들을 뒤로 한 칸씩 미는 연산 필요
• 시간복잡도 = O(N)

(3) 중간에 삽입할 경우

• 현재 삽입한 데이터 뒤에 있는 데이터 개수만큼 미는 연산 필요
• 시간복잡도 = O(N)

배열을 선택할 때 고려할 점

• 할당할 수 있는 메모리 크기 확인
  • 표현하려는 데이터가 너무 많으면 런타임에서 배열 할당 실패
  • 보통 정수형 1차원 배열은 1000만개, 2차원 배열은 3000*3000 크기가 최대
• 중간에 데이터 삽입이 많은지 확인
  • 배열은 선형 자료구조이므로 빈번하게 삽입하면 시간 초과 발생