본문 바로가기

코딩일기/알고리즘75

[자료구조] 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.
[자료구조] 그래프란? (feat. Java) 그래프란? 그래프는 정점(노드)의 집합과 정점(노드)를 이어주는 간선의 집합으로 이루어진 자료구조이다. 그래프의 종류 1. 방향 그래프 / 무방향 그래프 2. 가중치 그래프 3. 비연결 그래프 / 연결 그래프 4. 사이클 / 비순환 그래프 5. 완전 그래프 이렇게 나뉜다. 그럼 이제 각각의 그래프에 대해서 알아보자. 1. 방향 그래프 / 무방향 그래프 방향 그래프는 간선에 방향성이 존재하는 그래프로 A -> B라면 A에서 B로만 갈수 있는 그래프이다. 따라서 (A,B)와 (B,A)는 서로 다르다. 하지만 무방향 그래프는 하나의 간선을 통해서 양방향으로 갈수 있다. 따라서 A - B 라는 간선이 존재한다면 (A - B) 와 (B - A)는 서로 같다. 2. 가중치 그래프 가중치 그래프는 간선에 값이 주어진.. 2021. 6. 18.

티스토리툴바