파이썬 기본 자료구조

1) 리스트

 

- 동적배열 ( like C++'s vector() )

- .append()나 .pop(), 또 원하는 인덱스의 요소를 조회할때는 O(1)

- 그러나 맨 마지막 외 특정요소의 삭제,

  혹은 첫번째 요소의 추출 pop(0)의 경우 (이건 queue에서 지원하는 기본연산)

  O(n)의 시간복잡도가 소요됨.

  ==> 따라서 리스트에서 queue의 연산을 사용하는것은 대개 비효율적이고,

         이땐 deque와 같은 자료형을 사용하면 성능을 높일 수 있음.

 

- 지원하는 연산들 예시 :

 

* elem in a --> elem요소가 배열 a에 존재하는지 확인. / O(n)

* a.count(elem) --> elem 요소의 갯수를 리턴. / O(n)

* a.index(elem) --> elem 요소의 인덱스를 리턴. / O(n)

* del a[i] --> 배열 a의 i인덱스 요소를 삭제. / O(n) / 시간복잡도는 i에 따라 다른데 최악의 경우 O(n)이다.

* a.sort() --> Timsort를 이용한 정렬. / O(nlogn). 최선의 경우 O(n)에도 실행될 수 있다.

* min(a), max(a) -- > a 배열의 최솟값과 최댓값 구하기. / O(n) --> 전체를 선형탐색해야 최대, 최솟값을 구할 수 있음.

* a.reverse() --> 뒤집기. 리스트의 입력순서를 반대로 한다. / O(n)

* a.insert( idx, elem ) --> 배열 a의 idx번째 인덱스에 elem 요소를 삽입함

* 삭제 : [1] index로 삭제하기

               del a[1] --> 배열 a의 index 1 원소를 삭제

           [2] value로 삭제하기

               a.remove(n) --> 배열 a에서 원소 n을 삭제하기 

* a.pop(i) --> 배열 a에서 인덱스 i의 원소를 return한 후 삭제 진행.

 

 

 

 

2) 딕셔너리

 

- 해시할 수만 있다면 숫자 뿐 아니라 문자, 집합까지 불변객체 모두 키로 사용 가능.

- 해시테이블을 이용해 자료를 저장. --> 따라서 입력과 조회 모두 O(1)에 가능.

 

- 지원하는 연산들 예시 :

 

* len(a) / O(1)

* a[key] / O(1)

* a[key] = value / O(1)

* key in a / O(1)

* a.items() / --> 이렇게 하면 key, value 로 묶인 값들이 반환됨.

for k,v in a.items():
	print(k,v)
    
>>> 
key1 value1
key2 value2
key3 value3

* 삭제 : del a['key1'] 

 

 

 

 

 

 

[참고]

(1) < Counter 객체>

-> 아이템에 대한 개수를 계산해 딕셔너리로 리턴함.

-> import collections 해서 collections.Counter(a) 로 반환받아서 사용한다.

a = [1,2,3,4,5,5,6,6]
b = collecitons.Counter(a)
b
>> Counter({5:3, 6:2, 1:1 ,2:1, 3:1, 4:1})

-> 이렇게 key에는 item의 값이, value에는 item의 빈도수가 들어간 딕셔너리를 생성함.

-> 개수를 자동으로 계산해주기 때문에 매우 편리!

 

** Counter 객체에서 가장 빈도 높은 element 추출하는 방법

: most_common() 사용

# 가장 빈도가 높은 2개의 요소 추출하기

b.most_common(2)
>> [(5,3), (6,2)]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

* 내용 출처 :

책 <파이썬 알고리즘 인터뷰>