[1] 자료구조와 배열

자료구조 : 데이터가 모여 있는 구조로 컴퓨터에서 처리해야 하는 많은 데이터를 모아 효율적으로 관리하고 구조화하기 위해 사용된다.

 

✓ 시간 복잡도 O(n) : n의 크기에 따라 기하급수적으로 시간 복잡도가 늘어남.

   [시간 적게]  O(1) < O(𝑙𝑜𝑔𝑛logn) < O(n) < O(n𝑙𝑜𝑔𝑛logn) < O(𝑛2n2) < O(2𝑛2n) < O(n!)  [시간 많이]

---

배열(Array) : 묶음 단위로 값을  순차적으로 저장하는 선형 자료 구조로 배열에는 객체가 저장되며 객체 하나하나를 원소(element)라고 한다.

 

✓ 배열의 특징

•   추가적으로 소모되는 메모리 양이 거의 없다.
•   Cache hit rate(요청한 데이터를 캐시메모리에서 찾을 확률)가 높다. 
•   배열을 생성하려면 메모리 상에 연속한 구간을 할당해야 해서 할당에 제약이 걸릴 수 있다.

 

✓ 배열의 시간복잡도

1. 접근(access) : 인덱스에 해당하는 값 찾기

찾고자 하는 값의 인덱스를 알고 있으면 O(1)의 빠른 시간복잡도를 갖는다.

 

2. 검색(search) : 인덱스를 모를 때, 값 찾기

배열 전체를 반복문으로 돌아야하므로 O(n)의 시간복잡도를 갖는다.

 

3. 추가(add) : 배열의 가장 마지막 값 다음에 값을 삽입하기

배열의 크기를 알고 있으므로 O(1)의 시간복잡도를 갖는다.

단, 배열을 추가할 수 있는 빈공간이 존재해야 한다는 조건을 충족할 때만 가능하다.

 

4. 삽입(insert) : 인덱스에 해당 값을 삽입하기

추가가 아닌 삽입을 할 경우, 기존에 있던 데이터를 다음 칸으로 밀어내 빈 공간을 만들고 삽입해야 하므로 O(n)의 시간복잡도를 갖는다.

 

5. 제거(remove) : 인덱스에 해당하는 값 삭제하기

인덱스에 해당하는 값이 존재해야하며 해당 값(arr[i])을 삭제한 후의 빈 값을 다음 값(arr[i+1])으로 땡겨와야 하므로 반복문을 돌아야 한다. 따라서 O(n)의 시간복잡도를 갖는다. 

 

 

✓ 배열의 장/ 단점

•   장점 : 인덱스를 통해 접근하므로 검색이 빠르고 구현이 쉽다.
•   단점 : 배열의 크기는 생성할 때 정해야 하므로(크기 변경 불가, 새로운 배열을 만들어야 한다) 데이터의 수가 정확하지 않을 때 애매한 상황이 된다. 배열의 크기가 크면 메모리 낭비가, 크기가 작으면 데이터를 원하는만큼 담지 못한다. 

 

 

✓ 배열을 사용할 때

• 데이터의 개수가 확실하게 정해져 있을 때
• 검색 작업이 많고 삽입/삭제 작업이 적을 때

 

✓ 배열 구현 방법 : 리스트와 튜플

2022.04.05 - [Python/[re-Python] 파이썬 기본] - [re-Python Basic] 리스트, 딕셔너리, 집합

[re-Python Basic] 리스트, 딕셔너리, 집합

 

🍀 등가성(eqality)과 동일성(identity)

등가성 비교(==) vs 동일성 비교(is)
등가성 비교는 두 객체의 값이 같은지 비교하고 동일성 비교는 값과 식별 번호가 같은지 비교한다.