TIL 6주차 4,5일 - 자료 구조

자료 구조

1. 자료 구조

1.1 자료 구조란?

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

• 그 뿐만 아니라 데이터를 사용하려는 목적에 따라 형태를 구분하고, 분류하여 사용합니다.

• 데이터를 정해진 규칙없이 저장하거나, 하나의 구조로만 정리하고 활용하는 것보다 데이터를 체계적으로 정리하여 저장해두는 게 데이터를 활용하는 데 있어 훨씬 유리합니다.

• 선배 개발자들은 무수한 상황에서 데이터를 효율적으로 다룰 수 있는 방법을 모두 모아, '자료 구조' 라는 이름을 붙였습니다.
  자주 쓰이는 네가지 : Stack(스택), Queue(큐), Tree, Graph

2. Stack(스택)

• 데이터를 순서대로 쌓는 자료 구조

• 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근

• Stack 자료 구조의 정책을 LIFO(Last In First Out) 혹은 (First in Last Out) 이라 부릅니다.

2.1 실사용 예제

• 브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때 자료 구조 Stack이 활용됩니다.

• 브라우저에서 자료 구조 Stack이 사용될 떄에는 다음과 같은 순서를 거칩니다.

  1. 새로운 페이지에 접속할 때, 현재(기존) 페이지를 Prev Stack 에 보관합니다.
  2. 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때에는, 현재 페이지를 Next Stack 에 보관하고
     Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져옵니다.
  3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 떄에는,
     Next Stack의 가장 마지막 페이지를 가져옵니다.
  4. 마지막으로 현재 페이지를 Prev Stack 에 보관합니다.

3. Queue(큐)

• Stack 과 반대되는 개념

• 먼저 들어간 데이터가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out)을 특징으로 가지고 있습니다.

3.1 실사용 예제

• 컴퓨터에 연결된 프린터에서 여러 문서를 순서대로 인쇄할 떄 자료구조 Queue가 활용됩니다.

  1. 우리가 문서를 작성하고 출력 버튼을 누르면 해당 문서는 인쇄 작업 Queue에 들어갑니다.

  2. 프린터는 인쇄 작업 Queue 에 들어온 문서를 순서대로 인쇄합니다.

     '컴퓨터(출력 버튼) - (임시 기억 장치의) Queue에 하나씩 들어옴 - Queue에 들어온 문서를 순서대로 인쇄'

4. Graph(그래프)

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

• 하나의 점을 그래프에서는 정점(vertex, 버텍스),
  하나의 선을 그래프에서는 간선(edge, 간선) 이라고 합니다.

4.1 실사용 예제

• 포털 사이트의 검색 엔진, SNS에서 사람들과의 관계, 네비게이션(길찾기) 등

• 비가중치 그래프 : 정점이 연결되어 있다는 간선만 표시
  예시) 서울 - 대전, 대전-부산, 서울 - 부산

• 가중치 그래프 : 정점이 연결되어 있는 간선에 정보가 들어가 있음.
  예시) 정점 : 서울 , 대전, 부산
  간선 : 서울 --140km--대전, 대전--200km--부산, 부산--325km--서울

4.2 그래프 용어

• 무(방)향 그래프(undirected graph)
  서울 - 부산 이어져 있다면 서울 에서 부산으로 갈수 있고 부산에서 서울 갈수 있습니다.
  하지만 단방향(directed) 라면 서울 에서 부산은 갈 수 있지만, 부산에서 서울은 불가능합니다.

• 진입차수(in-degree) / 진출차수(out-degree)
  한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇개인지 나타냅니다.

• 인접(adjacency)
  두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점입니다.

• 자기 루프(self loop)
  정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현합니다.

• 사이클(cycle) : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현합니다

4.3 그래프 표현 방식

• 인접 행렬
  서로 다른 정점들이 인접한 상태인지를 표시한 2차원 배열
  이어져 있다면 1(true), 이어져 있지 않다면 0(false)

• 인접 리스트
  각 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현합니다.
  각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인전합 다른 정점을 담고 있습니다.
  

5. Tree(트리)

• 자료 구조 Tree 는 그래프의 여러 구조 중 무방향 그래프의 한 구조

• 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조라고 부릅니다.

• 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료 구조

• 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 비선형 구조

5.1 기본 용어

• 노드 : 트리 구조를 이루는 모든 개별 데이터

• 루트 : 트리 구조의 시작점이 되는 노드

• 두개의 모드가 상하 계층으로 연결되면 부모 노드(Parent Node), 자식 노드(Child Node)라 부른다.

• 자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(Leaf Node) 라 부릅니다.

5.2 기타 용어

• 깊이(depth)
  루트로부터 하위 계층의 특정 노드까지의 깊이
  루트 노드 부터 시작하기에 루트 노드의 깊이는 0이다.

• 레벨(Level)
  트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨(Level)이라고 표현합니다.
  루트 노드는 레벨 1로 시작하여 같은 레벨에 나란히 있는 노드를 형제 노드(sibling Node)라고 합니다.

• 높이(Height)
  트리 구조에서 리프 노드를 기준으로 루트까지의 높이를 표현합니다.

• 서브 트리(Sub Tree)
  트리 구조에서 root에서 뻗어나오는 큰 트리의 내부에서, 트리 구조를 갖춘 작은 트리를 서브 트리라고 부릅니다.

5.3 실사용 예제

• 컴퓨터의 디렉토리 구조

• 월드컵 토너먼트 대진표

• 조직도

6. BST(Binary Search Tree)

• 가장 자주 쓰이는 트리에는 이진 트리(Binary Tree) 와 이진 탐색 트리(Binary Search Tree)가 있습니다.

6.1 이진 트리(Binary Tree)

• 자식 노드가 최대 두 개인 노드들로 구성된 트리라고
  자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉩니다.

이진 트리 종류	영어 표기	설명
정 이진 트리	Full binary Tree	각 노드가 0개 혹은 2개의 자식 노드를 갖습니다.
완전 이진 트리	Complete binary Tree	마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다.
포화 이진 트리	Perfect binary Tree	정 이진 트리이면서 완전 이진 트리인 경우 입니다. 모든 리프 노의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다.

6.2 이진 탐색 트리(Binary Search Tree)

• 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 트리

느낀 점 && 미비한 점

자료 구조에 대한 모든 걸 공부한 것은 아니고 비록 4개 밖에 배우지 않았지만
개념은 다르게 활용하는 방안은 정답이 없고 실사용 예제에서 다른 알고리즘, 프로그래밍 언어를 써서 활용하는 개념이라는 것은 알게 되었다.
여기에서 조금 멘붕이 오긴 왔지만 넘어서야 할 단계라는 것도 마음 속으로는 알고 있기에 당장 100% 활용할 마음보다는 알고리즘이나 코드를 짤때 마음 한 켠에서 참고 삼아서 계속 생각하는 개념, 이론으로 담아 두어야 겠다.