나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다.
▶ 탐색이란?
탐색이란 많은 양의 데이터 중 원하는 데이터를 찾는 과정으로 DFS와 BFS가 있다. 이 유형은 코딩테스트에서 매우 자주 출되는 유형이라고 한다. DFS와 BFS에 대해 설명하기 전 먼저 알아야할 개념인 스택과 큐 자료구조에 대해 알아보고 가자.
▶ 스택 자료구조란?
먼저 들어온 데이터가 나중에 나가고 나중에 들어온 데이터가 먼저 나가는 형식으로 선입후출의 자료구조이다. 파이썬에서 스택은 append를 사용하여 원소를 추가하고 pop을 사용하여 나중에 들어온 데이터를 빼서 활용할 수 있다. 최상단 원소(나중에 들어온 원소)부터 출력하기 위해선 print(lst[::-1])로, 최하단 원소부터 출력하기 위해선 print(lst)로 출력할 수 있다.
▶ 큐 자료구조란?
스택과 반대로 먼저 들어온 데이터가 먼저 차례대로 나가는 선입선출의 자료구조이다. 파이썬에서 큐는 collections의 deque라이브러리를 통해 구현할 수 있다. append를 통해 원소를 추가하고 popleft함수를 사용하여 먼저 들어온 데이터를 뺌으로써 활용할 수 있다.
deque라이브러리는 스택과 큐의 장점을 모두 채택한 것으로 데이터를 삽입하고 제거하는 속도가 리스트에 비해 효율적이다.
'python > 알고리즘 문제풀이' 카테고리의 다른 글
| BFS와 DFS (3)/ BFS와 DFS 정의와 구현 (0) | 2021.06.28 |
|---|---|
| BFS와 DFS (2) / 재귀 함수 (0) | 2021.06.28 |
| 구현- 완전탐색 (0) | 2021.06.27 |
| 그리디 알고리즘 (2) / 큰수의법칙, 숫자카드게임, 1이될때까지 (0) | 2021.06.26 |
| 그리디 알고리즘 (1) / 그리디 알고리즘이란 (0) | 2021.06.25 |