[2주차]5장 배열

5장 배열 

배열의 개념 

 

배열은 자료구조로서 데이터를 저장할 수 있는 모든 공간마다 인덱스와 일대일 대응한다. 

따라서 어떤 위치에 있는 데이터든 한 번에 접근할 수 있어서 인덱스만 알면 데이터를 빠르게 탐색할 수 있다. 

이런 접근 방식을 임의 접근(random access)라고 한다. 

 

배열 선언

1)배열 선언의 방법 

 

일반적인 방법

arr = [0, 0, 0, 0, 0, 0]
arr = [0] * 6
# 두 코드의 결과 값은 동일하다.

 

리스트 생성자를 사용하는 방법

arr = list(range(6)) # [0, 1, 2, 3, 4, 5]

 

리스트 컴프리헨션을 사용하는 방법 

arr = [ 0 for _ in range(6)) # [0, 0, 0, 0, 0, 0]

 

 

2)배열의 특징

• 배열은 인덱스가 0부터 시작한다. 
• 파이썬의 경우 배열을 지원하는 문법은 없고 대신 리스트 문법을 사용하면 된다. 
• 파이썬의 리스트는 동적으로 크기를 조절할 수 있도록 구현되어있고, 슬라이싱, 삽입, 삭제, 연결 등 연산을 사용할 수 있어서 편리하다. 

배열과 차원

배열은 2차원, 3차원 등 다차원 배열로 존재할 수 있다. 

하지만 컴퓨터 메모리는 1차원이다. 때문에 배열은 차원과 무관하게 메모리에 연속적으로 할당된다. 

 

1) 1차원 배열

만약 배열이 0번부터 10번까지 있다면 0번 배열에는 낮은 메모리 주소에서 시작하여 10번 배열까지는 오름차순으로 메모리 주소가 높아진다. 

 

2) 2차원 배열 

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

# 2차원 배열을  다음과 같이 출력할 수 있다. 
print(arr[2][3]) #12 출력

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

#변경된 값을 출력
print(arr[2][3]) # 15

 

리스트 컴프리헨션을 사용하면 다음과 같이 선언할 수 도 있다. 

# 크기가 3 * 4인 리스트를 선언하는 예시
arr = [[i] * 4 for i in rnage(3)] #[[0, 0, 0, 0], [1, 1, 1, 1], [2, 2, 2, 2]]

 

배열 연산의 시간 복잡도

배열은 임의 접근이라는 방식으로 접근함으로 모든 위치에 있는 데이터를 한번에 접근할 수 있다. 

따라서 데이터에 접근하기 위한 시간 복잡도는 O(1)이다. 

 

배열 데이터에 맨 앞에 다른 새로운 데이터를 추가한다면, 기존에 있던 데이터는 뒤로 한칸씩 밀어야 한다. 

따라서 이를 위한 연산이 필요한데, 이때 총 데이터의 개수가 N개라면 이를 위한 연산의 시간 복잡도는 O(N)이 된다. 

 

만약 배열의 데이터의 중간에 다른 데이터를 삽입할 경우 중간 이후에 있는 데이터를 뒤로 한칸씩 밀어야한다. 

중간 이후에 있는 데이터가 N개라면 이를 위한 연산의 시간 복잡도는 O(N)이 된다. 

 

== 배열은 특정한 경우에 따라서 데이터 추가나 삭제에 드는 비용이 많을 수 있다. 

 

배열을 선택할 때 고려할 점 

배열은 임의 접근이라는 특징으로 인해 인덱스를 통해 데이터로 바로 접근할 수 있어서 데이터에 빈번하게 접근하는 경우에 효율적이지만, 메모리 낭비가 발생할 수 있다. 따라서 다음과 같은 사항을 고려해야한다. 

 

1. 할당할 수 있는 메모리의 크기 확인(배열로 표현하고자 하는 데이터에 대한 메모리의 크기 확인)

2. 중간이나 맨 앞에 데이터 삽입이 빈번한가?(이럴 경우 시간복잡도가 높아짐)

 

(단, 현재 파이썬에서 리스트로 배열을 구현함으로써 배열 크기에 대한 고민은 하지 않아도 되고, 배열의 특성정도로만 이해하면 됨)

 

배열 구현을 위해 자주 사용하는 파이썬 리스트 기법

 

리스트에서 데이터 추가하기 

 

append() 메서드로 데이터 추가하기 

# 리스트의 맨 끝에 데이터 추가 
tmp_list = [1, 2, 3]
tmp_list.append(4) # [1, 2, 3, 4]

 

+연산자로 데이터 추가하기 

tmp_list = [1, 2, 3]
tmp_list = tmp_list + [4, 5]  # [1, 2, 3, 4, 5]

 

insert() 메서드로 데이터 추가하기 

tmp_list = [1, 2, 3, 4, 5]
tmp_list.insert(2, 9999) # [1, 2, 9999, 3, 4, 5]

 

리스트에서 데이터 삭제하기 

 

pop() 메서드로 특정 위치의 데이터 팝

tmp_list = [1, 2, 3, 4, 5]
popped_element = tmp_list.pop(2) # 3
print(tmp_list) # [1, 2, 4, 5]

 

remove() 메서드로 특정 데이터 삭제 

- 인수로 받은 값이 처음 등장하는 위치의 데이터를 삭제함 

tmp_list = [1, 2, 3, 2, 4, 5]
tmp_list.remove(2) # [1, 3, 2, 4, 5]

 

리스트 컴프리헨션으로 데이터에 특정 연산 적용

리스트에 제곱 연산 적용 예

numbers = [1, 2, 3, 4, 5]
squares = [num**2 for num in numbers] # [1, 4, 9, 16, 25] 이래도 nubers는 여전히 [1, 2, 3, 4, 5]임