출처: 이것이 취업을 위한 코딩테스트다 with 파이썬
탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다.
대표적인 탐색 알고리즘으로 DFS와 BFS를 꼽을 수 있는데 이 두 알고리즘의 원리를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해와 재귀함수에 대한 이해가 전제되어야 한다.
* 자료구조: 데이터를 표현하고 관리하고 처리하기 위한 구조
* 오버플로우: 특정한 자료구조가 수용할 수 있는 데이터의 크기를
이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생
* 언더플로우: 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서
삭제 연산을 수행하면 발생
Plain Text
복사
스택
스택은 선입후출 구조 또는 후입선출 구조
큐
선입선출 구조
재귀함수
자기 자신을 다시 호출하는 함수
재귀 함수의 종료 조건
재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수가 언제 끝날지, 종료 조건을 꼭 명시해야 한다.
•
소스코드를 반복적으로 구현한다는 말은 반복문을 이용한다는 의미이며, 흔히 재귀적으로 구현한다는 말과 대비되는 의미로 사용.
•
반복문 대신에 재귀 함수를 사용했을 때 얻을 수 있는 장점은 재귀 함수의 코드가 더 간결하다. 그 이유는 재귀 함수가 수학의 점화식을 그대로 소스코드로 옮겼기 때문이다
•
수학에서 점화식은 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것을 의미한다.
ex) 유클리드 호제법
두 자연수 A,B(A>B)에 대해서 A를 B로 나눈 나머지가 R일 경우
A와 B의 최대공약수와 B와 R의 최대공약수가 일치하다.
즉) 두 수중 하나의 수가 1일때까지 재귀함수 돌림
DFS
깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
DFS는 스택 자료구조(혹은 재귀 함수)를 이용
1.
탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다.
2.
스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리를 합니다.
3.
더 이상 2번의 과정을 수행할 수 없을때까지 반복합니다.
프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있다
•
인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식
→ index를 통해서 바로 노드를 찾을 수 있음
→ 메모리 공간이 노드 개수 X 노드 개수 만큼 비용이 듦
•
인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식
→ 처음 노드부터 찾으려는 노드를 순서대로 탐색 후 찾음
→ 메모리 공간이 노드 개수 + 간선 개수 만큼 듦
→ 검색 시간, 메모리 공간 최적화하려면 ArrayList를 사용하면 된다.
BFS
bfs는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색한다.
bfs는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같음
1.
탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다.
2.
큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 넣고 방문처리합니다.
3.
더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.
