반응형 분류 전체보기110 탐색 알고리즘 - 너비 우선 탐색(Breadth First Search, BFS) 너비 우선 탐색(Breadth First Search, BFS) 너비 우선 탐색이란? - 임의의 노드에서 인접한 노드를 먼저 모두 탐색하고 다음 단계로 넘어간다. - 순환 알고리즘의 형태 - 그래프 탐색 시 방문 노드를 반드시 검사해야 한다. - 두 노드 사이의 최단 경로, 임의의 경로를 탐색할 때 사용한다. - DFS보다 빠른 탐색 속도를 보인다. - 큐를 이용하여 구현한다. 너비 우선 탐색 방법 - 1. A노드를 먼저 방문하고, 방문한 노드를 표시한다. - 2. A노드와 인접한 노드를 큐에 넣고, 해당 노드들을 차례로 방문한다. - 3. A노드와 인접한 노드를 방문하며 해당 노드와 인접한 노드를 다시 큐에 넣는다. - 4. 위 과정을 반복하며 모든 노드를 방문한다. 너비 우선 탐색 코드(C++) #i.. 2020. 6. 22. 탐색 알고리즘 - 깊이 우선 탐색(Depth First Search, DFS) 깊이 우선 탐색(Depth First Search, DFS) 깊이 우선 탐색이란? - 임의의 노드에서 다음 분기로 넘어가기 전 해당 분기를 모두 탐색하는 것. - 순환 알고리즘의 형태 - 그래프 탐색 시 방문 노드를 반드시 검사해야 한다. - 스택 또는 재귀를 이용하여 구현한다. 깊이 우선 탐색 방법 - 1. A노드를 방문하고, 방문한 노드를 표시한다. - 2. A노드와 인접한 B노드를 방문하고, 방문한 노드를 표시한다. - 3. B노드와 인접한 C노드를 방문하고, 방문한 노드를 표시한다. - 4. C노드와 인접한 노드가 없는 경우, 다시 B노드로 돌아가서 다른 인접한 노드가 있는지 탐색한다. - 5. 위 과정을 반복하여 모든 노드를 탐색한다. 깊이 우선 탐색 코드(C++) - 1. 재귀 이용 #incl.. 2020. 6. 22. 탐색 알고리즘 - 이분 탐색(Binary Search) 이분 탐색(Binary Search) 이분 탐색이란? - 정렬되어 있는 데이터에서 원하는 값을 찾을 때 효율적으로 사용할 수 있는 알고리즘이다. - 순차 탐색 보다 훨씬 좋은 성능을 보인다. - n개의 데이터가 주어지면 O(logn)의 시간복잡도를 가진다. - 데이터를 절반씩 나누어 가며 탐색한다. 이분 탐색 과정 - 1. 데이터의 중앙 값과 찾는 값을 비교한다. - 2-1. 찾는 값 > 중앙 값인 경우 중앙 값의 오른쪽 부분을 탐색한다. 2-2. 찾는 값 Right위치가.. 2020. 6. 22. 유니온 파인드(Union - Find) 유니온 파인드(Union - Find) 유니온 파인드란? - 여러 개의 노드 중 선택된 두 노드가 같은 집합에 속하는지 판별하는 알고리즘 - 서로소 집합(Disjoint - Set) 알고리즘이라고도 불린다. - 재귀 함수를 이용하여 부모 노드를 찾고, 합친다. 유니온 파인드 실행 과정 - Find : 선택된 두 노드의 부모를 확인하여 현재 같은 집합에 속하는지 판단하는 과정 - Union : 두 노드를 합치는 과정. 두 노드를 합쳐서 같은 부모를 가지도록 만든다. 유니온 파인드 코드(C++) // 유니온 파인드 클래스 class unionFind { public: void initUnion(int n) { // 부모 노드에 자기 자신이 들어가 있는 경우(아무것도 연결되어 있지 않다.) for (int i.. 2020. 6. 17. 이전 1 ··· 21 22 23 24 25 26 27 28 다음 반응형
