[Algorithm] 자료구조 기초 이론

 

자료구조란 ?

자료구조란 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것

 

데이터(data)는 ?

데이터는 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값. 

데이터는 그 자체만으로 어떤 정보를 가지기 힘들고, 분석하고 정리하여 활용해야만 의미를 가질 수 있다.

 

 

 

자주 등장하는 네 가지 자료구조

• Stack, Queue, Tree, Graph

 

 

 

 

---

Stack

• Stack은 쌓다, 쌓이다, 포개지다 와 같은 뜻으로 자료구조에서는 데이터(data)를 순서대로 쌓는다는 의미를 가진다
• 자료구조 Stack의 특징은 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근.
• 이런 Stack 자료구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 한다.

 

 

---

Queue

 

• 큐(Queue)는 줄을 서서 기다리다, 대기 행렬 이라는 뜻
• 자료구조 Stack과 반대되는 개념
• 먼저 들어간 데이터(data)가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out) 가 특징.
• 가장 나중에 진입한 자동차는 먼저 도착한 자동차가 모두 빠져나가기 전까지는 톨게이트를 빠져나갈 수 없다.
• 자료구조 Queue는 데이터(data)가 입력된 순서대로 처리할 때 주로 사용.
• 컴퓨터 장치들 사이에서 데이터(data)를 주고 받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용.
• 이것을 통틀어 버퍼(buffer)라고 한다.
• 대부분의 컴퓨터 장치에서 발생하는 이벤트는 파동 그래프와 같이 불규칙적으로 발생함.
• 이에 비해 CPU와 같이 발생한 이벤트를 처리하는 장치는 일정한 처리 속도를 갖는다.
• 불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 버퍼(buffer)를 사용.

   

  컴퓨터와 프린터 사이의 데이터(data) 통신 정리

  • 일반적으로 프린터는 속도가 느리다.
  • CPU는 프린터와 비교하여, 데이터를 처리하는 속도가 빠르다.
  • 따라서, CPU는 빠른 속도로 인쇄에 필요한 데이터(data)를 만든 다음, 인쇄 작업 Queue에 저장하고 다른 작업을 수행.
  • 프린터는 인쇄 작업 Queue에서 데이터(data)를 받아 일정한 속도로 인쇄.

  유튜브와 같은 동영상 스트리밍 앱을 통해 동영상을 시청할 때, 다운로드 된 데이터(data)가 영상을 재생하기에 충분하지 않은 경우가 생김. 이때 동영상을 정상적으로 재생하기 위해 Queue에 모아 두었다가 동영상을 재생하기에 충분한 양의 데이터가 모였을 때 동영상 재생하는 것.

  
  
  

  ---

   
•  
•  

Tree

 

• 그래프의 여러 구조 중 무방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다
• 트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조
• 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 비선형 구조
• 트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클이 없다.

 

 

루트(Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결

각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하계층으로 연결되면 부모/자식 관계를 가진다.

 

자식 없는 노드 리프 노드(leaf Node)

 

용어정리

• 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
• 루트(Root) : 트리 구조의 시작점이 되는 노드
• 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
• 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
• 리프(Leaf) : 트리 구조의 끝지점이고, 자식 노드가 없는 노드

 

 

 

 

 

---

Graph

 

그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조

직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있고,

간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다

하나의 점을 그래프에서는 정점(vertex)이라고 표현하고,

하나의 선은 간선(edge) 이라고 한다.

 

그래프 용어들

• 진입차수(in-degree) / 진출차수(out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타내는 것
• 인접(adjacency): 두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점
• 자기 루프(self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현. 다른 정점을 거치지 않는다
• 사이클(cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있는 것. 

 

 

그래프의 표현 방식: 인접 행렬 & 인접 리스트

 

인접 행렬

두 정점을 바로 이어 주는 간선이 있다면 이 두 정점은 인접하다고 표현

인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬으로 2차원 배열의 형태로 나타낸다.

만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표입니다.

만약 가중치 그래프라면 1 대신 관계에서 의미 있는 값을 저장합니다.

위의 내비게이션 예제라면, 거리를 입력하면 좋습니다. 네비게이션 그래프를 인접 행렬로 표현하면 다음과 같습니다.

 

 

인접 행렬은 언제 사용할까?

• 한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이.
• 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용.

 

인접 리스트

인접 리스트는 각 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현

각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담는다.

만약 우선 순위를 다뤄야 한다면 더 적합한 자료구조(ex. queue, heap)를 사용하는 것이 합리적 .

 

인접 리스트는 언제 사용할까?

• 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용
• 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지한다