[Algorithm] DFS/BFS

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
대표적인 그래프 탐색 알고리즘으로 DFS, BFS

DFS

깊이 우선 탐색(Depth-First Search)

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료구조(혹은 재귀함수)를 이용, 구체적인 동작은 아래와 같음

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

*방문 기준: 문제의 요구에 따라 달라짐

BFS

너비 우선 탐색(Breadth-First Search)

• 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐 자료구조를 사용
• 동작구조는 아래와 같다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
   

스택 자료구조

• 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출 - LIFO)
• 입구와 출구가 동일한 형태
  

큐 자료구조

• 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출 - FIFO)
• 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태
  
  => 왼쪽 IN, 오른쪽 OUT

재귀 함수

• 재귀 함수(recursive function)란 자기 자신을 다시 호출하는 함수
• 💥 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓이므로, 스택을 사용해야 할 때 구현상 스택 라이브러리 대신 재귀 함수를 이용
• 단순한 형태의 재귀 함수 예제
  • '재귀 함수를 호출합니다.' 라는 문자열을 무한히 출력
  • 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력

function recursiveFunction() {
	console.log('재귀 함수 호출');
    recursiveFunction();
}
recursiveFunction();

재귀 함수의 종료 조건

• 재귀 함수를 문제 풀이에서 사용할 때는 종료 조건을 반드시 명시할 것

function recursiveFunction(i) {
// 100번째 호출을 했을 때 종료되도록 종료 조건 명시
	if(i === 100) return ;
	console.log(`${i]번째 재귀 함수에서 `${i+1} 번째 재귀함수를 호출`);
    recursiveFunction(i+1);
    print(`${i}번째 재귀함수를 종료`)
}
recursiveFunction(1);

팩토리얼 구현 예제 (19:50 ~)

유클리드 호제 (21: 50 ~)

참고 - 동빈나 유튜브