[Do it!_Algorithm with Python] 2.탐색

Source: inflearn 'Do it! 알고리즘 코딩테스트 with python'

 

 

Depth-First Search (DFS)

---

깊이 우선 탐색은 그래프의 완전 탐색 기법 중 하나이다.

 * 완전 탐색 기법 : 가능한 경우의 수를 모두 나열하면서 원하는 답을 찾는 방법 (그래프의 모든 노드 다 살펴볼거야~)

 

 

▪️방법

1) 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기(줄기)를 정한다.

2) 그 분기의 최대 깊이 (가장 밑에 있는 노드)까지 탐색을 마친다

3) 다른 쪽 줄기로 이동하여 반복한다.

 

 

▪️특징, 시간 복잡도

기능	특징	시간복잡도 (node 수: V / edge 수 : E)
그래프 완전 탐색	- LIFO 탐색 - 재귀 함수로 구현 - 스택 자료구조 이용	O(V+E)

우선 깊이우선 탐색은 그래프 완전 탐색에 사용된다.

따라서 재귀함수를 이용해서 반복할 수 있다. 또는 Stack을 사용해도 된다.

Stack은 앞서 보았듯이 FILO 방법이다 (먼저 들어온 데이터가 나중에 나감).

이는 결국 재귀함수의 logic과 같으므로, 재귀함수나 stack 중 하나를 선택해서 구현하면 된다.

 

만약 재귀함수를 사용할 경우, stack overflow에 조심해야 한다.

* stack overflow: A라는 함수 안에서 A를 부르게 되면 무한대로 자기 자신을 부른다. (한 줄기에서 쭉 아래로 무한대로 들어가는 것)

 이때 만약 tree의 높이가 너무 높으면 컴퓨터에서 자동적으로 overflow를 일으켜서 에러를 발생시킨다.

 '언제까지 들어갈꺼니..너 멈춰' 이런 느낌?

 

DFS는 코테에서 가장 많이 사용된다.

기본적으로 그래프를 탐색하는 데 사용되지만 사이클 찾기, 위상정렬 등 여러 방법으로 활용될 수 있으니 잘 알아두자.

 

 

▪️핵심 이론

• 방문 배열 필요 
  • 한번 방문한 노드는 다시 방문하지 않는다. (비효율적임) 따라서 방문했던 노드를 기록할 배열이 필요하다.
• 인접 리스트로 그래프 표현
  • 보통 그래프를 표현할 때는 인접 행렬 / 인접 리스트를 사용하지만, 우선 DFS는 인접 '리스트'를 사용한다.
  • 즉, 데이터를 담는 자료구조로 인접 리스트 사용
• 후입선출 특징을 가지므로 stack을 사용한다.
  • 하지만 보통 문제를 풀 때는 stack성질을 갖는 재귀함수의 형태로 많이 구현한다.

 

▪️과정

 

1. DFS를 시작할 노드를 정한 후, 사용할 자료구조 (인접리스트) 초기화 하기

 

먼저 인접리스트를 만드는 방법!

원본 그래프의 노드 1을 보면, 화살표가 노드 2,3을 가리킨다. 따라서 인접리스트의 1 영역에 2,3을 추가해준다.

노드 3은 4를 가리키므로 인접리스트 3 영역에 4를 추가해준다.

 

다음으로 방문배열 만들기!

먼저 시작할 때는 모두 F로 초기화 해둔다.

이후 노드 1에서 출발할때는 자신의 방문배열 영역에 T로 업데이트 해준다. 이후 다음 노드로 이동할때마다 동일하게 업데이트 한다.

 

마지막으로 stack에 추가해주기

방문 배열을 업데이트 해줬으면 그 노드를 stack 자료구조에 추가해 준다. ( stack에 먼저 넣고 방문배열 업데이트 해도 상관 없다.)

 

 

 

 

2. 스택에서 노드를 꺼낸 후, 꺼낸 노드의 인접 노드를 다시 스택에 삽입

 

1) pop으로 가장 나중에 들어간 노드(node 1)를 꺼내면서 탐색 순서에 노드 1을 추가해준다.

2) 꺼냈던 노드 1의 인접 리스트를 확인한다. 노드 2와 3이 연결되어 있구나! 앞으로 방문해야할 노드가 이거군

3)  근데 노드 2와 3 방문했었나? 이미 탐색한 거 아니야? 만약 T이면 skip하고 F일 경우 stack에 2와 3을 추가한다.

    (stack 추가 전 방문배열 확인 필수!)

4) 동시에 방문배열을 T로 업데이트 해준다. (2와 3 방문한다~)

 

 

 

 

