Page tree
Skip to end of metadata
Go to start of metadata

1. 리스트

연결 리스트는 데이터 요소의 선형 집합으로, 데이터의 순서가 메모리에 물리적인 순서대로 저장되지 않는 특징을 갖습니다.

Linked List - Java

연결 리스트는 동적으로 새로운 노드를 삽입하거나 삭제하기 간편하다. 포인터 기반이나 배열 기반으로 구현 가능하다.

배열과 다르게 특정 인덱스에 접근하기 위해서 순서대로 읽어야 하므로 상수 시간에 해당 인덱스에 접근할 수 없다. 즉, 탐색에는 O(n)이 소요된다. 그렇지만 추가하거나 삭제하는 작업은 O(1)에 가능하다.


2. 그래프

그래프는 비선형 자료구조로, 정점(Node, Vertex), 간선(Edge)로 나타낼 수 있습니다.

또한 방향을 갖는 그래프와 무방향 그래프가 존재합니다. 

Algorithm) 그래프(graph) - 자료구조 - ZeroCho Blog

그리고 그래프에선 경로가 존재하는데 예를 들어 A에서 D까지의 경로는 여러가지가 존재합니다.

또한 간선에 가중치 값을 가진 가중치 그래프가 있습니다.

그리고 정점과 연결되어 있는 간선의 개수를 차수(Degree)라고 합니다. 차수는 방향 그래프에서는 in-degree와 out-degree로 구분합니다.

그래프를 표현하는 방법은 다양합니다. 주로 인접 행렬과 인접 리스트 방식으로 표현합니다. 인접 행렬은 아래와 같습니다.

6-2. 그래프의 표현(인접 행렬, 인접 리스트, 인접 다중 리스트)

인접 리스트로 표현한 방식은 아래와 같습니다.

5. 그래프 (Graph) - 인접리스트법

인접 행렬의 경우 희소 행렬로 표현되므로 메모리를 많이 차지합니다.

그래프 순회란 그래프 탐색이라고도 하며, 그래프의 각 정점을 방문하는 방법을 이야기합니다.

그래프 순회는 깊이 우선 탐색(Depth-First Search)와 너비 우선 탐색(Breadth-First Search) 2가지 알고리즘이 있습니다. DFS는 스택이나 재귀로 구현하며, BFS는 주로 큐로 구현하며 최단 경로를 구하는 문제에 사용합니다.

그래프 탐색 알고리즘 BFS, DFS 정리 - Blog by saegeullee

3. 트리

트리는 루트 값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합입니다. 트리의 중요한 속성중 하나는 트리는 자식도 트리이고 그 자식도 트리 구조를 갖는 형태입니다.

트리는 위의 그림과 같이 루트에서 시작합니다. 루트는 자식노드를 가지며 간선으로 연결되어 있습니다. 자식 노드의 개수를 차수(Degree)라고 하며 깊이는 루트 노드로부터 현재 노드까지의 거리입니다.

트리와 그래프의 차이점은 무엇을까요? 트리는 그래프의 한 종류이며, 순환 구조를 갖지 않는 그래프입니다. 그리고 트리는 부모가 자식으로 가리키는 단방향 그래프이며 부모는 하나만 갖는 것이 특징입니다.


4. 문제

4.1 리스트

4.2 그래프

4.3 트리


  • No labels