[자료구조] 자료구조 (Data Structure)

Data Structure

자료구조란?

사전적인 의미는 자료(Data)의 집합의 의미하며, 각 요소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것이라고 합니다.

쉽게 말하면 현실을 프로그래밍 적으로 표현 하는 것이라고 할 수 있습니다

또한 큰 데이터를 효율적으로 관리하는 것 역시 자료구조의 중요한 목적이라고 할 수 있습니다

 

예를 들어 집에 한권의 책이 있다면 굳이 정리할 필요가 없습니다

그런데 만약 100권 500권 있다면 이걸 그냥 냅두면 집이 매우 엉망이거나 원하는 책을 찾기 어려울 것입니다.

하지만 이것을 책장을 이용해 정리를 한다면 책이 차지하는 공간도 작아지고

필요한 책을 빠르게 찾을 수 있을 것입니다.

 

컴퓨터에서도 마찬가지로 데이터가 한두개 밖에 없다면 문제가 되지 않습니다

하지만 데이터가 천만개 억개가 된다면 이것을 관리하기 위한 다양한 장치들이 필요합니다

 

자료구조는 크게 선형구조와 비선형구조로 구분됩니다.

 

선형구조

자료를 구성하는 데이터를 순차적으로 나열시킨 형태를 의미합니다.

 

비선형구조

하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 것입니다.

 

Array

배열이라고 하는 가장 기본적인 자료구조입니다.

데이터를 빈틈없이 나열한, 즉 연속된 메모리 공간을 사용한 자료구조입니다

 

index로 해당 요소(element)에 접근할 수 있습니다.

해당 데이터의 index로 검색하기 때문에 검색속도가 빠릅니다

 

하지만 삽입, 삭제는 느립니다.

예를 들어 index 1번을 삭제 했다면 1번 뒤에 있던 데이터들이 앞으로 한칸씩 다 옮겨줘야 하기 때문입니다.

 

Linked List

Linked List는 이름처럼 링크 되어있다고 생각하면 됩니다.

데이터를 순서대로 나열한 자료구조입니다.

 

배열과는 다르게 데이터들이 연속적으로 놓여있진 않지만

화살표들로 연결되어 있어 데이터들이 떨어진 장소에 위치해 있습니다

 

linked list는 n번째 값을 찾기 위해 첫번째 요소부터 순서대로 확인해야 하기 때문에

데이터를 찾는데는 배열보다 느립니다

 

하지만 데이터를 삽입하거나 삭제할때는 linked list가 효율적입니다

각각의 요소들은 자기 자긴 다음에 어떤 요소인지만을 기억하고 있기 때문에

이 부분만 다른 값으로 바꿔주는 것입니다.

 

linked list는 또한 크게 두가지로 나눌수 있습니다

Singly Linked List

단방향 리스트입니다.

각 요소에는 2가지 항목이 들어가 있습니다 데이터와 다음 요소를 가리키는 포인터입니다.

포인터가 위 그림에서 화살표입니다.

포인터에는 다음 요소가 어디에 있는지 위치 정보가 저장되어 있습니다.

HEAD 포인터에는 리스트의 맨 처음 요소의 위치 정보가 저장되어 있습니다.

 

Doubly Linked List

양방향 리스트입니다.

단방향과는 다르게 리스트를 보면 화살표가 양방향으로 존재합니다.

다음 위치 정보 뿐만 아니라 이전 위치 정보 포인터가 추가로 포함되어 있습니다.

또한 양방향에는 단방향에 HEAD 포인터가 있던 것처럼 TAIL 포인터도 가지고 있는데

그림에는 안나와있네요;;

 

Stack

스택이란 쌓아 올린다는 것을 의미합니다

따라서 스택 자료구조는 책을 쌓는 것처럼 쌓아 올린 형태의 자료구조를 말합니다.

 

책을 쌓으면 가장 위에 있는 책을 꺼내듯이 스택도 가장 위쪽 데이터부터 사용할 수 있습니다.

즉, 가장 늦게 들어온것이 가장 먼저 나가는 Last-In First-Out, LIFO 구조라고 합니다.

 

스택에서 데이터를 삽입 하는 것을 PUSH, 삭제하는 것을 POP이라고 합니다.

 

스택의 활용 예시에는 웹 브라우저의 뒤로 가기, 역순 문자열, 실행 취소 등이 있습니다.

 

Queue

큐 자료구조는 먼저 온 사람이 먼저 나가는 First-In First-Out FIFO, 선입선출 구조입니다.

 

스택은 정해진 한 곳에서 삽입, 삭제가 이루어지지만

큐는 한쪽 끝에서는 삽입이 다른쪽 끝에서는 삭제 작업이 양쪽으로 이루어집니다.

 

입구와 출구가 있는 통로라고 생각하면 될 것 같네요

은행 업무도 이런 큐의 예시입니다.

 

Tree

 

눈치 채셨나요 위에까지는 모두 선형 구조였지만 트리는 비선형 자료구조입니다.

위 그림 처럼 나뭇가지 처럼 펴저 나가는 구조입니다.

 

