탐색

주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘

vector<vector<int>> A;
vector<bool> visited;

깊이 우선 탐색 (DFS)

그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여
최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여
다시 탐색을 수행하는 알고리즘

• 재귀 함수로 구현
• 스택 자료구조를 이용
• 한 번 방문한 노드를 다시 방문하지 않도록, 방문 여부를 체크할 배열이 필요

시간 복잡도 : O(V+E) , V = 노드 수, E = 간선 수

void DFS(int node)
{
	cout << node << " ";
 	visited[node] = true;
	
    for (int i : A[node])
	{
		if(!visited[i])
    		DFS(i);
	}
}

너비 우선 탐색 (BFS)

시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘

• FIFO 탐색
• 큐 자료구조를 이용
• 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장

시간 복잡도 : O(V+E) , V = 노드 수, E = 간선 수

void BFS(int node)
{
	queue<int> q;
    q.push(node);
    
    visited[node] = true;
    
    while(!q.empty())
    {
    	int cur = q.front();
        q.pop();
        cout << cur << " ";
        
        for(int i : A[cur])
        {
        	if(!visited[i])
            {
            	visited[i] = true;
                q.push(i);
			}
		}
	}
}

이진 탐색

데이터가 정렬된 상태에서 원하는 값을 찾아내는 알고리즘.

• 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는 방법.
• 중앙값 비교를 통한 대상 축소 방식
• 데이터들은 정렬된 상태여야 한다.

시간 복잡도 : O(log N)

while(start <= end)
{
	int mid = (start + end) / 2;
    int midV = A[mid];
    
    if(midV > target)
    	end = mid - 1;
	else if(midV < target)
    	start = mid + 1;
	else
    {
    	find = true;
        break;
	}
}