큐

[알고리즘] 큐를 이용해 BFS 구현하기 (python)

오늘은 BFS 구현에서 주로 사용하는 큐에 대해 포스팅하고, 관련 적용 사례를 복습해보려고 한다. 사실 BFS/DFS 문제를 풀다보면 나는 DFS에 훨씬 더 익숙해서, DFS로 주로 풀이를 한다. 그 이유가 BFS 구현에서 큐에서 막히기 때문이라고 생각했고, 관련 포스팅을 하게된 것이다! # 큐(Queue) 우선 큐는 쉽게 말해서 다음과 같은 선입선출 구조이다. 먼저 들어온 요소가 먼저 나가는, 그런 것이다. BFS(너비우선탐색) 구현에는 큐를 이용하는 것이 정석인데, 그 이유는 BFS는 인접한 노드부터 차례로 넓게 탐색하는 알고리즘이기 때문이다. (BFS에 대해서는 따로 설명하지 않겠다) Python에는 친절하게도 deque 라이브러리가 존재해서, 큐 자료구조를 이용하고 싶을 때는 관련 라이브러리를 다..

[자료구조] - (2) 스택(Stacks) with Python

스택(Stacks) 역시 추상적 선형 자료 구조 중 하나이다. 본 게시글은 Python 코드로 작성되었습니다. 1. 스택의 구조 기본적으로 스택은 넣을 때는 한쪽 끝에서 밀어넣어야 하고(push), 꺼낼 때에는 같은 쪽에서 뽑아 꺼내야한다.(pop) 간단히 그림으로 나타내면 다음과 같다. 이와 비슷한 선형 자료구조 큐(Queue)는 좀 다르다. 큐는 '선입선출'의 구조로서, 먼저 들어간 요소가 가장 먼저 나오는 구조이다. 기본적으로 스택은 한쪽에서 꺼내고 빼고를 하는 반면, 큐는 한쪽에서 들어가면 다른쪽에서 나온다! 그리고 스택은 가장 마지막에 들어간 요소가 가장 먼저 나온다 (후입선출) 스택에는 정해진 저장 공간이 있다. 따라서 비어있는 스택에서 원소를 꺼내려 하거나, 꽉찬 스택에 데이터 원소를 넣으려..