![[CS]자료 구조 & 알고리즘](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Futm4Y%2FbtrRnuwEL9v%2FXnejxqb2xNKcPlXlyEU3dK%2Fimg.png)
❓자료 구조란?
자료 구조란 여러 데이터의 묶음을 저장하고 사용하는 방법을 정의한 것입니다.
❗ 데이터(DATA)란
자료구조란 데이터를 정리하고 활용하기 쉽게 하기 위해 존재합니다.
👉그렇다면 위에서 설명하는 데이터는 무엇을 말하는 것일까요?
데이터란 문자📝, 소리🔊, 그림🧩, 영상🎥 등 실생활을 구성하고 있는 모든 값입니다.
❗하지만 데이터들은 그 자체 만으로 어떤 정보도 가지기 힘들기 때문에 데이터를 분석하고 정리하는 과정을 통해 데이터를 활용할 수 있게 됩니다.
👉데이터를 체계적으로 정리하여 저장해 두는 게 데이터를 활용하는 데 있어 훨씬유리합니다.
🧬자료 구조의 분류
데이터를 효율적으로 다룰 수 있는 방법들을 한데 모아 만든 것이 자료 구조입니다.
👇다음은 자료구조를 보기 쉽게 정리한 표입니다.
다음은 자료 구조에서 많이 사용하는 자주 등장하는 방법들이다.👇👇
1. Arrary(배열)
동일한 크기에 메모리 공간이 빈틈없이 연속적으로 나열된 자료 구조를 말한다.
배열의 요소는 하나의 타입으로 통일되어 있으며 서로 연속적으로 인접해 있다. 이러한 배열을 밀집 배열(dense array)라고 한다.
덕분에 배열은 위의 데이터 표와 같이 인덱스를 통해 효율적으로 요소에 접근할 수 있습니다.
❗하지만 위처럼 정리가 되지 않은 배열은 특정한 값을 찾기 위해서는 모든 배열 요소를 처음부터 끝까지 차례차례 탐색(선형 탐색) 해야 해야 하는 복잡함을 가지고 있습니다.
또한 배열에 중간 부분에 요소를 삽입하거나 삭제하면 배열의 메모리는 그대로 남아있기 때문에 남은 배열의 메모리 주소를 이동시켜 주어야 한다.
그렇기 때문에 배열을 뒤에다 요소 추가하고 삭제하는 arr.push()와 arr.pop()보다는 배열의 앞에 요소를 앞에 추가하거나 삭제하는 arr.unshift()와 arr.shift()가 더 느리다.
2. Linked List(연결 리스트)
Linked List는 element가 인접한 메모리에 저장되지 않는 선형 데이터 구조입니다.
👉노드들이 array처럼 붙어 있지 않고 포인터를 사용하여 연결됩니다.
때문에, Linked listd의 노드들은 데이터와 다음 노드의 주소에 대한 갑을 가지고 있습니다,
👉위에 보이는 head부분은 Linked in의 시작 부분입니다. 앞에 위치한 노드를 통해 다음 노드로 가기 때문에 처음 시작 부분은 중요합니다.
struct node
{
int data;
struct node *next;
};위와 같은 이유로 노드들을 거쳐 거쳐 element를 찾아야 하기 때문에 linked인은 array요소에 비해 상대적으로 느리지만 중간에 element를 연결하고 추가하는 것에 있어서 굉장히 free 합니다.
👉array는 메모리 주소에 순차적으로 채우기 때문에 새로운 element가 들어갈 틈이나 사제할 element가 마땅치 않습니다.
그렇다면 element를 추가하고 삭제할 때 다음 노드는 위치는 어떻게 설정하는 것일까요?
/*처음부분에 노드 추가하기*/
let node = new Node(data);
//새로운 노드 생성
node.next = head
//새로운 노드의 다음 노드로 첫번째 노드 지정
head = node
//새로 만들어진 노드를 헤드로 지정/*⭐중간 부분에 데이터 추가*/
let node = head
//노드이 위치 찾기
while (--findNode!=0){
node = node.next
}
//찾고자 하는 노드의 위치에 다다를때까지 다음노드로 이동
let backNode = node.next
//찾고자하는 노드를 저장한다.
let newNode = new Node(input)
//새로운 노드 생성
node.next = newNode
//찾고자 했던 노드의 위치의 다음 노드로 새로 생성한 노드 추가
newNode.next = backNode
//새로 생성한 노드의 다음위치로 backNode지정
/*⭐중간 부분에 데이터 삭제*/
let node = head
while (--k!=0)
node = node.next
//노드의 위치 찾기
let tobedeleted = node.next
//삭제하고자 하는 노드를 저장한다.
node.next = node.next.next
//삭제하는 노드를 다음 노드를 전의 다음 노드에 추가한다.
delete tobedeleted
//노드를 삭제한다.위의 예시 자료처럼 노드를 찾는 과정이 제일 길고 추가하거나 삭제하는 과정은 생각보다 짧고 간단한 것은 볼 수 있습니다.
👉array list와 정반 대적인 성격임을 알 수 있습니다,
3. Stack(스택)
쌓다 라는 의미로 데이터를 차곡차곡 쌓아 올린 형태의 자료 구조입니다.
위의 사진과 같이 먼저 들어간 데이터가 가장 나중에 나오는 후입 선출(LIFO Last In First Out)의 구조를 가지고 있습니다.
👉때문에 stack자료 구조는 하나의 입출력 방향을 가지고 있습니다.
때문에 top으로 정한 곳을 통해서만 접근이 가능하고, 무한이 스택이 쌓이는 것을 방지하기 위해 스택의 크기가 제한되어 있습니다.
대부분의 실사용 예제는 브라우저의뒤로 가기, 앞으로 가기 기능을 구현할 때 활용됩니다.
4. Queue(큐)
스택과 다르게 선입선출의 구조로 되어 있는 자료 구조입니다.
위의 자료를 보면 큐(Queue)의 이름처럼 데이터가 통과하기 위해 앞에 데이터가 통과하기를 대기하는 것을 볼 수 있습니다.
👉큐의 한쪽 끝에서는 삽입 작업이, 다른 쪽 끝에서는 삭제 작업이 양쪽으로 이루어지는 것을 알 수 있습니다.
👆위와 같은 가장 먼저 삽입된 자료가 가장 먼저 처리되는 스택의 구조를 후입 선출(LIFO Last In First Out) 구조라고 합니다.
Queue의 경우 입력한 순서대로 출력이 나오기 때문에 여러 문서들을 순서대로 보내야 할 때나, 전송속도가 다른 여러 데이터를송수신할 때 많이 사용됩니다.
5. Hash table(해쉬 테이블)
Hash table은 해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조를 말합니다.
👉해시 함수는 임기의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수를 말합니다.
📌해시 함수를 통해 얻어지는 값은 해시 값, 또는 해시 코드라고 합니다.
즉! 해시함수를 거치는 해싱 과정을 통해 고정된 크기의 값으로변환한 뒤 데이터를 저장하는 자료 구조를 Hash table이라고 합니다.
👉이러한 해싱 구조로 데이터를 저장하면 Key값으로 데이터를 찾을 때 해시 함수를 1번만 수행하면 되므로 매우 빠르게 데이터를 저장/삭제/조회할 수 있습니다.
6. Graph(그래프)
그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조입니다.
마치 거미줄처럼여러 개의 점들이 선으로 이어져 잇는 복잡한 네트워크망과 같은 모습을 가지고 있습니다,
그래프에서의 정점은 하나의 점을 뜻하고 만약 점들이 직접 적인 관계가 있다면 간선을 통해 둘을 이어줍니다.
👉정점 두 개를 직접 이어주는 간선이 있다면 두 정점은 인접하다고 얘기할 수 있습니다.
인접하지 않은 경우도 물론 존재하면 여러 점들과 선을 통해 연결된 경우 간접적인 관계라고 말합니다.
👉노드들 마다 서로 연결이 있을 수도 있고 없을 수도 있으며 부모와 자식 개념이 존재하지 않고 방향성과 무 방향성 그래프가 둘 다 존재합니다.
그래프의 구현 방법에는 인접 행렬과 인접 리스트 방식이 있습니다.
인접 행렬 : 그래프의 노드를 2차원 배열로 만든 것입니다.
노드들 간에 직접 연결이 있으면 1, 아니면 0을 넣어 행렬을 만듭니다.
인접 리스트 : 그래프의 노드를 리스트로 표현한 것입니다.
노드들 간에 직접 연결이 되어 있으면 해당 노드의 인덱스에 그 노드를 삽입해주어 표현한 것입니다.
앞서 설명했던 2개의 구현 방식 각각의 상반된 장단점을 가지고 있습니다.
| 인접행렬 | 인접 리스트 | |
| 시간 복잡도 | 2차원 배열 안에 모든 정점들의 간선 정보가 담겨있기 때문에 두 정점에 대한 연결 정보를 조회할 때 O(1) 의 시간복잡도면 가능하다. | 특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래걸린다. |
| 공간 | 필요한 만큼의 공간만 사용하기 때문에 공간의 낭비가 적다. | 무조건 2차원 배열이 필요하기 때문에 필요 이상의 공간이 낭비된다. |
관련 용어 정리
- 정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소입니다.
- 간선 (edge): 정점 간의 관계를 나타냅니다. (정점을 이어주는 선)
- 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻합니다.
- 가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보, ex. 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀 있는 그래프를 뜻합니다.
- 비 가중치 그래프 (unweighted Graph): 연결의 강도가 적혀 있지 않는 그래프를 뜻합니다.
- 무(방) 향 그래프 (undirected graph): 앞서 보았던 내비게이션 예제는 무(방)향 그래프입니다. 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는 것도 가능합니다. 하지만 단방향(directed) 그래프로 구현된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능합니다(혹은 그 반대). 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있습니다.
- 진입 차수 (in-degree) / 진출 차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냅니다.
- 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점입니다.
- 자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다라고 표현합니다. 다른 정점을 거치지 않는다는 것이 특징입니다.
- 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현합니다. 내비게이션 그래프는 서울 —> 대전 —> 부산 —> 서울로 이동이 가능하므로, 사이클이 존재하는 그래프입니다.
7. Tree(트리)
Tree는 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조입니다.
👉나무를 거꾸로 뒤집어 놓은 모양과 매우 유사하다 하여 지어진 이름입니다.
기본 용어 설명
깊이(Depth)
➡트리구조의 루트로부터 하위 걔틍의 특정 노드까지의 깊이를 표현합니다.
레벨(Level)
➡같은 깊이를 가지고 있는 노드들을 묶어서 레벨로 표현할 수 있습니다.
서브 트리(Sub tree)
➡큰 트리의 내부에 트리 구조를 갖춘 작은 트리를 서브 트리라고 합니다.
부모 노드(Parent node)
➡자식 노드를 가진 노드입니다.
자식 노드(Child node)
➡부모 노드의 하위 노드입니다,
형제 노드(Sibling node)
➡같은 부모를 가진 노드입니다.
👆위의 사진은 자식 노드가 최대 두 개인 노드들로 구성된 이진트리(binary tree)입니다
➡트리 구조는 효율적인 탐색을 위해 사용되기도 합니다. 그리고 탐색 할 때 가장 많이 사용하는 트리가 바로 이진트리를 이용한 이진 탐색 트리입니다.
📍이진트리의 특징으로는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징 이 있습니다.
위와 같은 특징을 이용해 빠르고 간편하게 탐색을 할 수 있습니다.
➡루트 노드의 키와 찾고자 하는 값을 비교합니다. 만약 찾고자 하는 값이라면 탐색을 종료합니다.
➡찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행합니다.
➡찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색을 진행합니다.
728x90
반응형
'CS' 카테고리의 다른 글
| [운영체제]UNIX / LINUX 비교하기 (0) | 2023.03.21 |
|---|---|
| [CS]컴퓨터의 기본 구성 (0) | 2022.12.01 |