3. 스택 자료구조에 값이 없어질때 까지 반복한다.

 

 

스택에 아무것도 없다는 것은, 더이상 방문할 노드가 없다는 뜻이므로 종료한다.

이때 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않아야 한다. 앞에서 말했던 3)과정!

 

 

🔻key point

스택에 노드를 삽입할 때 => 방문 배열 체크 (인접 노드를 방문 배열과 대조해서 이미 방문한 것은 스택에 넣지 말기)

스택에서 노들 뺄 때 => 탐색 순서에 기록

 

 

 

 

 

Breath-First Search (BFS)

---

너비우선 탐색 또한 그래프 완전탐색 깁법 중 하나이다.

하지만 DFS와 달리 시작 노드를 기준으로 '가까운' 노드를 먼저 방문하면서 탐색한다.

 

 

기능	특징	시간복잡도 (node 수: V / edge 수 : E)
그래프 완전 탐색	- FIFO 탐색 - Queue 자료구조 이용	O(V+E)

또한 LIFO가 아니라 FIFO 방식으로 탐색하므로, '큐'를 이용한다.

BFS은 탐색 시작 노드와 가까운 노드에 먼저 방문하기떄문에, 목표 노드에 도착하는 방법(경로)가 여러 개 일때, 최단 경로를 보장한다.

 

 

 

1. DFS를 시작할 노드를 정한 후, 사용할 자료구조 (인접리스트) 초기화 하기

DFS와 거의 동일하고, 자료구조가 '큐'인 점만 다르다.

 

 

 

 

2. 큐에서 노드를 꺼낸 후, 꺼낸 노드의 인접 노드를 다시 큐에 삽입

 

DFS와 거의 동일하다.

가장 먼저 노드 1을방문하고 큐에 넣었으므로, 나갈때도 노드 1이 먼저 나간다. 이때 빼내면서 탐색 순서에 추가해준다.

이후 노드 1과 인접해 있던 2와 3을 차례로 넣고, 방문배열을 업데이트 해준다.

단! 이때도 넣기 전에 꼭 방문배열을 확인해준다! 이미 방문했으면 큐에 넣지 않는다.

 

(뺄 때 탐색 순서 추가 / 넣기 전 방문노드 체크, 넣고 난 후에는 방문노드 업데이트)

 

 

 

3. 큐 자료구조에 값이 없어질때 까지 반복한다.

 

자료구조가 '큐'이므로, 먼저 들어간 노드가 먼저 나온다.

노드 2가 먼저 들어갔으므로 노드 2를 빼내면서 탐색순서에 추가해 준다.

이후 노드 2와 인접한 5와 6을 방문했는지 확인하고, 둘 다 F 이므로 큐에 추가해준다.

다음에는 노드 3을 빼내면서 동일한 과정을 반복한다.

마지막에 노드 4가 나가면서 큐는 비게되고 탐색을 종료한다.

 

 

 

 

🔻DFS, BFS 정리

탐색 종류	기능	특징	시간복잡도 (node 수: V / edge 수 : E)
DFS	그래프 완전 탐색	- 한 분기에서 최대 깊이까지 쭉 내려감 - LIFO 탐색 - 재귀 함수로 구현 - Stack 자료구조 이용	O(V+E)
BFS	그래프 완전 탐색	- 시작 노드에서 가장 가까운 노드를 먼저 탐색 - FIFO 탐색 - Queue 자료구조 이용	O(V+E)

 

 

 

 

Binary Search

---

이진탐색은 우선 조건이 하나 있는데, 데이터가 정렬돼 있어야 한다.

이 상태에서 원하는 값을 찾아내는 알고리즘이다.

 

 

원리는 내가 갖고 있는 데이터의 중앙값과, 찾고자하는 target 값을 비교해서 데이터의 크기를 절반으로 줄이며 찾는 방법이다.

시간복잡도가 꽤 좋기때문에, 원하는 데이터를 찾고 싶을 때 사용하는 가장 일반적인 방법이다.

기능	특징	시간복잡도 (N: 데이터 수)
Target 데이터 탐색	중앙값 비교로 데이터의 크기를 절반씩 축소	O(logN)

 

 

▪️핵심 이론

오른차순으로 정렬된 데이터에서 다음 과정을 반복한다.

1) 현재 데이터셋의 중앙값 선택

2) 중앙값 > target data => 중앙값 기준으로 오른쪽 데이터셋 선택

3) 중앙값 < target data => 중앙값 기준으로 왼쪽 데이터셋 선택

4) 이 과정을 반복하다가 중앙값 == target data이면 탐색 종료