배열

배열

C에서의 배열은

int numArray[4];  

numArray[0] = 2;
numArray[1] = 3;
numArray[2] = 5;
numArray[3] = 7;

이렇게 배열을 선언할 때 크기를 정한다.
메모리의 연속된 공간에 정수값이 저장되게 된다.
2, 3, 5, 7이 연속적으로 저장되어 있는 것이다.

파이썬에서의 배열은 각 요소들이 연속적으로 저장되어 있지 않을 수 있다.

num_list = [2, 3, 5, 7]

위의 경우에서 각각의 요소를 가리키는 레퍼런스가 4개 저장된다.
그러면 각각의 레퍼런스가 2, 3, 5, 7을 가리키게 된다.
그래서 파이썬의 배열에는 값을 직접 저장하는게 아니고 레퍼런스를 저장하는 것이기 때문에 값들의 크기가 상관이 없고 여러 데이터타입을 같이 저장할 수 있다.

배열 인덱스

int numArray[4];  

numArray[0] = 2;
numArray[1] = 3;
numArray[2] = 5;
numArray[3] = 7;

c에서 정수는 4바이트이므로 총 16바이트의 연속된 공간을 예약한다.

배열에 데이터를 저장할 때는
만약 공간의 시작 주소가 100이라면 0번 인덱스는 100부터 103까지를 쓰게된다.
1번 인덱스는 104부터 107까지 쓰게 된다.

배열에 저장된 데이터를 가져올 때는
마찬가지로 인덱스를 사용해 printf("%d", numArray[0]); 이렇게 가져오면 된다.
내부적으로 numArray는 배열이 시작되는 주소를 가리키고 있다.
인덱스를 가져오려면 시작주소 + 데이터의 크기 * 인덱스 를 한다.
시작주소가 100이고 2번 인덱스를 가져오려면 100 + 4 * 2를 하면 2번 인덱스의 주소를 구할 수 있다.

이렇게 배열의 인덱스를 가져오거나 저장할 때 필요한 주소는 계산으로 알 수 있고 RAM은 임의접근이기 때문에 O(1)으로 접근 가능하기 때문에 빠르고 효율적이다.
주소만 알고있으면 한번에 접근할 수 있는 RAM의 구조를 잘 활용하는 자료구조이다.

배열 탐색

접근은 인덱스를 통해 값을 찾는 것이고 탐색은 특정 조건을 만족하는 값을 찾는 것이다.
탐색은 배열의 모든 값을 모두 확인해야 하기 떄문에 O(n)만큼 걸린다.

정적 배열과 동적 배열

배열은 정적 배열과 동적 배열로 나뉜다.
정적 배열은 처음 정의할 때 크기를 정하고 그 이상 값을 추가할 수 없다.
동적 배열은 값이 다 차도 계속해서 값을 추가할 수 있다.
보통 그냥 배열이라고 하면 정적 배열을 말하는 것이다.

정적 배열

배열을 만들 때 데이터타입과 크기를 미리 지정해야 한다.
정수 5개를 담을 배열이 다 차게 되었을 때 또 정수를 추가로 담고 싶다면 정수 6개 크기의 배열을 만들어 5개를 복사하고 추가하면 된다.

동적 배열

상황에 맞게 크기가 바뀐다.
예약한 공간이 꽉 찼을 때 값을 추가하려고 하면 더 큰 메모리 공간을 확보하고 기존의 데이터를 복사한다.
메모리 공간을 확보할 때는 보통 2배씩 늘려주게 된다. 이것을 더블링이라 한다.
초기값을 작게 잡아 배열을 생성하고 필요 할 때마다 늘려주고 복사하고 다시 공간이 다 차면 같은 과정을 계속 반복한다.

결국 동적 배열도 정적 배열로 만들어진 자료 구조이고 정적 배열의 크기를 상황에 맞게 조절한다.

사용자는 내부적으로 사용되고 있는 배열의 크기를 모른다.
데이터를 5개를 저장했더라도 내부적으로는 7개 짜리 배열일 수도 있다.
len()함수를 사용해 리스트의 길이를 출력하면 실제 배열의 크기인 7이 아니라 값을 저장해 놓은 만큼의 공간인 5가 출력되게 된다.
파이썬은 값을 저장해 놓은 공간에만 접근할 수 있도록 처리하고 만약 내부적으론 존재하지만 아직 값으로 채워지지 않은 6번째 인덱스를 접근하면 에러가 나게 된다.

동적 배열 추가 연산

배열의 가장 끝에 새로운 값을 추가하는 것을 추가 연산(append operation)이라 한다.

추가 연산을 할 때 정적 배열의 남는 공간이 있을 때와 없을 때 두 가지 경우가 있다.

