[파이썬] 배열

🤔 배열

 

C 배열

 

크기가 고정되어 있다. (int numArray[4] 는 4칸의 공간을 미리 예약, 총 16byte)

같은 타입의 데이터만 담을 수 있다.

 

c 배열이 들어가는 방법

C 언어 자리 선정법 (연속적 저장)

Python 배열

 

python 배열이 들어가는 방법

 

주소를 알고있으면 배열에 접근하는데 걸리는 시간은 O(1)이라는 점이 굉장히 효율적이다.

 

🤔 배열탐색

 

배열안에서 어떤 값을 찾을 때 0번째 부터 순서대로 찾는 것을 선형 탐색이라고 한다.

배열의 첫번째에 찾는 값이 있을경우 빠르지만 없는 경우 O(n)의 시간이 걸리게 된다.

배열에 접근하는 것은 O(n)으로 빠를지언정 탐색을 하게 되면 O(n)의 시간이 걸리게 된다는 것이다.

 

🤔 정적 배열과 동적 배열

 

1. 정적 배열 : 크기 고정 (요소 제한)

5개를 담을 수 있는 배열에 새로웃 수를 집어넣을라고 한다면 정적인 배열 특성 때문에 배열을 처음에 6개를 담을 수 있도록 초기화 해야 한다. 이러한 현상을 방지하기 위해 너무 큰 공간을 할당하면 낭비되는 공간이 많아지게 된다.

 

2. 동적 배열 : 크기 유동적 (요소 계속 추가 가능)

상황에 따라 크기가 유동적으로 바뀐다. 기존에 있던 배열에서 새로운 숫자가 추가되면 새로운 상대적으로 큰 크기의 배열을 새로 만들게 되고 기존의 값들을 먼저 추가하고 새로운 값을 뒤에 추가하게 된다.

결국 정적 배열로 만들어진 자료구조이고 상황에 맞게 바뀐다는 것이다.

 

🤔 추가 연산 (append operation)

 

경우 1) 정적 배열 남는 공간 있을 때 : O(1) 그냥 추가만 하면 되므로..

경우 2) 정적 배열이 꽉 찼을 때

기존 배열 0번 인덱스에 접근해서 복사 후 새로운 배열 0번 인덱스에 접근해 붙여넣는 식으로 하나하나

복사하면 n번 반복된다. 따라서 O(n)이고 새로운 값을 추가하는 일은 O(1)만큼 시간이 걸리니

더해 O(n)만큼 걸린다.

 

🤔 분할 상환 분석 (Amortized Analysis)

 

같은 동작을 n번 했을 때 드는 시간이 x일 때 동작을 한 번 하는 데 걸린 시간은 x/n걸리게 된다.

 

x 번째 추가	배열 크기	새로운 배열에 요소 옮겨 저장하는데 걸리는 시간
1	1	0
2	2	1
3	4	2
4	4	0
5	8	4
6	8	0
7	8	0
8	8	0
9	16	8
...

 

크기가 1이었던 배열은 2, 3, 5, 9번째 수가 추가 될 때 배열의 크기를 늘리게 된다. 그럴 때마다 데이터를 옮겨야 하는데 이 때마다 1, 2, 4, 8 개씩 복사하고 붙여넣는다.

복사하고 붙여넣는 총 시간 비용은 8 + 4 + 2 + 1 이다.

일반화를 해서 수를 추가하는 것을 n번했다고 하고, 가장 마지막에 데이트를 m개 옮겨서 저장했다고 하자.

총 걸린 시간은 위와 같이 [m + m/2 + m/4 + ... + 1] 이 걸리게 된다.

늘어나는 것은 1 + 2 + 4 + ... + m/2 + m 순으로 늘어나지만 역순으로 한 것이다.

가장 마지막의 복사한 숫자의 개수가 m이면 새로이 생기는 배열들은 이런식으로 보여진다.

 

 

새로 생기는 배열들의 크기의 합은 절대 2m을 넘을 수 없다는 점이다.

예를 들어 가장 최근에 데이터를 옮겨 저장할 때 8이 걸렸다는 뜻은 현재 배열 안에 있는 데이터는 9~16개 사이라는 것을 위 방식으로 알 수 있다.

 

정리하면 연속으로 추가 연산을 n 번을 하면 데이터를 옮겨서 저장하는 데 걸리는 총 시간은  2n보다 작다는 것을 알 수 있다.

 

