본문 바로가기

탐색2

[백준] 1260 DFS와 BFS DFS와 BFS를 공부하고 좋은 예제를 찾아보다가 백준 알고리즘을 찾게되었다.DFS는 스택을 이용한 방식으로 현 경로상의 노드만을 기억하면 되기때문에 저장공간의 수요가 적다.목표노드가 깊은 곳에 있는 경우 빨리 구할 수 있다. BFS는 큐를 이용한 방식이다. 현 노드에서 인접한 노드를 모두 들리면서 탐색하는 방식이다. 문제. 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.입력. 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 .. 2018. 8. 20.
순차탐색 순차탐색(sequential search) - 탐색은 컴퓨터가 가장 많이 하는 작업중 하나이기 때문에, 탐색을 효율적으로 수행하는 것은 매우 중요하다. - 탐색의 단위는 항목이고, 항목 안에는 항목과 항목을 구별시켜주는 key가 존재하는데, 이를 탐색키라고 한다. 정렬되지 않은 배열에서의 탐색 : 배열을 정렬시키지 않아도 되지만, 비효율적 정렬 된 배열에서의 탐색 : 유지보수는 쉽지만, 값이 클 경우 비효율적. - 순차탐색은 간단한 탐색을 할 경우에만 사용하는 것이 좋다. 2018. 1. 29.