[파이썬] 자주쓰이는 파이썬 자료구조 & 메소드 시간복잡도

list

• 순서가 있는 수정가능한 객체의 집합.
• 수정, 삭제, 추가가 가능합니다.
• list 는 [] 대괄호로 선언되어지며, 내부 원소는 ,로 구분됩니다.

import copy

## List init ##
list = []
list = list()

## Append ## -- O(1)
list.append(3)
list.append(5)

## Extend ## -- O(k)
list.extend([8,7,4,1,2,6])

## Delete ## -- O(n)
del list[1]
list.remove(1)

## Sort ## -- O(nlogn)
list.sort() #오름차순
list.sort(reverse=True) #내림차순
res = sorted(list)

## Pop ##
list.pop() #가장 끝 원소 pop -- O(1)
list.pop(0) #가장 첫 원소 pop -- O(k)

## Copy ##
list2 = copy.copy(list) #얕은 복사 -- O(n)
list2 = list
list2 = list[:]

list3 = copy.deepcopy(list) #깊은 복사 -- O(n)

## Get length ## -- O(n)
length = len(list)

 

set

• 중복이 없는 요소들의 집합.
• 수학적으로 두개의 집합 간 연산을 제공. (차집합, 합집합, 교집합) 
• set 는 {} 중괄호로 감싸서 사용되어지며, 내부 원소는 ,로 구분됩니다.

## set init ##
set1 = set() # 중괄호만으로는 생성하지 못함. -> dict 타입으로 동일하기때문
set2 = {1,2,3}

s_list = [1,2,3,4,5,5,2]
set3 = set(s_list) # 리스트로도 생성 가능 (중복 제거 & 순서 없음).

## Add ## -- O(1)
set1.add(3)
set1.add(5)

## Update ## -- O(k)
set1.update([8,7,4,1,2,6]) # 여러 데이터를 한번에 추가

## Containmet ## -- O(1)
if 4 in set1:
    print('Set containment is O(1), List/Tuple containment is O(N)')

## Remove & Discard ## -- O(1)
set1.remove(2) # 아이템이 없으면 KeyError 발생 -> Dict와 유사
set1.discard(10) # 없어도 에러발생x

## Sort ## -- O(nlogn)
res = sorted(set1) # 결과는 리스트값

## Pop ##
set1.pop() # random pop -- O(1)  -> set은 순서가 없기 때문에 랜덤 pop

## Copy ##
copy_set1 = set1.copy() #얕은 복사 -- O(n)
copy_set2 = set(set1)

## Union ## -- O(len(s1) + len(s2)) -> 합집합
s1 = {1,2,3,4}
s2 = {2,3,4,5,6}
union_set1 = s1 | s2
union_set2 = s1.union(s2)

## Intersection ## -- O(len(s1) + len(s2)) -> 교집합
inter_set1 = s1 & s2
inter_set2 = s1.intersection(s2)

## Difference ## -- O(len(s1) + len(s2)) -> 차집합
diff_set1 = s1 - s2
diff_set2 = s1.difference(s2)

## Symmetric difference ## -- O(len(s1) + len(s2)) -> 대칭차집합
symm_set1 = s1 ^ s2
symm_set2 = s1.symmetric_difference(s2)

dictionary

• 파이썬의 해시테이블(key, value) 자료구조.
• set과 마찬가지로 순서가 없는 집합
• dict 는 {} 중괄호로 사용되어지며, 내부 원소는 ' : ' (키 : 값) 와 ' , ' 로 구분됩니다. 
• <codeblock TO BE CONTINUE>

collections.deque

• 양방향 큐.
• 알고리즘과 같은 문제에서 유용하게 사용되는 collections의 자료구조 중 하나이다.
• deque() 로 선언하여 사용할 수 있다.
• <codeblock TO BE CONTINUE>

ref

https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt