Solving Skill ] 탐색

탐색(Search)

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정입니다.

 

그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다루고,

대표적인 탐색 알고리즘으로는 BFS, DFS가 있습니다.

 

 

---

그 전에 Sack, Queue, 재귀 함수를 알아보아야 합니다.

(스택, 큐를 사용할 때, overflow와 underflow에 특히 주의해야 합니다.

  또한 재귀 함수는 스택과 내부적으로 비슷합니다.)

 

재귀함수를 떠올리면...

저는 피보나치 수열이 가장 먼저 생각나네요.

int fibo(int n){
	if(n == 1 || n == 2) return 1;
    	else return fibo(n - 1) + fibo(n - 2);
}

여기서 우리가 확인할 수 있는 것은 바로 점화식입니다. 점화식은 DP와도 관련이 깊습니다.

 

이제 BFS와 DFS를 자세히 알아보겠습니다.

 

 

언제까지 알아만 보고 있는 지 모르겠지만....

왜 stack과 queue는... 이해해도,, 코드로 짜기가 쉽지 않을까요...

더군다나 BFS와 DFS는...ㅋ 하;;; 열받네

---

🐛 DFS(Depth - First  Search)

      "그래프에서 깊은 부분을 우선 탐색하는 알고리즘"입니다.

 

즉, 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이며,
대표적으로 백트레킹에 사용합니다.

일반적으로 Stack을 사용해 구현하지만, 재귀로도 구현이 가능합니다.

동작방식은 아래와 같습니다.

 

1. Stack의 최상단 노드를 확인합니다.
2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고, 방문처리를 합니다.
    방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냅니다.
3. 2번 과정을 반복합니다.

 

💻코드 참고💻

 

 

 

🌊 BFS(Breadth - First  Search)

      "가까운 노드부터 탐색하는 알고리즘"입니다.

 

즉, 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법입니다.
* 미로 찾기 알고리즘에서 주로 이용됩니다.

일반적으로 Queue를 사용해 구현합니다.

동작방식은 아래와 같습니다.

 

1. 탐색 시작 노드를 큐에 넣고, 방문처리를 합니다.

2. 큐에서 노드를 꺼낸 후, 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 큐에 모두 삽입하고 방문처리를 합니다.

3. 2번의 과정을 반복합니다.

 

💻코드 참고💻

---

 🌷 문제

  유형 1 - 음료수 얼려 먹기

  유형 2 - 미로 탈출

 

 

 

 

....

사실 지금 정말 자고 싶은데.. 자면 찝찝할까봐 못 자겠다...오늘 머리에 넣은 거.. 내일 증발되면 어쩌지..?

매일 새로운 탐색!ㅎ 이번엔 정말 끝내고 싶다ㅠㅠ

그래서 문제를 하나 풀고 잘까 하는데...

또 바로 못 풀고 끙끙대다가 찝찝하게 잘까바.... 그게 두렵다ㅠ

 

이 지겨움의 굴레... 언제쯤 잘 짜게 되냐규... 아.. 어쩌란 말이냐 트위스트 추면서...

 

 

---

너비 우선 탐색. Breadth-first search(BFS)

Graph 탐색] Breadth-First Search (BFS)

깊이 우선 탐색. Depth First Search(DFS)