코테용 최소 필요 자료구조 개괄

https://bit.ly/3a926Zp

1. 스택

• LIFO(Last In First Out)구조 : 가장 마지막에 들어간 원소가 가장 먼저 나옴
• 리스트를 사용해 구현
• 알 수 있는 값은 맨 위의 값 : 맨 위에 새 값을 쌓아 올리거나 맨 위에 있는 값을 빼거나 삽입/삭제
• 삽입 : push 연산 / 삭제 : pop 연산 / 맨위의 값을 보는 연산 : top 연산
• 파이썬에 따로 라이브러리가 있진 않고 리스트를 스택처럼 사용
• O(1)

 

2. 큐

• FIFO(First In First Out) : 가장 먼저 들어갔던 값이 가장 먼저 나온다

2.1 덱

• 앞 뒤로 모두 출입 가능
• 파이썬에서 기본으로 제공해주는 collections 모듈의 deque 클래스 사용 : 양방향 연결리스트로 구현되어 있어서 리스트보다 출입 연산에 효율적 : deque가 pop에 O(1)복잡도 가진다면 이라면 list는 pop에 O(n)의 복잡도 가짐
• Deque : Double Ended Queue
• append(x) : deque의 오른쪽에 x  더함
• appendleft(x) : deque의 왼쪽에 x 더함
• pop() : deque의 오른쪽에서 요소 꺼냄
• popleft(): deque의 왼쪽에서 요소 꺼냄
  
  

2.2 우선순위 큐

• 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
• 만드는 법
  • 리스트를 이용하는 법 : 삽입시간 - O(1), 삭제시간 - O(N)
  • 힙(heap) 이용하는 법 : 삽입시간 - O(logN), 삭제시간- O(logN)
• 파이썬에서 기본으로 제공해주는 heapq라이브러리 사용 : 요소를 push,pop 할때마다 자동으로 정렬
• 파이썬에서 제공하는 heap 라이브러리는 값이 낮은 순(우선순위가 높음)으로 먼저 뽑아내는 최소힙
• heapify() : 기존의 배열을  heap 구조로 만듦
• heappush(배열이름, 요소) : heap(배열)에 요소를 추가
• heappop(배열이름) : heap(배열)에서 요소를 제거