[CS] 자료구조 기초 Day-35

자료구조란?

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

데이터는 분석하고 정리하여 활용해야 의미를 가질 수 있습니다.
또한 목적에 따라 형태를 구분하고, 분류하여 사용합니다.

필요에 따라 데이터의 특징을 잘 파악(분석)하여 정리하고, 활용해야 합니다.

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

자주 사용하는 자료구조

• Stack
• Queue
• Tree
• Graph

특정 상황에 놓인 문제를 해결하는 데 특화되어 있습니다. 많은 자료구조를 알아두면, 어떤 상황이 닥쳤을 때 적합한 자료구조를 빠르고 정확하게 적용하여 문제를 해결할 수 있습니다.

Stack

쌓다, 쌓이다, 포개지다 와 같은 뜻을 가지고 있습니다.
데이터를 순서대로 쌓는 자료구조입니다.

가장 먼저 들어간 데이터는 가장 나중에 나올 수 있습니다. 반대로 가장 늦게 들어간 데이터는 가장 먼저 나올 수 있습니다.
(LIFO: Last In First Out) 혹은 (FILO: First in Last Out)

Queue

줄을 서서 기다리다, 대기행렬 이라는 뜻을 가지고 있습니다.
가장 먼저 들어간 데이터는 가장 먼저 나옵니다.
(FIFO: First In First Out) 혹은 (LILO: Last In Last Out) 특징으로 가지고 있습니다.

데이터가 입력된 순서대로 처리할 때 주로 사용합니다.

Graph

거미줄처럼 여러 개의 점들이 선으로 이어져 있는 복잡한 네트워크망과 같은 모습을 가지고 있습니다.

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

• 직접적인 관계: 두 점 사이를 이어주는 선이 있을 때

• 간접적인 관계: 몇 개의 점과 선에 걸쳐 이어진 경우

• 정점(Vertex): 하나의 점

• 간선(Edge): 하나의 선

알아둬야 할 그래프 용어

• 정점(Vertext): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소
• 간선(Edge): 정점 간의 관계를 나타냅니다.
• 인접 정점(adjacent vertext): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻합니다.
• 가중치 그래프(weighted Graph): 연결의 강도가 얼마나 되는지 적혀져 있는 그래프를 뜻합니다.
• 비가중치 그래프(unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프를 뜻합니다.
• 무(방)향 그래프(undirected Graph): 두 개 정점의 데이터가 서로 이동하는 것이 가능한 그래프
• 단(방)향 그래프(directed Graph): 데이터의 일방 통행
• 진입차수(in-degree) / 진출차수(out-degree): 한 정점에 진입하고 진출하는 간선이 몇 개인지를 나타냄
• 인접(adjacency): 두 정점 간 간선이 직접 이어져 있다면 두 정점은 인접한 정점입니다.
• 자기 루프(self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다라고 표현합니다.
• 사이클(cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현합니다.

그래프 표현 방식(인접 행렬 & 인접 리스트)

인접 행렬

인접(adjacency): 두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접한다고 합니다.
가중치 그래프(weighted Graph)를 통해서 연결 됐는지 알 수 있습니다. 정점이 이저여 있다면 1(true) 이어져 있지 않다면 0(false)로 표시합니다.

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

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

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

• 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용합니다.

Tree

단방향 그래프의 한 구조로, 하나의 뿌리로부터 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조라고 부릅니다.

데이터가 바로 아래에 있는 하나 이상의 데이터에 단방향으로 연결된 계층적 자료구조입니다. 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조입니다.

트리 구조는 루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터 간선(Edge)로 연결합니다. 각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가집니다. 자식이 없는 노드는 리프 노드(Leaf Node)라고 부릅니다.

용어 정리

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

자료구조(Tree)의 깊이와 높이, 레벨

• 깊이(depth)
  트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현할 수 있습니다. 루트 노드는 지면에 있는 것처럼 깊이가 0입니다.

• 레벨(level)
  같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현할 수 있습니다. depth가 0인 루트는 level 1입니다. 루트의 자식 노드는 level 2입니다. (같은 레벨에 나란히 있는 노드를 형제 노드(sibling Node)라고 부릅니다.)

• 높이(height)
  트리 구조에서 리프 노드를 기준으로 루트까지의 높이를 표현할 수 있다. 리프 노드의 높이를 0으로 부모 노드로 진행 될수록 +1 씩 하면 된다.

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

Binary Search Tree

트리 구조는 편리한 구조를 전시하는 것 외에 효율적인 탐색을 위해 사용하기도 합니다.
효율적인 탐색을 위해 고민하고 발전 시켜 특징에 따라 여러 가지 이름으로 불립니다.

• 이진 트리(Binary Tree): 자식 노드가 최대 두 개인 노드들로 구성된 트리입니다. 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있습니다. 이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉩니다.

• 정 이진 트리(Full binary tree): 각 노드가 0개 혹은 2개 자식 노드를 갖습니다.

• 포화 이진 트리(Perfect binary tree): 정 이진 트리이면서 완전 이진 트리인 경우입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다.

• 완전 이진 트리(Complete binary tree): 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져 있어야 합니다.

Tree traversal

트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 합니다. 트리 구조는 계층적 구조라는 특별한 특징을 가지기 때문에, 모든 노드를 순회하는 방법에 크게 세 가지가 있습니다.

전위 순회(preorder traverse)

가장 먼저 루트 노드를 방문 후 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색합니다.

중위 순회(inorder traverse)

루트를 가운데에 두고 순회합니다. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여 루트를 기준으로 왼쪽 노드 순회가 끝나면 오른쪽 노드로 이동하여 탐색합니다.

후위 순회(postorder traverse)

루트를 가장 마지막에 순회합니다. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 거치지 않고 이동해 순회한 뒤 제일 마지막에 루트를 방문합니다.

BFS / DFS

그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점을 한 번씩 방문(탐색)하는 것이 목적입니다. 그래프의 데이터는 배열처럼 정렬이 되어 있지 않습니다. 따라서 원하는 자료를 찾으려면, 하나씩 모두 방문하여 찾아야 합니다.

정점 탐색 방법에는 여러 가지가 있습니다. 그 중 대표적인 것이 BFS / DFS 입니다.

BFS (Breadth-First Search)

가까운 정점부터 탐색합니다. 그리고 탐색할 정점이 없을 때 그 다음 떨어져 있는 정점을 순서대로 방문합니다. 다른 말로 너비 우선 탐색이라고 합니다.

주로 정점 사이의 최단 경로를 찾을 때 사용합니다. 최악의 경우 모든 경로를 다 살펴봐야 합니다.

DFS (Depth-First Search)

하나의 경로를 끝까지 탐색한 후, 다음 경로로 넘어갑니다. 단 몇 번으로 경로를 찾을 수 있습니다.

깊이를 우선적으로 탐색하는 방법을 Depth-First Search 깊이 우선 탐색 이라고 합니다. BFS보다 탐색 시간이 오래 걸릴 수도 있지만 훨씬 빠를 수도 있기 때문에 장단점을 잘 따져봐야 합니다.