[TIL] 05/17 항해99 9일 차 - 큐(Queue), 문제풀이

 

들어가며

할게 너무 많은데 어제 늦게자는 바람에 하루종일 피곤해서 제대로 공부 못했다. 페이스 조절이 중요한데 자꾸 욕심부리게 된다.

어제도 그렇게까지 할 생각은 아니었는데... 낮 시간에 의미없이 보내는 시간들을 줄이는게 일찍잘 수 있는 방법이지 않을까 싶다. 

 

아무튼, 졸린눈을 부여잡고 오늘의 TIL은 큐에 대한 정리와 문제풀이를 하고자한다.

---

큐(Queue)

 

큐는 시퀀스의 한쪽 끝에는 엔티티를 추가하고, 다른 반대쪽 끝에는 제거할 수 있는 엔티티 컬렉션이다.

쉽게 말하면 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조로, 데이터의 입력과 출력 순서는 선입선출(FIFO, Fisrt In First Out)이다.

 

큐는 스택에 비해서는 상대적으로 쓰임새가 적다고 한다.

엥? 근데 왜이렇게 많이 나와요?라고 묻는다면 상대적으로 적을 뿐이지 데크(Deque)나 우선순위 큐(Priority Queue)같은 변형들은 여러 분야에서 아주아주 유용하게 쓰인다고 한다. 이외에도 너비 우선 탐색(BFS, Breadth-First Search)나 캐시등을 구현할 때도 널리 사용된다고 하니, 차차 배워가면서 이렇게 쓰이겠구나 정도로 알아두자.

 

파이썬은 리스트가 스택의 역할을 했듯이 큐의 모든 연산또한 지원하기 때문에 그대로 사용하는 것도 좋지만, 더 나은 성능을 원한다면 양방향 삽입, 삭제가 모두 O(1)에 가능한 데크를 사용하는 편이 가장 좋다.

 

 

큐가 사용되는 예시?

자료를 제공해주신 호균님에게 압도적 감사!

 

큐 구현해보기 - 연결리스트로 구현

class Node:
	def __init__(self, item, next):
    	self.item = item
        self.next = next
        

class MyQueue:
	def __init__(self):
    	self.top = None
        
    def push(self, value):
    	if not self.top:
        	self.top = Node(value, None)
            
        node = self.top
        
        while node.next:
        	node = node.next
        
        node.next = Node(value, None)
        
	def pop(self):
    	if not self.top:
        	return
        
        node = self.top
        self.top = self.top.next
        return node.item

 

큐도 스택과 마찬가지로 리스트와 거의 동일하기 때문에, 이렇게 일일히 구현하지 않고 리스트를 사용해도 된다고 한다. 하지만 구현을 직접 해보고 개념을 익히는게 중요하므로 코드가 익숙해질 때까지 자주 따라 쳐보자!

 

 

문제 풀이

[leetcode] 25. 원형 큐 디자인 (Design Circular Queue)

[leetcode] 25. 원형 큐 디자인 (Design Circular Queue)

나오는 개념 - 원형 큐

 

[Baekjoon] 백준 2164번 카드2

[Baekjoon] 백준 2164번 카드2

나오는 개념 - 데크(deque), 리스트 컴프리헨션

---

마치며

너무 뿌듯해서 한번 더 자랑해야지!

지금까지 코드 구현을 하나도 못하던 내가 오늘은 구현 시도까지 하고 하나는 비록 틀렸지만 하나는 맞았다!!! 점점 발전해가는 모습이 눈에 보이니까 너무 뿌듯하다. 이렇게 계속 하다보면 실력이 많이 늘거라는게 증명되니까 기분이 좋다. 뭔가 내가 하고있는 방향이 맞다는게 증명된거 같아서 깜깜하던 눈 앞이 조금은 밝아지는 기분이다.

 

오늘의 마인드 컨트롤

나는 아직 배우는 단계이다. 너무 조급해하지말고 차근차근 공부하다보면 이 모든 과정이 나에게 피가되고 살이 될 것이다!