Computer Science/Algorithm
-
[Algorithm] DFS( Depth-First Search), BFS(Breadth-First Search)Computer Science/Algorithm 2022. 11. 28. 19:18
1. DFS 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동 로투 노드(혹은 임의의 다른 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식 ▶모든 노드를 방문하고자 하는 경우에 이 방법을 선택 ▶깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함 ▶검색 속도 자체는 BFS에 비해서 느림 ▶ 스택, 재귀함수로 구현 ① 탐색 시작 노드를 스택에 삽입하고 방문처리 ② 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리 ③ 위 과정을 수행할 수 없을때까지 반복 - 노드 방문 시 방문(Visited)여부를 반드시 검사해야 한다. 아니면 무한 루프에 빠질 수 있음. - 탐색 과정이 ..
-
[Algorithm] Union-Find algorithmComputer Science/Algorithm 2022. 11. 7. 17:19
Disjoint Set - 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 즉, 공통 원소가 없는 "상호 배타적"인 부분 집합들로 나눠진 원소들에 대한 자료구조 Union-Find algorithm - 서로소 집합(Disjoint Set)을 표현할 때 사용하는 알고리즘 - 그래프 알고리즘으로 Union(합집합) + Find(찾기) 로 '합집합 찾기'라는 의미를 가지고 있다. - 여러 노드 중 2개의 노드를 선택하여 같은 그래프에 속해 있는 지 확인하는 알고리즘이다. 연산 - Make-set(x) // 초기화 : x를 유일한 원소로 하는 새로운 집합 생성 - Union(x, y) // 합하기 :원소 x가 속한 부분집합과 원소 y가 속한 부분집합의 합집합을 구한다. ..