새로운 데이터를 저장하는 데 n의 시간이 들고 데이터를 옮겨 저장하는데 에는 2n보다 약간 적은 시간이 필요하다. 두 시간을 합치면 O(3n)의 시간 결국 O(n)이라고 할 수 있다.

하지만 이건 연속으로 n 번하는 데 걸리는 시간 복잡도이다.

1번하는 데 걸리는 시간은 O(n)/n 즉 O(1)이 걸린다.

 

무조건 분할 상환 분석을 한다고 꼭 시간 복잡도가 줄어드는 것은 아니다. 보통 줄어들지 않는다.

하지만 이렇게 해서 줄어든다면 이 분할 상환 분석을 한 시간 복잡도를 사용한다.

 

정확하게는 동적 배열의 추가(append) 연산은 최악의 경우 O(n)이 걸리지만, 분할 상환 분석을 하면 O(1)이 걸린다고 표현하는게 맞다.

 

🤔 삽입 연산 (insert operation)

 

경우1 ) 정적 배열 남는 공간 있을 때

연속되어 있는 배열 중간에 새로운 수를 저장하기 위해서는 중간 이후에 있는 인덱스들을 한칸씩 뒤로 미루게 된다. 그리고 빈공간에 새로운 수를 넣게 되는데 이 경우 시간복잡도, 그 중에서도 최악의 경우는 맨 앞에 넣는 경우인데 O(n)의 시간이 걸리게 된다. 정확히는 넣는 시간까지 O(n + 1)이다. (1은 제외)

 

경우2 ) 정적 배열이 찼을 때

새로운 배열을 만들게 되고 기존에 있던 수들을 복사하고 위의 방식과 같이 새로운 요소를 저장한다.

복사하는데 걸리는 시간 O(n), 위의 방식이 걸리는 시간 O(n + 1) 더해서 O(2n + 1)의 시간이 걸린다.

결국 O(n)이 걸린다.

 

둘다 O(n)이 걸린다. 따라서 삽입 연산에 걸리는 시간 복잡도는 O(n)이 걸린다.

 

🤔 삭제 연산 (delete operation)

 

미리 지정한 배열의 크기에서 추가로 공간을 필요로 하지 않으므로 최악의 경우 맨 앞을 요소를 뺀다고 했을 때 뒤의 요소들을 한 칸씩 앞으로 당기면 되므로 

삭제연산은 O(n)의 시간이 걸리고 맨 뒤의 요소를 삭제하게 된다면 O(1)이 걸린다.

 

🤔 내부 배열의 크기 줄이기

 

데이터가 10000개 있는 동적 배열에서 9900개의 요소를 지웠다면 100개 밖에 남지 않게 되고 결국 9900개의 공간이 낭비되게 된다. 공간을 더 효율적으로 사용하기 위해 내부 배열의 크기도 적절히 줄여서 공간을 쓴다.

이렇게 하기 위해서 만약 9개의 요소를 갖고 있던 배열에서 6개의 요소를 제거한다고 치면 공간의 효율성 때문에 새로운 3의 크기의 배열을 만들고 그곳에다 옮기면 된다. 줄일 때 크기를 꼭 1/3으로 줄여야 하는 것은 아니다. 1/2 1/4 등 개발자나 프로그래밍 언어에 따라 다르다.

 

맨 끝 데이터를 삭제할 때는 O(1)의 시간이 n번 반복된다. 작은 배열로 옮기기 위해서는 O(n)의 시간이 걸린다. 작은 배열로 안옮겨도 되지만 드물게 옮긴다.

 

따라서 분할 상환 분석을 적용하면 맨 끝 데이터 삭제 연산도 O(1)이 걸린다고 할 수 있다.

 

🤔 동적 배열에서의 삭제

 

정적인 배열에서는 numArray의 [2, 3, 5, 7]에서 2번째 요소인 3을 삭제를 할 수 없다. None, NuLL값은 정수형이 아니므로 없는 값을 넣을 수도 없다. 정적 배열은 3이 있는 자리에 5를 댕겨오는 식으로 해서 결국

[2, 5, 7, 7] 이렇게 되고 마지막에 있는 7을 지우는게 아니라 파이썬 내부적으로 개발자가 접근할 수 있는 인덱스 범위를 0 ~ 2로 만들어 버린다. 실질적으로 접근할 수 없기에 삭제되었다고 보는 것이다.