탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조

<1> 자료구조 기초

1. 스택 Stack

선입후출 First In Last Out

후입선출 Last In First Out

2. 큐 Queue

선입선출 First In First Out

from collections import deque
queue = deque()
# deque는 스택과 큐의 장점을 모두 채택하여 데이터를 넣고 빼는 속도가 효율적

3. 재귀 함수

자기 자신을 다시 호출하는 함수

• 종료 조건 반드시 명시해야 함

<2> 탐색 알고리즘 DFS / BFS

1. DFS

깊이 우선 탐색

그래프에서 깊은 부분(가장 멀리 있는 노드)을 우선적으로 탐색하는 알고리즘

• 탐색 방향의 역방향으로 되돌아가는 백트래킹(back tracking) 특성을 가지고 있음

• 인접 행렬 방식

  2차원 배열에 각 노드가 연결된 형태 기록

  • 노드 개수 많을수록 메모리 낭비
  • 노드 개수가 1,000개 이하일 때 사용

• 인접 리스트 방식

  ‘연결 리스트’ 자료구조 이용

  • 메모리 효율적 사용
  • 연결 정보 얻는 속도 느림