시간복잡도 분할 상환 분석(동적 배열의 추가 연산)

동적 배열의 추가(append) 연산 동적 배열의 추가 연산의 시간 복잡도를 계산해보자 다음과 같은 배열에 새로운 데이터를 추가한다고 하자 두 가지 경우에 대해서 생각해 볼 수 있다 1. 배열에 남는 공간이 있을 때 이 경우는 그냥 빈 공간에 데이터를 저장하면 되므로 시간 복잡도는 O(1)이다 2. 배열이 꽉 찼을 때 이 경우는 기존의 배열보다 큰 배열을 만들고 기존 배열에서 새로운 배열로 값을 다 복사해야 된다 기존 배열의 0번 인덱스에 접근해서 값을 복사하고 새 배열의 0번 인덱스에 접근해서 값을 붙여 넣고... 이미 있던 n개의 데이터를 복사해야 되므로 O(n)이 되고 새로운 데이터를 추가해야 되므로 O(1)이 되어 총 O(n+1) = O(n)이 된다 정리 배열에 남는 공간이 있을 때: O(1) 배..

리스트는 사실 배열?(3/3)

리스트 그렇다 파이썬 리스트는 사실 동적 배열이다 C의 배열을 이용해서 구현한 동적 배열이다 리스트를 하나 만들어 보았다 리스트는 동적 배열이므로 내부적으로는 C의 배열이 만들어져 있다 우리는 리스트에 마음대로 값을 추가할 수 있다 동적 배열이기 때문에 상황에 맞게 배열의 크기가 조절되기 때문이다 우리는 리스트 내부에 있는 배열의 크기를 모른다 현재 리스트에 담긴 데이터 수가 5개여도 내부적으로는 5개짜리 배열이 있을 수도 있고 6개짜리 배열이 있을 수도 있고 16개짜리 배열이 있을 수도 있다 현재 num 리스트에는 5개의 데이터가 저장되어 있다 리스트의 길이를 출력해보면 리스트의 길이는 5라고 나온다 실제 내부적으로 사용하고 있는 공간이 더 많을지라도 파이썬은 우리가 저장한 공간에 대해서만 알려준다 파..

리스트는 사실 배열?(2/3) - 정적 배열과 동적 배열

정적 배열 정적 배열은 크기가 고정되어 있는 배열이다 일반적으로 그냥 배열이라고 부르는 배열은 정적 배열이다 길이가 4인 배열에 값이 다 저장되어있는 상황 여기에 새로운 값 5를 넣고 싶으면 어떻게 해야 할까 길이가 5인 새로운 배열을 만들고 기존의 데이터들을 새로운 배열에 옮긴 뒤 5를 저장하면 된다 그런데 이는 너무 비효율적이다 그냥 배열 뒤에 넣으면 안 돼? 배열을 정의하게 되면 메모리에서 쓸 수 있는 공간을 찾아서 저장하려고 하는 데이터 타입과 저장하려는 데이터 수에 따라 연속적인 공간이 정해진다 우리는 배열 바로 뒷부분이 어떤 공간인지 모른다 사용해도 되는 공간인지 알 수 없기 때문에 배열 바로 뒤에 5를 추가하게 되면 위험하다 위험성을 예방하기 위해서 배열은 미리 공간을 고정해 놓는 것이다 그..

리스트는 사실 배열?(1/3) - 배열과의 차이점

리스트 파이썬 리스트는 사실 C의 배열을 이용해서 만들어졌다 이 이야기를 하기 전에 먼저 배열과 리스트의 차이부터 알아보자 배열과 리스트의 차이 배열은 크기가 고정되어 있으며 같은 타입의 데이터만 담을 수 있다 int형 배열을 만들고 배열에 값을 저장할 경우 데이터형의 크기만큼 메모리를 차지하며 값이 저장된다 배열은 값들이 실제 메모리에 저장되지만 리스트는 다르다 리스트는 값들이 아예 다른 곳에 저장되어 있을 수 있다 즉, 실제 값들이 연속적인 공간에 있을 수도 있고 아닐 수도 있다 리스트에는 실제 값들이 저장되어있는 것이 아니라 실제 값들에 대한 *레퍼런스가 저장되어 있는 것이다 그래서 리스트에는 다양한 타입의 값들을 저장하는 것이 가능한 것이다 레퍼런스란? 변수 x에 1을 저장했다고 하자 x = 1이..