본문 바로가기

Wook's 개척일기234

[자료구조] BFS(Breadth First Search) Java 구현 BFS는 Breadth First Search로 너비우선 탐색이란 뜻을 가진다. 너비 우선 탐색을 아래와 같은 과정으로 그래프를 모두 순회하는것이다. 자식노드와 그 형제노드를 모두 검색한뒤 그 다음에 있는 자식의 자식 노드와 그 형제들을 순회하는 방법이다. 해당 그림처럼 노드를 넓게 탐색한다. 그래서 주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을때 이방법을 사용한다. BFS의 장점 1. 노드의 수가 적고 깊이가 얕은경우 빠르게 동작한다. 2. 단순 검색 속도가 DFS보다 빠르다. 3. 너비를 우선 탐색하기 때문에 답이 되는 경로가 여러개인 경우 최단경로를 보장한다. 4. 최단 경로가 존재한다면 경로가 무한대로 깊어져도 최단경로를 반드시 찾을수 있다. BFS의 단점 1. 재귀호출의 DFS와.. 2021. 6. 20.
[자료구조] DFS(Depth First Search) Java 구현 DFS는 Depth First Search 로 번역을 하면 깊이우선 탐색이다. 깊이 우선 탐색은 아래와 같은 방식으로 작동한다. 해당 노드와 인접한 노드들을 방문하고 그 노드의 자식(인접노드)이 있다면 방문 다하고 난 다음에 형제 노드를 방문하는것이다. 그렇다면 DFS의 장점과 단점에 대해서 알아보자. DFS 장점 1. 현재 경로상의 노드들만 기억하면 되서 저장공간의 수요가 적다. 2. 목표 노드가 깊은 단계에 있는 경우라면 해를 빨리 구할수 있다. 3. 구현이 너비 우선 탐색보다는 쉽다. DFS 단점 1. 단순 검색 속도가 BFS보다 느림 2. 해가 없는 경우에 무한 루프에 빠질수가 있다. 3. 깊이우선은 해를 구하면 종료가 되기 때문에 최단경로가 된다는 보장이 없음 그렇다면 DFS는 어떤 상황일때 주.. 2021. 6. 20.
[자료구조] 인접행렬로 구현한 그래프 (Java) 그래프는 인접행렬을 통해서도 구현이 가능하다. 인접행렬을 통한 그래프의 특성과 장단점부터 살펴보자. 인접행렬 특성 인접 행렬은 그래프와의 연결관계를 이차원 배열로 나타내는방식이다. 인접행렬의 장단점 장점 1. 구현이 쉽다. 2. 노드 i와 j가 연결되어 있는지 확인하고 싶을때 index로 바로 확인이 가능하기 때문에 시간복잡도 O(1)을 가진다. 단점 1. 전체 노드의 개수가 V개 일때 어떤 특정 노드의 연결된 노드를 확일하고 싶을때 해당 노드와 연결된 노드가 있는지 배열로 일일히 체크 해야하기 때문에 O(V)의 시간이 걸린다. 2. 노드개수만큼의 이차원 배열을 만들어야 하기 때문에 메모리를 O(V^2)의 메모리 복잡도를 가진다. 따라서 노드의 수에 비해 간선의 수가 적은 그래프에는 적절하지 않다. 그럼.. 2021. 6. 19.
[자료구조] 인접리스트 구현 : LinkedList (Java) 인접리스트는 노드의 인접된 노드를 아래와 같이 연결시키는것이다. 따라서 인접리스트로 그래프를 구현하게 되면 아래와 같은 장점이 발생한다. 장점 실제 연결된 노드 들끼리만 저장하기 때문에 모든 정점들의 원소의 합이 간선의 개수와 같다. 따라서 간선의 개수에 비례하는 메모리만 차지한다 O(E) (E는 간선을 뜻함) 단점 특정 노드와 연결된 노드가 몇번인지 확인하기 위해 모든 노드들을 확인해야 한다. 따라서 O(V)만큼의 시간 복잡도를 지닌다. 인접리스트로 그래프 구현하는것의 특징에 대해서 알아봤으니 이제 실제로 소스를 어떻게 구현했는지를 알아보자. 일단 아는 LinkedList를 활용하여서 인접리스트를 구현하였다. LinkedList에 대해 잘 모르시는 분들은 아래링크 참조하시면 될것 같다. https://.. 2021. 6. 19.

티스토리툴바