Java 코테 핵심이론 (DFS, BFS, 이진탐색)

5-1 깊이 우선 탐색 (DFS)

깊이 우선 탐색은 그래프 완전 탐색 기법중 하나로 그래프의 시작 노드에서 출발하여 한쪽 분기를 정한 후 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. 시간 복잡도는 O(노드 수 + 에지 수)이다.

 

<특징>

• 재귀 함수로 구현
• 스택 자료구조 이용 (후입 선출)

실제 구현 시 재귀 함수를 이용하므로 스택 오버플로를 유의해야 한다. DFS로 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상정렬등의 문제를 풀 수 있다.

 

 

<핵심 이론>

DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하며, 그래프는 인접 리스트로 표현한다. DFS 구현은 스택보다는 스택 성질을 갖는 재귀 함수로 많이 구현합니다.

 

 

1. 우선 DFS를 시작할 노드를 정한 후,  사용할 인접 리스트를 초기화 한다.

초기 작업은 인접 리스트로 그래프 표현하기/ 방문 배열 초기화하기/ 시작 노드 스택에 삽입하기를 수행한다.

 

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

먼저 pop을 수행하여 노드를 꺼내고 해당 노드의 인접 리스트를 확인한다.
인접리스트에 있는 값을 스택에 넣는다. 그리고 방문 배열에 체크해준다.

 

3. 스택 자료구조에 값이 없을 때까지 반복하기

이미 다녀간 노드는 방문배열을 바탕으로 재삽입하지 않는 것이 핵심이다.

 

정리하면 스택에 노드를 삽입할 때 방문 배열을 체크하고, 스택에서 노드를 뺄 때 탐색 순서에 기록하며 인접 노드를 방문 배열과 대조한다.

 

 

5-2 너비 우선 탐색 (BFS)

너비 우선 탐색은 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발하여 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘입니다.

 

<특징>

• 선입 선출 구조
• Queue 자료구조 이용

너비 우선 탐색은 선입선출 방식으로 탐색하므로 큐를 이용해 구현한다. 또한 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개 일때 최단 경로를 보장한다.

 

 

<핵심 이론>

1. 우선 BFS를 시작할 노드를 정한 후,  사용할 인접 리스트를 초기화 한다.

초기 작업은 인접 리스트로 그래프 표현하기/ 방문 배열 초기화하기/ 시작 노드 에 삽입하기를 수행한다.

 

2. 큐에서 노드를 껀내 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기

먼저 큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입한다.
이 때 방문 배열을 체크하여 이미 방문한 노드는 큐에 삽입하지 않 큐에서 꺼낸 노드는 탐색 순서에 기록한다.

 

3.  자료구조에 값이 없을 때까지 반복하기

이미 다녀간 노드는 방문배열을 바탕으로 재삽입하지 않는 것이 핵심이다.

 

 

5-3 이진 탐색

이진 탐색은 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.

 

<특징>

• 중앙값 비교를 통한 대상 축소 방식
• 시간 복잡도는 O(logN)

이진 탐색은 정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘으로 구현 및 원리가 비교적 간단하므로 많은 코딩테스트에서 부분문제로 요구한다.

 

<핵심 이론>

1. 현재 데이터 셋의 중앙값을 선택한다.
2. 중앙값 > 타깃 데이터 일 때 중앙값 기준으로 왼쪽 데이터 셋을 선택한다.
3. 반대일 때는 오른쪽 데이터 셋을 선택한다.
4. 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.