알고리즘 요점 정리 - 스택 큐 힙

입사 후 정신이 없어서 면접 준비를 할 때 작성한 요점 개념에 대한 글을 포스팅한다는게 깜박했다.
임시저장 게시물 부랴부랴 업로드해야겠다 !!!

 

 

 

 

 

목차

스택

큐

힙

 

 

---

 

스택  LIFO

데이터 간 순서를 약속하는 것이다.

 

마치 접시처럼, 먼저 쌓인 것이 가장 늦게 출력된다.

deque (맨 앞과 뒤에 데이터를 삽입 및 삭제할 수 있도록 하는 자료형) 양방향 자료형을 쓰는데, 이는 append나 pop이 압도적으로 빠르다.

• 추가는 append
• 접근은 [-1]
• 삭제는 pop()

 

---

큐 FIFO

병원 대기줄과 같이, 먼저 쌓인 것이 먼저 출력된다.

 

즉 들어가는 순서대로 나온다.

이 또한 deque를 사용한다. 뒤에서는 append와 pop을, 앞에서 넣을땐  appendleft 앞에서 꺼낼땐 popleft를 사용한다.

큐는 튜플과 함께 사용할 수 있다.

• 앞에서 추가는 appendleft
• 앞에서 꺼낼 땐 popleft
• 뒤에서 추가는 append
• 뒤에서 꺼낼땐 pop

 

 

---

힙

완전이진트리 형태로써, 가장작은 원소 혹은 가장 큰 원소를 찾아 문제를 해결할 때 용이한 방법이다.

 

최대힙의 경우, 트리 내 부모노드의 데이터는 자식 노드들의 데이터보다 크거나 같다.

 

항상 오른쪽부터 채워지며, 마지막 레벨을 제외하고 나머지는 모두 이진트리다.

만약 노드 개수가 n이면 높이는 logn이므로, n*logn의 시간복잡도가 소요된다.

 

heapq 라이브러리를 이용해서 주로 사용한다. 이는 최소힙을 만드는 라이브러리다.

 

• heapify : 힙으로 만들기
• heappop : 가장 작은 원소를 출력
• heappush : 원소를 넣는 역할