[이것이코딩테스트다]5장_탐색 알고리즘 DFS/BFS(1)_DFS,BFS에 필요한 자료구조 기초

#탐색

탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다.  프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로는 DFS와 BFS를 꼽을 수 있다. 

 

#DFS/BFS를 위해 필요한 자료구조

스택과 큐

 

#자료구조란?

자료구조 : '데이터를 표현하고 관리하고 처리하기 위한 구조'를 의미한다.

 

#스택과 큐

스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성된다. 

-삽입(push) : 데이터를 삽입한다.

-삭제(pop) : 데이터를 삭제한다. 

 

#오버플로우, 언더플로우

스택과 큐를 사용할 때는 오버플로우와 언더플로우를 고민해야한다. 

-오버플로우 : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입연산을 수행할 때 발생한다. 즉, 저장공간을 벗어나 데이터가 넘쳐흐를 때 발생한다.

-언더플로우 : 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태이므로 언더플로가 발생한다.