[알고리즘(Algorithm)] 5. 스택(Stack)과 큐(Queue)
- 스택(Stack)과 큐(Queue)는 배열(Array)에서 발전된 형태의 자료구조이다.
- 스택과 큐의 구조는 비슷하지만 처리 방식에 차이가 있다.
※ 스택(Stack)과 큐(Queue)의 핵심 이론
* 스택(Stack)
: "쌓여있다.", "쌓아 올리다.", "굴뚝" ... 🗻
즉, 스택은 굴뚝 형태로 데이터를 차곡차곡 쌓아 올린 형태의 자료구조이다.
이러한 스택은 *후입선출(LIFO : Last In, First Out)이 이루어지는데, 이는 다음 그림을 통해 확인할 수 있다.
* 후입 선출은 삭제와 삽입에 대한 방식으로, 출입(삽입)과 퇴출(삭제)가 한 쪽에서만 발생하는 것을 알 수 있다.
| 스택(Stack)의 연산 | |
| Push(data) | data를 스택의 가장 윗 부분에 추가한다. (Last in / Top) |
| Peek() | 스택의 가장 위에 있는 항목을 반환한다. (Top) |
| pop() | 스택에서 가장 위에 있는 항목을 제거한다. (First out / Top) |
| isEmpty() | 스택이 비어 있는 경우 True를 반환한다. |
이러한 스택은 "깊이 우선 탐색 (DFS: Depth-First Search)", "백트래킹(Backtracking)" 종류의 코딩 테스트에 효과적이다.후입 선출(LIFO)은 "재귀 함수 알고리즘" 원리와 일맥상통하기 때문이다.
* 재귀 함수 알고리즘(Recursive Algorithm)
* 재귀 함수 알고리즘, 재귀 알고리즘(Recursive Algorithm)
: 하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘.
이러한 재귀 문제에서는, 평소 사용하던 '절차 지향적(Procedural) 사고'기 아닌, '*귀납적 사고(Induction)'를 통해 접근하여야 한다.
| 절차 지향적 사고와 귀납적 사고의 차이 |
도미노 n개를 예로 들어, 각 사고의 차이점을 설명한다. 절차 지향적 사고의 경우, 1번 도미노를 쓰러뜨리면, 2번 도미노가 쓰러지고 이후 3번 도미노까지 쓰러진다. 이러한 방식으로 연이어 n개의 도미노가 쓰러지는 것이 '절차 지향적 사고'이다. 귀납적 사고의 경우, k번 도미노가 쓰러진다 가정하면, k+1번째 도미노 또한 쓰러지고, 이후 k+2번째 도미노도 쓰러진다. 따라서 결국 모든 도미노가 쓰러질때까지 확인하게 되며, 이를 '귀납적 사고'라 한다. * 귀납(induction) 또는 귀납법 : 개개의 구체적인 사실이나 현상에 대한 관찰을 통해 일반적인(보편적인) 사고를 이끌어내는 것. |
* 깊이 우선 탐색 (DFS: Depth-First Search)
* 탐색(Search)
: 수많은 데이터 중, 원하는 데이터를 찾는 과정을 뜻한다.
"깊이 우선 탐색(Depth-First Search)"은 그래프 탐색 알고리즘(Graph Search Algorithm) 중 하나이다.
| 그래프 탐색 알고리즘(Graph Search Algorithm) |
* 그래프 탐색 문제(Graph traversal problem) : 어떤 한 그래프와 해당 그래프의 시작 정점이 주어졌을 때, 시작점에서 간선(Edge, E)를 타고이동할 수 있는 정점(Vertex, V)들을 모두 찾는 문제. 이러한 그래프 탐색 알고리즘에는 너비 우선 탐색(BFS)와 "깊이 우선 탐색(DFS)"가 있다. |
* 깊이 우선 탐색(Depth-First Search)
: 루트 노드(혹은 다른 임의의 노드)에서 시작하여 다음 분기(Branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.
* 깊이 우선 탐색(Depth-First Search)의 특징
- 자기 자신을 호출하는 순환 / 재귀 알고리즘(Recursive Algorithm)의 형태를 가지고 있다. - 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다. - 해당 알고리즘에선, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 만드시 검사해야 한다. (무한 루프 방지) |
* 백트래킹(Backtracking)
: 문제 해결을 위해 진행 과정을 수행하던 도중, 해당 경로가 답이 되지 않으리라 판단되면 이를 멈추고 다시 되돌아 간다.
(반복문을 모두 수행하지 않고, 답을 도출할 수 없다 판단되면 작업을 중단하여 돌아간다.)
이러한 방식을 "가지 치기(Pruning)"이라 한다.
즉, 백 트래킹(Backtracking) 방식은 모든 경우의 수 중에서 특정 조건을 만족하는 경우만 살펴보는 것이다.
[참고] https://chanhuiseok.github.io/posts/algo-23/
알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제
이번에 살펴볼 개념은 백트래킹에 관한 내용입니다.
chanhuiseok.github.io
* 큐(Queue)
: "줄(기다린다, 대기 ...)", "줄을 맞추어 기다리는 것" ... 🚶♂️🚶♀️👩🦯👨🦼
즉, 먼저 온 사람이 먼저 업무를 보는 방식의 *선입선출(FIFO, First In, First Out) 자료 구조이다.
* 선입선출(FIFO, First In First Out)은 삽입 방향 따로, 삭제 방향이 따로 이므로 양방향에서 이뤄진다.
| 큐(Queue) 용어 | |
| rear | 큐에서 가장 끝 데이터를 가리키는 영역 (값6) |
| front | 큐에서 가장 앞의 데이터를 가리키는 영역 (값1) |
| add | rear(가장 끝 데이터) 부분에 새로운 데이터를 삽입하는 연산 |
| poll | front(가장 앞 데이터) 부분에 있는 데이터를 삭제하고 확인하는 연산 |
| peek | front(가장 앞 데이터) 부분에 있는 데이터를 단순히 확인함. |
이러한 큐는 너비 우선 탐색(BFS, Breadth-First Search)에서 자주 사용하므로 이 역시 스택과 함께 잘 알아두어야 한다.
* 너비 우선 탐색(BFS, Breadth-First Search)
* Stack의 깊이 우선 탐색(DFS)에서도 확인할 수 있다.
| 그래프 탐색 알고리즘(Graph Search Algorithm) |
* 그래프 탐색 문제(Graph traversal problem) : 어떤 한 그래프와 해당 그래프의 시작 정점이 주어졌을 때, 시작점에서 간선(Edge, E)를 타고이동할 수 있는 정점(Vertex, V)들을 모두 찾는 문제. 이러한 그래프 탐색 알고리즘에는 "너비 우선 탐색(BFS)"와 깊이 우선 탐색(DFS)가 있다. |
* 너비 우선 탐색(BFS, Breadth-First Search)
: 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
즉, 시작 정점으로 부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회(traversal) 방법이다.
앞의 "깊이 우선 탐색(DFS)" 이전에 넓게(Wide) 탐색하는 것이 특징이다.
* 너비 우선 탐색(BFS, Breadth-First Search)의 특징
- 직관적이지 않을 수 있다. (시작노드에서 거리에 따라 단계별로 탐색하기 때문.) - 재귀적(Recursive)으로 동작하지 않는다. - 어떤 노드를 방문 했었는지 여부를 반드시 검사해야 한다. (DFS와 동일) - BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 '큐(Queue)'를 사용한다. - 'Prim', 'Dijkstra' 알고리즘과 유사하다. |
큐(Queue)에는 '우선순위 큐(Priority Queue)★'라는 개념 또한 있다.
* 우선순위 큐와 힙(Priority Queue & Heap)
큐(Queue)는 먼저 들어온 데이터(순서) 나가는 FIFO(First In, First Out) 형태의 자료구조이다.
이때, 우선순위 큐(Priority Queue) 데이터의 순서가 아닌 '우선순위'를 기준으로 하여 FIFO 방식을 취한다.
이러한 우선순위 큐는 일반적으로 힙(Heap)을 사용하여 구현한다.
큐 설정에 따라 front에 항상 최댓값(Maximum) 또는 최솟값(Minimum)이 위치하게 된다.
이때, 우선순위 큐는 설정에 맞는 '최대', '최소'를 찾아내지만, 해당 과정에서 무조건적인 '정렬'이 일어나지는 않는다.
(반드시 정렬되어 있다는 보장은 없다.)
* 힙(Heap)
: 우선순위 큐를 위해 고완된 *완전이진트리(Complete Binary Tree) 형태의 자료구조.
이떄, 힙은 트리 종류 중 하나임을 알 수 있다.
* 힙의 특징
- 완전 이진트리(Complete Binary Tree) 형태로 이루어져 있다. - 부모노드와 서브트리간 대소 관계가 성립된다. (반정렬 상태) - 이진 탐색 트리(BST, Binary Search Tree)와 달리 중복값이 허용된다. |
* 코딩테스트에서 많이 사용하는 개념이므로 익혀두는 것이 좋다.
* 자세한 내용은 [자료구조] 우선순위 큐와 힙 (Priority Queue & Heap) - Suyeon's Blog를 참고하거나,
이후 포스팅에서 참고 바란다. (다른 포스팅으로 정리할 예정 - tree 부분)
참고 및 출처 : [ Do it! 알고리즘 테스트 with JAVA - 하루코딩(Inflearn) ]