[Week02] 알고리즘 - 큐 (feat. python)

모듈

: 함수,변수 또는 클래스들을 모아놓은 파일 - 파일명이 모듈명이 된다. 

 

 if __name__ == "__main__" 의 의미

👉 python은 c나 java와 다르게 스크립트 기반 인터프리터 언어로 특별히 시작 지점이 명시가 되어있지 않은 언어이다. 

그래서 특별히 변수를 할당하여 현재 스트립트의 시작점이 어디인지 판단하는데 그 변수로서 이용하는 것이 __name__ 이다. 

 

 파일 실행시에는 __name__ 변수에 "__main__"을 저장하게 되지만 해당 모듈이 import 될 경우 변수에 "모듈명"이 들어가기때문에

if __name__ == "__main__" 문은 실행되지않는다. 

 

__init__의 의미

👉 생성자의 의미 ( 여기서 self는 인스턴스 자신, 메소드의 임의의 인수 정도의 의미를 가진다. )

class의 인스턴스를 생성할때 초기화를 위한 함수. 인스턴스화를 실시할떄 반드시 처음에 호출되는 특수한 함수이다. 

 

class test:
	def __init__(self,x) :
		self.x = x
    
	def test_function(self) : #메소드
		perint(self.x)

 

ADT 추상적 자료형

: 물리적으로 존재하는 것이 아니라 일종의 규칙, 배열위에 어떤 규칙을 설정할지 정하는 것

• 스택 stack : 선입후출
• 큐 queque : 선입선출

 

스택

• 파이썬은 따로 스택 모듈이 존재하지않는다. 보통 덱(deque) 라이브러리를 import해서 스택 대신 사용가능한다.
• 리스트 함수를 사용해서 간단하게 스택을 사용할수있다. 

큐

큐 동작 

enqueue / dequeue

 

큐 리스트 구현하기

1. 리스트를 큐 방식으로 구현하면 head변수와 tail 변수에 index정보를 담는다. 
2. 데이터를 추출하면(dequeue) 데이터가 당겨지는 것이 아니라 head 변수가 뒤로 넘어간다. 
3. 추가와 추출을 반복하다 보면 head와 tail이 뒤로 밀려 리스트가 가득 차 앞쪽에 빈공간(쓰레기 값)이 많은데도 더 이상 데이터를 넣을 수 없게 된다. 
4. 그것을 방지하기 위해 원형 리스트를 이용한다.
5. 물리적이 아닌 관념적 원형 list이며 리스트 index가 마지막 index에 1이 더해지면 다시 0번지로 돌아오도록 점유한다. - 점점 오른쪽으로 이동하며 확장 (deque의 .rotate()함수 사용 가능)

원형 큐는 알고리즘 뿐 아니라 실무에서 많이 사용되는 데이터 구조이다. 

원형 큐의 특징은 맥시멈 사이즈가 있기 때문에 오버플로어가 생길 수 있다. 

 

✅  덱 (double ended queue) 모듈

양쪽 끝에서 삽입과 삭제가 가능하다.

원칙적으로는 제일 앞/뒤가 아닌 나머지 원소들의 확인, 변경이 불가능한데 덱에서는 index접근이 가능하다.

양쪽으로 확장이 가능하기 때문에 구현시 시작 지점을 중간에 두어야한다. 

popleft() - 첫번째 데이터를 제거

eppendleft() - 데이터를 맨 앞에 삽입

 

- 큐 (Queue) 모듈

덱보다 느림, 인덱스 값으로 값을 알수없다.

: 주로 멀티 쓰레딩 환경에서 사용되며, 내부적으로 라킹(locking)을 지원하여 여러 개의 쓰레드가 동시에 데이터를 추가하거나 삭제할 수 있다.

덱과 달리 방향성이 없기 때문에 데이터를 추가와 삭제가 하나의 메소드로 처리됨.

put(x) - 데이터 추가

get( ) - 데이터 삭제

우선순위 큐

: pop할떄 가장 먼저 들어온 원소 대신 우선순의가 가장 놓은 원소가 나오는 큐 기능 - 힙 구조를 이용해 빠르게 연산이 가능하다. 

1.  원소추가 O(logN)
2. 우선순위가 가장 높은 원소의 확인 O(1)
3. 우선순위가 가장 높은 워소의 제거 O(logN)

힙

이진 트리 - 이진검색트리(BST)와 달리 늘 균형이 잘 맞는 이진트리

최소힙 / 최대힙

• 삽입 : 원래 순서대로 삽입(맨위-오른쪽-왼쪽)후에 조건에 위배된다면 위배되지않을때까지 자리 변경
• 추출 : 루트에 들어있는 값이 최소/최대값 - 최소힙에서는 최솟값, 최대힙에서는 최대값을 찾을 수있고 다른 값을 찾는 것은 트리를 전부 뒤지는게 아닌 이상 확인이 불가능하다. 
• 삭제 : 루트값을 삭제할때 트리 구조가 깨지지않게 가장 마지막 자리수(자식이 없는)와 루트값을 바꾼후 삭제한다. 그 후 삽입에서와 동일하게 트리구조가 위배되지않게 내부적으로 자리를 변경해준다. 

x번지의 왼쪽 자식 index : 2x

x번지의 오른쪽 자식 index : 2x + 1

x번지의 부모 index : x/2

 

이진검색트리는 왜 힙처럼 배열로 나타낼 수 없는 지 생각해보기

 

 

✅  힙 (heapq) 모듈

heapq.heappush(heap, item) : item을 heap list 에 추가

heapq.heappop(heap) : heap list 에서 가장 작은 원소를 pop. 비어 있는 경우 IndexError가 호출됨. 

heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 O(N)

 

- 덱(queue) 모듈 PriorityQueue 클래스 

내부적으로 heap모듈을 사용한다.

생성자

que = PriorityQueue()

que = PriorityQueue(maxsize=8) : 최대크기 지정생정자

 

 

열코 🔥🔥