트리의 구성 요소들입니다

 

노드

트리를 구성하고 있는 기본 요소들

 

루트 노드

트리 구조에서 부모가 없느 최상위 노드(루트 노드는 항상 한개)

 

리프 노드

트리 구조에서 더 이상 자식 노드가 없는 노드

 

부모 노드

자식 노드를 가진 노드

 

자식 노드

부모 노드의 하위 노드

 

형제 노드

같은 부모를 가진 노드

 

그림을 보면 알듯이 트리는 사이클(순환)이 없는 자료구조입니다.

 

각 노드의 자식 노드를 2개 가진 트리를 이진트리 (Binary Tree)라고 합니다

자식 노드가 하나일순 있지만 3개 이상 가질 수는 없습니다

 

위 그림은 완전 이진 트리 (Complete Binary Tree)입니다

 

완전 이진 트리란 이진트리에서 마지막 자식 노드를 제외한 모든 노드가 채워져 있어야 하는 구조입니다.

마지막 노드는 왼쪽부터 채워져 있어야 합니다.

만약 그림에서 C의 자식 노드인 F가 오른쪽에 채워져있었다면 그건 완전 이진 트리가 아닙니다.

 

Heap

힙은 완전 이진 트리의 일종으로 우선 순위 큐를 위하여 만들어진 자료구조입니다.

여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아 내도록 만들어진 자료구조입니다.

 

최대 힙 (max heap)

부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

 

최소 힙 (min heap)

부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

 

힙을 구현 할 때는 배열을 사용합니다

 

부모 노드와 자식 노드의 관계에는 공식이 있습니다

왼쪽 자식 = 자신의 인덱스*2

오른쪽 자식 = 자신의 인덱스*2+1

 

HashTable

해시 테이블은 (key, value)로 데이터를 저장하는 자료구조중 하나로 빠르게 데이터를 검색할 수 있는 자료구조입니다.

 

해시 테이블에서는 해시 함수(Hash Function)를 사용하는데 key를 hash로 바꿔주는 역할을 합니다

 

다만, 서로 다른 키가같은 해시가 되는 경우를 해시 충돌(Hash Collision)이라고 하는데,

해시 충돌을 최대한 줄이는 함수를 만드는 것이 중요합니다.

 

해시는 해시 함수의 결과물이며 저장소(bucket or slot)에서 값과 매칭되어 저장됩니다

 

 

해시를 이용한 방식에 나타날수 있는 문제는 무한한 값(key)을 유한한 값(hash)으로 표현 하면서

서로 다른 두 개 이상의 유한한 값이 동일한 출력 값을 가지게 되는겁니다.

 

3마리의 비둘기가 2개의 비둘기 집에 들어가게 되면 적어도 1개 집에는 비둘기가 2마리 이상 나오겠죠

 

이러한 문제를 해결하는 방법은 Chaining이라고 합니다.

체이닝은 자료 저장 시 저장소에서 충돌이 일어나면 해당 값과 기존 값을 연결 시키는 기법입니다.

이 떄 Linked List를 이용하여 기존의 자료 다음에 위치 시키는 것입니다.

 

체이닝의 장단점

장점 :
1) 한정된 저장소(Bucket)을 효율적으로 사용할 수 있다.
2) 해시 함수(Hash Function)을 선택하는 중요성이 상대적으로 적다.
3) 상대적으로 적은 메모리를 사용한다. 미리 공간을 잡아 놓을 필요가 없다.

 

단점 :
1) 한 Hash에 자료들이 계속 연결된다면(쏠림 현상) 검색 효율을 낮출 수 있다.
2) 외부 저장 공간을 사용한다.
3) 외부 저장 공간 작업을 추가로 해야 한다.

 

Graph

정점(노드)과 간선의(엣지)의 집합이라고 할 수 있습니다

트리 또한 그래프이지만 사이클이 허용되지 않는 그래프입니다.

 

위와 같이 간선에 방향이 없다면 무방향 그래프(Undirected Graph)라고 합니다.

 

간선에 방향성이 있다면 방향 그래프(Directed Graph)

 

 

위 그림은 간선에 가중치가 있는 가중치 그래프(Weight Graph)입니다

각 정점을 이동할 때 발생하는 비용, 가중치를 알 수 있습니다.

 

 

 

 

오늘 하루종일 자료구조 글만 찾아봤네요

이정도는 매우 간추린 정도이니 더 깊게 공부 해야겠습니다.

 

 

 

 

 

 

출처: https://andrew0409.tistory.com/148 

https://choheeis.github.io/newblog//articles/2019-07/BasicDataStructure

https://devuna.tistory.com/22

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#array-vs-linked-listhttps://yoongrammer.tistory.com/68#%ED%8A%B8%EB%A6%AC_(Tree)

https://daeguowl.tistory.com/111

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

https://velog.io/@cyranocoding/Hash-Hashing-Hash-Table%ED%95%B4%EC%8B%9C-%ED%95%B4%EC%8B%B1-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%9D%98-%EC%9D%B4%ED%95%B4-6ijyonph6o