본문 바로가기

💾 Algorithm/- 자료구조 & 알고리즘16

[자료 구조] 자바를 이용한 그래프의 구현-인접 리스트 구현 :: Graph implementation by using adjacency List in java. 인접 리스트 인접 리스트는 그래프의 각 정점에 인접한 정점을 연결 리스트로 표현하는 방법이다. 연결 리스트의 노드는 인접 정점 정보를 저장하는데, 그래프에는 이러한 각 인접 리스트에 대한 헤더 포인터를 갖는 배열로 갖는다. 이 말은 정점의 번호만 알고 있으면 각 정점의 연결 리스트에 쉽게 접근 가능하다는 소리와 같다. 위의 그림과 같이 연결되어있는 관계를 리스트로 표현하는 것이다. 인접 리스트의 특징 n개의 노드가 있다면 n^2만큼의 메모리 양이 필요했던 인접 행렬과 달리, 인접 리스트는 필요한 만큼만의 메모리를 잡아먹는다. 또한 노드를 탐색하는 것도 상수에 가까운 시간이 걸리지만 어떤 노드i와 j의 연결 상태를 보려면 모든 원소를 돌아야 하기 떄문에 오래 걸린다는 단점이 있다. 인접 리스트의 구현 cl.. 2020. 6. 25.

[자료 구조] 자바를 이용한 그래프의 구현-인접 행렬 구현 :: Graph implementation by using adjacency matrix in java. 인접 행렬 인접 행렬은 G= {V, E} 의 그래프를 boolean의 행렬로 나타낸 것이다. 행렬의 상태에는 두 가지가 있다. M[i][j] = 1인 경우 M[i][j] = 0인 경우 행렬의 상태값이 1인 경우는 그래프가 간선에 의해 연결되어 있을 때, 즉 i, j가 그래프에 존재할 때를 뜻하고 그렇지 않을 때는 0이라고 표현한다. 인접 행렬의 특징 인접 행렬을 이용하는데 가장 큰 장점은 바로 간선의 존재 유뮤이다. 정점 u와 정점 v를 연결하는 간선이 존재하는지 확인하기 위해서는 M[u][v]의 값이 1인 경우와 0인 경우만 조사하면 되기 때문에 시간 복잡도가 O(1)인 상수 시간이 나온다. 또한 인접 행렬은 n개의 정점을 갖는 그래프를 인접 행렬로 표현하고자 한다면 간선의 수와는 무관하게 항상 n^2.. 2020. 6. 25.

[자료 구조] 그래프 자료구조 :: Graph Data Structure 그래프(Graph)란? 그래프란? 쉽게 한 문장으로 설명한다면, 현실 세계의 관계를 시각적으로 나타낼 수 있는 구조. 라고 할 수 있다. 우리는 일상에서 다음과 같은 곳에서 그래프를 사용한다. 네비게이션 최단 경로 네트워크 통신 친구 관계 그래프를 사용하면 객체간의 관계를 쉽게 나타낼 수 있다는 장점으로 많이 사용한다. 이를 전문적인 용어로 말 한다면 정점과 간선의 집합으로 구성되며 수학적으로는 G = (V, E)의 관계로 나타난다. 처음 보는 사람들은 이해가 안 갈 수도 있는데, 한 번 따라가 보자. 그래프의 종류 그래프의 종류는 다음과 같은 세 가지로 나뉜다. 무방향 그래프 (Undirected Graph) 무항향 그래프는 간선에 방향이 표시되어있지 않은 그래프를 무방향 그래프라고 한다. 여기서 하나.. 2020. 6. 25.

[자료 구조] PriorityQueue 컬렉션을 이용한 자바 우선순위 큐 :: Java Priority Queue implementing by PriorityQueue Class 우리가 지난시간에 Heap을 배웠는데, 사실 Heap은 이 Priority Queue, 우선순위 큐를 위해서 고안된 자료구조라고 해도 과언이 아니다. 우선순위 큐에 대해서 지금부터 알아가보자. 우선순위 큐 우선순위 큐는 말 그대로 우선순위(Priority) 가 존재하는 큐 이다. 예를들어 우리가 학생들이 있을 때, 나이 순으로 학생들을 쭉 세운다면 나이가 우선순위가 되어 나이가 크거나 작은 순서로 학생들이 정렬이 될 것이다. 이 말을 다시 풀어서 말 한다면, 들어온 순서에 상관 없이 우선순위가 높은 데이터가 먼저 출력된다는 뜻이다. 스택 VS 큐 VS 우선순위 큐 자료 구조 삭제 대상 스택 가장 나중에 들어온 데이터 큐 가장 먼저 들어온 데이터 우선순위 큐 가장 우선순위가 높은 데이터 여기서 신기한 사실.. 2020. 6. 25.

이전 1 2 3 4 다음

티스토리툴바