자료구조 기초 - 스택, 큐,그래프,트리

자료구조란?

• 자료를 더 효율적으로 저장하고, 관리하기 위해 사용
• 적절한 자료구조는 실행시간을 단축시켜주거나 메모리 용량의 절약을 이끌어 낸다.

자료구조의 선택 기준

1. 자료의 처리 시간
2. 자료의 크기
3. 자료의 활용 빈도
4. 자료의 갱신 정도
5. 프로그램의 용이성

스택(Stack)

스택은 뜻으로 쌓다와 같은 뜻을 가지고 있으며, 후입선출이라는 특징이 있다.

후입선출 (LIFO : last in, first out)

이는 맨 위에 있는 데이터 즉, 제일 마지막에 저장한 데이터를 제일 먼저 꺼낸다.

큐(Queue)

큐는 뜻으로 줄을 기다리다와 대기 행렬과 같은 뜻을 가지고 있으며, 선입선출이라는 특징이 있다.

선입선출 (FIFO : first in, first out)

이는 맨 앞에 있는 데이터 즉, 제일 처음에 저장한 데이터를 제일 먼저 꺼낸다.

그래프(Graph)

이는 노드(정점=vertex)와 간선(edge)으로 구성되어, 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조다.

그래프 용어

• 정점(Vertex) : 연결한 객체들을 의미
• 인접 정점(Adjacent vertex) : 간선에 의해 직접 연결된 정점
• 간선(Edge) : 정점들을 연결하는 선
• 차수(Degree) : 정점에 연결되어 있는 간선의 수, 방향 그래프에서 진입/진출 차수의 합
• 진입차수(In-Degree) : 방향 그래프에서 정점을 머리로 하는 간선의 수, 정점으로 들어오는 간선
• 진출차수(Out-Degree) : 방향 그래프에서 정점을 꼬리로 하는 건선의 수, 정점에서 나가는 간선
• 경로(Path) : 정점A에서 정점B까지 간선에 따라 갈 수 있는 길을 순서대로 나열한 것
• 단순 경로(Simple-path): 경로 중 반복되는 정점이 없는것, 같은 간선을 자나가지 않는 경로
• 사이클(Cycle) : 경로의 시작 정점과 마지막 정점이 같은 경로를 의미

그래프 표현방식

1. 인접행렬 방식 (Adjacency matrix)

• 그래프의 연결관계를 이차원 배열 로 나타내는 방식이다.

정점 A에서 정점 B로 가는 간선이 있으면 1, 아니면 0로 표현한다.

2. 인접리스트 방식 (Adjacency list)

• 인접 리스트는 각 정점이 어떤 정점과 인접한지 리스트의 형태로 볼 수 있는 표현 방식이다.
• 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트에는 자신과 인접한 다른 정점들이 담겨 있다.

이외에 스패닝 트리 알고리즘을 알고 싶다면, 이 링크를 클릭하여 이전 포스팅을 참고하자.

트리(Tree)

노드로 구성된 계층적 자료구조로 최상위 노드(루트)를 만들고, 그 아래 자식 노드를 추가하는 방식이다.

• 그래프의 여러 구조 중 사이클이 없는 그래프이며 일방향 그래프의 한 구조로, 최소연결트리로 불린다.
• 따라서, 루트에서 어떤 노드로 가는 경로는 유일하다.