[코테 재활훈련] 자료구조 별 알고리즘 - List(Array list)

파이썬 코딩 테스트 강의

자료구조 2강 - 자료구조와 메모리 이해하기

• 예시에서 Array에 int형 변수가 들어가기 때문에 각 4byte를 차지함
• 각 요소는 가장 작은 주소값이 대표 주소값

• 값과 주소값을 저장
• 값과 주소값으로 이루어진 구조체 = Node

코딩테스트를 위한 시간 복잡도

O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)

<aside> 💡 보통 10^8을 넘어가면 안된다

</aside>

자료구조 - List

정적 배열(Array)의 특성

1. 고정된 저장 공간
2. 순차적인 데이터 저장

배열은 선언시 size를 정하여 해당 size만큼 연속된 메모리를 할당 받아 data를 연속적/순차적으로 저장하는 자료구조 입니다

int arr[5] = {3, 7, 4, 2, 6}

위의 예시에서는 배열의 size를 5로 정했기 때문에 int형 데이터 4byte 5개를 저장할 메모리 공간인 20Byte를 미리 할당 받습니다. 이처럼 고정된 size를 갖게 되기 때문에 static array라고 부르기도 합니다.

4byte(int형 데이터) * 5(size) = 20byte

또한 배열의 데이터를 연속적이고 순차적으로 메모리에 저장합니다

Random access

배열변수는 자신이 할당받은 첫번째 주소값을 가리키고, 첫 주소값을 알고 있다면 어떠한 index에도 즉시 접근이 가능하다. 이를 Randome access또는 Direct access라고 하고 시간복잡도 O(1)을 가진다.

정적 배열의 한계

데이터 개수가 정해져있는 경우 static 배열을 사용하는게 효율적이지만 선언시 정한 사이즈보다 더 많은 데이터를 저장해야 하는 경우 공간이 남지 않아 문제가 발생 할 수 있다. 그렇다고 큰 사이즈의 배열을 선언하게 되면 메모리가 비효율적으로 사용될 수 있습니다. 이를 해결할 수 있는것이 바로 dynamic array 입니다.

Dynamic Array

💡 선언 이후에 size를 변경할 수 없는 정적 배열과 다르게 동적배열은 size를 늘릴 수 있습니다.

>

동적 배열은 배열의 크기를 Resizing할 수 있는 배열입니다. 할당된 사이즈를 초과하기 전까지는 기존과 같이 데이터를 저장하다가 size를 초과하게되면 일반적으로 2배 큰 크기로 resize(Doubling)한 배열을 새로 선언하고 그곳으로 모든 데이터를 옮깁니다(O(n)).

 

💡 Python의 List 자료형은 C언어로 구현된 Dynamic Array이다 사이즈는 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, … 순서로 커진다

 

Python에서는 list자료형이 이미 dynamic array로 이미 잘 구현되어있기 때문에 직접 구현할 필요는 없지만 list의 연산들과 그들의 시간복잡도를 익혀야 할 것이다.

Dynamic Array의 연산들과 시간복잡도

• 선언 및 초기화 → O(n)
• 접근 및 수정 → O(1)
• append → O(1) 사이즈를 초과한 경우만 → O(n)
• pop() 마지막 데이터를 삭제 → O(1)
• insert(1,10) 1번 인덱스에 10을 넣기 → O(n)
• 중간에 있는 요소 삭제 → O(n)

2. 접근 방법

 

(번외) Python list의 sort(), sorted()의 시간 복잡도

• Timsort 알고리즘 사용(Timsort 알고리즘에 대하여 : https://d2.naver.com/helloworld/0315536)
• 평균 or 최악 O(nlogn)을 보장

 

다양한 정렬 알고리즘의 시간 복잡도

출처 :&nbsp;https://d2.naver.com/helloworld/0315536