[알고리즘][왜이거써요?]list 와 deque, 분기를 잡자, 자주쓰는 list 함수

1. 이런 경우에는 list보다는 deque를 사용하는건 어떨까?

→ 첫번째 값을 넣고 뺴고를 자주 해야할 상황

첫번째 원소를 추가 삭제한다면 극명한 속도 차이가 발생

 

덱과는 다르게 python의 리스트는 fixed size memory blocks(array)로 구현되어 있습니다.

이름은 List여서 링크드 리스트처럼 보이지만 고정된 사이즈의 메모리를 갖는 array 형태입니다.

리스트의 마지막 원소를 삭제는 O(1)이지만, 아래 그림처럼 첫번째 원소를 삭제하면 삭제 후 모든 원소를 앞으로 이동시키기 때문에 시간 복잡도가 O(n)입니다. 

 

삽입, 삭제의 operation()이 앞, 뒤, 중간 등에서 발생한다면 list 보다는 deque 사용을 우선적으로 고려하는 것이 속도 측면에서는 훨씬 좋을 것

 

 

2. 분기(예를 들어, = 같은부분) 는 항상 유의하고 생각해 주어야한다 예외가 발생하기 마련

→ 반드시 잡아주자

 

3. 있는지 여부를 알고싶을땐, list 보다 set(집합) 을 사용하자

4. 자주 찾는 List 함수 

비어있는지 확인

	#if not st
        if len(st)==0:
            an.append(-1)

 

배열 뒤집기

list=[]

#원본은 안바뀜
list[::-1]

#원본 바뀜
list.reverse()

 

2차배열 sort

#첫번째 기준으로만 정렬
answer.sort(key=lambda x:(x[0]))

#[0] 기준으로만 역정렬
answer.sort(key=lambda x:(-x[0]))

#[0]으로 우선 정렬하고 그 안에서 [1]로 정렬
answer.sort(key=lambda x:(x[0],x[1]))