1. 탐색

많은양의 데이터 중에서 원하는 데이터를 찾는 과정
대표적인 알고리즘으로 DFS, BFS 가 있다!!
하지만 이를 이해하기위해 기초 자료구조에 대한 이해가필요하다..

2. 자료구조

데이터를 표현하고 관리하고 처리하는 구조
대표적으로 스택, 큐 가 있다!!
자료구조가 수용할수있는 데이터의 크기를 넘어서 Push하면 오버플로 발생!!
데이터가 전혀없는 상태에서 Pop하면 언더플로 발생!!

🔍 스택

스택은 박스 쌓기에 비유 하면 쉽다!! 선입후출 구조

✔ 스택예제

let stack = [];

// 삽입(5) - 삽입(2) - 삽입(3) - 삭제()

stack.push(5);
stack.push(2);
stack.push(3);
stack.pop();

console.log(stack);

결과값 : [5,2]

🔍 큐

큐는 대기 줄에 비유 하면 쉽다 !! 선입선출 구조

✔ 큐예제

let queue = [];

// 삽입(5) - 삽입(2) - 삽입(3) - 삭제()

queue.push(5);
queue.push(2);
queue.push(3);
queue.shift();

console.log(queue);

결과값 : [2,3]

💡 DFS 란?

깊이우선 탐색!!
그래프에서 가장아래의 자식(깊은부분)부터 탐색한다!!
동작원리 : 스택 사용
구현방법 : 재귀함수 사용

💡 BFS 란?

넓이우선 탐색!!
그래프에서 가장가까운 자식부터 탐색한다!!
동작원리 : 큐 사용
구현방법 : 큐 사용

💡 백트래킹이란?

백트래킹이란, 깊이 우선 탐색(DFS)으로 시작하여 불필요한 분기(branch)를 가지치기(pruning)하는 방식으로, 탐색 도중 답이 될 수 없는 경우(유망성이 없음)에 대해서는 더 진행하지 않고 부모 노드로 되돌아가서 다른 해를 찾는 기법이다.
DFS가 불필요한 경우까지 모두 탐색하는 것을 제한할 수 있는 방법이다. 조건문 등의 장치를 통해 답이 될 수 없는 상황을 정의하고 DFS 중에 그에 해당하면 탐색을 중지시킨 뒤 이전 분기로 돌아간다.

💡 자주나오는 문제유형

1. 경로탐색 유형(최단거리, 시간) - BFS

2. 네트워크 유형(연결) - DFS

3. 조합유형(모든조합만들기) - DFS

팁:) 쉬운것들은 DFS로 풀도록 하되, 복잡하거나 시간초과되는 문제는 BFS로 해결해보자!!

탐색알고리즘 문제모음
프로그래머스 고득점 kit