남는 공간이 있을 때는 비어있는 공간에 그냥 값을 추가하면 되고 시간 복잡도는 O(1)이다.

남는 공간이 없을 때는 현재 배열보다 2배 더 큰 메모리 공간을 예약하고 기존의 값을 모두 복사한다. 그리고 새로운 값을 추가한다.
기존의 값을 새로운 공간에 복사하는 것은 O(n)만큼 걸린다.
새로운 값을 추가하는 것은 O(1)만큼 걸리니 총 O(n)만큼 걸리는 것이다.

즉, 동적 배열에 추가 연산을 하는 것은 최고의 경우에 O(1), 최악의 경우에 O(n)이 걸린다.
시간 복잡도는 보수적으로 생각해 보통 최악의 경우를 말하므로 O(n)이라고 볼 수 있다.
하지만 동적 배열에서 더블링이 일어나는 일은 어쩌다 한 번이고 이로 인해 시간 복잡도는 O(n)이라고 하는 것은 지나치게 비관적이고 정확하지도 않기 때문에 이런 경우에는 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 시간 복잡도를 계산할 수 있다. 이것을 분할 상환 분석이라 하고 이 방식에서의 시간 복잡도는 O(1)이 된다.

분할 상환 분석

같은 동작을 n번 했을 때 드는 시간이 x일 때 동작을 한 번 하는 데 걸린 시간은 x/n이다.
즉, 시간 복잡도를 최악의 경우가 아니라 평균을 내서 구한다.

동적 배열 삽입 연산

배열의 아무 위치에 새로운 데이터를 넣는 것을 삽입 연산(insert operation)이라 한다.

삽입 연산을 할 때 정적 배열의 남는 공간이 있을 때와 없을 때 두 가지 경우가 있다.

남는 공간이 있을 때는 삽입하고자 하는 위치부터 이후의 모든 인덱스들을 한칸씩 뒤로 민다.
그리고 생긴 공간에 데이터를 넣는다.
이 경우의 최악의 경우는 0번 인덱스에 삽입하는 경우이니 O(n)이다.

남는 공간이 없을 때는 새로운 공간을 할당해 기존 데이터를 모두 복사한다.
그리고 남는 공간이 있을 때와 마찬가지의 작업을 한다.
이 경우의 시간 복잡도는 O(n)이다.

그래서 삽입 연산의 시간 복잡도는 O(n)이다.

동적 배열 삭제 연산

삭제 연산은 삭제하고 싶은 데이터 뒤에 있는 모든 데이터 요소들을 한 칸씩 앞으로 밀어서 저장 하면 된다.
그리고 동적 배열에서 접근할 수 있는 인덱스 범위도 1을 줄여준다.

최악의 경우는 맨 앞의 데이터를 지우는 경우고 O(n)만큼 걸린다.
최적의 경우는 맨 뒤의 데이터를 지우는 경우고 O(1)만큼 걸린다.

동적 배열 크기 줄이기

크기를 줄일 때는 내부 배열의 사용 비율이 특정 값 이하로 떨어질 때이다.
비율이 1/3이라면 기존의 크기가 9인 배열에서 데이터를 삭제해 값이 3개 이하가 되면 배열 크기를 3으로 줄인다. 이 비율은 개발자나 언어에 따라 다르다.

정적 배열의 크기는 고정되어 있고 크기를 줄이려면 크기를 줄인 새 배열에 모두 복사해서 넣어야 한다. 맨 뒤의 데이터를 삭제하는건 O(1)만큼 걸리지만 데이터를 모두 복사해야 하기 때문에 O(n)만큼 걸린다.
하지만 내부 배열의 크기가 줄어드는 건 드문 경우이고 분할 상환 분석을 적용하면 O(1)이 걸린다고 보면 된다.

정적 배열에 삽입과 삭제가 안되는 이유

정적 배열[1, 2, 3, 4]가 있을 때 1번 인덱스인 2를 삭제하려고 None이나 Null을 넣게되면 데이터타입이 동일하지 않기 때문에 에러가 난다.
2번 인덱스의 데이터를 1번 인덱스에 넣고 3번 인덱스의 데이터를 2번 인덱스에 넣어서 [1, 3, 4, 4]이런식으로 밖에 만들지 못해서 자연스럽게 삭제할 수가 없다.

동적 배열[1, 2, 3, 4]가 있을 때 마찬가지로 1번 인덱스를 삭제하려면[1, 3, 4, 4]이렇게 만든다. 그리고 파이썬 내부적으로 개발자가 접근할 수 있는 범위를 인덱스0 ~ 2까지로 만들어 버린다. 그러면 실제로 인덱스3에 값이 있든 없든 개발자는 접근을 할 수가 없고 실질적으로 삭제됐다고 할 수 있다.