탐색

탐색이란?

탐색이란 다시 말해서 “데이터를 찾는 방법”을 의미한다.

대표적인 예로는 순차 탐색과 이진 탐색을 예로 들 수 있는데,

• 순차 탐색: 정렬되지 않은 데이터를 대상으로 하는 탐색
• 이진 탐색: 정렬된 데이터를 대상으로 하는 탐색

이와 같이 정리할 수 있겠다.

탐색 알고리즘 문제를 풀다 보면 여러 가지 개념을 접할 수 있다.

기본적인 탐색의 개념이 데이터를 찾는 방법이다 보니깐 데이터를 저장하는 방식에서 부터 찾는 방식에 있어서 여러 개념들이 존재한다.

그래서 탐색에 있어서 중요한 것은 다음과 같다.

효율적인 탐색을 위해서는 “어떻게 찾을까”만을 고민해서는 안되고 “효율적인 탐색을 위한 저장방법이 무엇일까”를 우선적으로 고민해야한다.

현재까지 공부한 내용을 순차적으로 정리할 것인데 다음과 같은 순으로 정리할 것이다.

종류

먼저 가중치(Cost)가 없어도 구할 수 있는 탐색 방식을 알아 볼 것이다.

1. DFS
2. BFS
   해당 두 방식은 간선을 이동할 때 Cost가 있어도 되고, 없어도 되는 방식이다.
   이 둘은 완전 탐색을 수행하는 탐색 기법으로 DFS & BFS에서 정리를 해놓았다.

그리고 Cost가 있을 때 최단 거리를 구할 수 있는 탐색 방식을 알아 볼 것이다.

3. Dijkstra Algorithm (다익스트라 알고리즘)
4. Bellman-Ford Algorithm (벨만-포드 알고리즘)
5. Floyd-Warshall Algorithm (플로이드-와샬 알고리즘)
6. SPFA (Shortest Path Faster Algoirthm)

코드의 경우 Github(JeongbeomSeo) -> 탐색 알고리즘 코드 해당 페이지에 정리를 해놓았다.