Chapter 5. DFS/BFS를 들어가기 앞서 자료구조에 대한 기초적인 지식이 필요하다. 먼저 탐색(Search)과 자료구조(Data structure)에 대해서 알아본다.
탐색이란 많은 양의 데이터 중에서 자신이 원하는 데이터를 찾는 과정을 의미한다. 뒤에서 작성하게 될 그래프, 트리 등의 자료구조 내에서 원하는 데이터를 찾는 알고리즘이 자주 등장할 것이다. 대표적으로 DFS 혹은 BFS 등의 탐색 알고리즘이 존재한다. 이러한 탐색 알고리즘을 정확하게 이해하기 위해서는 자료구조에 대한 이해가 필요하다.
자료구조란 '데이터를 표현하고 관리하고 처리하기 위한 구조'를 의미한다. 그 중 스택(Stack)과 큐(Queue)는 자료구조의 기초 개념이며 자세한 내용은 다음 게시글에서 다루기로 한다.
스택과 큐는 다음 두 개의 핵심적인 함수로 구성된다.
- 삽입 (push) : 데이터를 삽입한다.
- 삭제 (pop) : 데이터를 삭제한다.
실제로 스택과 큐를 사용할 때는 삽입, 삭제 외에도 오버플로(overflow), 언더플로(underflow)를 고려해야 한다. 오버플로와 언더플로의 의미는 아래와 같다.
- 오버플로 (overflow) : 해당 자료구조가 수용할 수 있는 데이터의 크기가 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생한다.
- 언더플로 (underflow) : 해당 자료구조가 비어있는 상태에서 삭제 연산을 수행할 때 발생한다.
따라서 스택과 큐 등을 사용할 때는 데이터를 수용할 수 있는 메모리의 크기를 고려하는 것 또한 중요함을 알 수 있다.
'Algorithm' 카테고리의 다른 글
자료구조 (Data Structure) (3) - 큐 (Queue) 란? (0) | 2023.07.30 |
---|---|
자료구조 (Data Structure) (2) - 스택 (Stack) 이란? (0) | 2023.07.30 |
구현 (Implementation) (3) - 실전문제 4.3) 게임 개발 (0) | 2023.07.29 |
구현 (Implementation) (2) - 실전문제 4.2) 왕실의 나이트 (0) | 2023.07.29 |
구현 (Implementation) (1) - 코딩테스트에서 구현이란? / 예제 4.1) 상하좌우, 예제 4.2) 시각 (0) | 2023.07.28 |