자료구조란?

자료구조란?

말 그대로 자료(data)를 담는 구조이다. 정확히 설명하자면 데이터 값의 모임, 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. 

 

예> 책장에 책을 꽂아 넣으려고 하는데 책을 알파벳 순서로 꽂아둘 것인지 아니면 책상에 쌓아 올려둘 것인지를 결정하는 것이다.

 

즉, 이런 데이터가 저장된 형태를 결정하는 것

---

자료구조의 분류 

구현과 형태에 따라 분류가 가능하다 

구현 

배열 : 가장 일반적인 구조. 메모리 상에 동일한 타입의 데이터 요소를 연속적으로 저장한다. 자료값을 나타내는 가장 작은 단위가 자료를 다루는 단위이다. (인덱스를 통해 빠르게 접근이 가능+고정된 크기를 가진다.)                               

예> 학생의 점수를 저장하는 배열 [85, 90, 78, 92]와 같이 사용

 

튜플 : 둘 이상의 자료형을 묶음으로 다루는 구조이다.

예> (1, "Alice", 95.5)와 같이 학생의 ID, 이름, 점수를 함께 저장

 

연결 리스트 : 노드를 단위로 한다. 노드는 자료와 다음 노드를 가리키는 참조값으로 구성되어 있다. 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝이다.

예>  A -> B -> C 형태로 노드가 연결된 구조

 

원형 연결 리스트 : 각 노드는 다음 노드를 가리키고, 마지막 노드가 처음 노드를 가리키는 연결 리스트이다.

예> : A -> B -> C -> A와 같이 순환하는 구조

 

이중 연결 리스트 : 각 노드는 이전 노드와 다음 노드를 가리키는 참조값으로 구성된다. 처음 노드의 이전 노드와 마지막 노드의 다음 노드는 없다.

예>NULL <- A <-> B <-> C -> NULL과 같이 양쪽으로 연결된 리스트

 

환형 이중 연결 리스트 : 처음 노드가 이전 노드로 마지막 노드를 가리키고, 마지막 노드가 다음 노드로 처음 노드를 가리키는 이중 연결 리스트이다.

예> A <-> B <-> C <-> A와 같은 구조

 

해시 테이블 : 개체가 해시값에 따라 인덱싱된다.

예> 학생 ID를 키로 하고, 학생 정보를 값으로 저장하는 형태로, 빠른 검색이 가능

 

 

---

형태

형태는 한 번 더 선형 구조와 비선형 구조로 나뉘어진다.

선형 구조 

스택 : 스택 자료구조에 먼저 저장된 것이 꺼내어 쓸 때는 제일 나중에 나온다. 반대로, 가장 최근에 저장된 것이 꺼내어 쓸 때는 제일 먼저 나온다. 만약, 자료들의 나열 순서를 바꾸고 싶다면 스택에 집어 넣었다가 꺼내면 역순으로 바뀐다.

 LIFO(Last In, First Out) 구조

예> 웹 브라우저의 뒤로 가기 버튼은 스택으로 구현

 

 

큐 : 스택과 반대로 큐 자료구조에 먼저 저장된 것이 제일 먼저 나온다. 반대로, 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나온다.

FIFO(First In, First Out) 구조

예> 대기열에서 사람들이 줄을 서는 방식

 

환형 큐 : 한정된 길이 안에서 부수적인 작업 없이 읽고 쓰기를 할 수 있는 큐이다.

예>원형으로 배치된 좌석에서의 대기 시스템.

 

덱 : 양쪽에서 넣기와 빼기를 할 수 있는 일반화된 선형 구조이다.

예> 양쪽에서 물건을 꺼내고 넣을 수 있는 선반.

---

비선형 구조 

그래프 : 꼭짓점과 꼭짓점을 잇는 변으로 구성된다.

예>소셜 네트워크에서 친구 관계를 나타내는 그래프.

 

유향 그래프, 무향 그래프 : 변이 방향성을 갖는지 갖지 않는지에 따른 그래프의 분류이다.무향 그래프의 경우, 순환이 없는 연결 그래프를 뜻한다. 유향 그래프의 경우 변의 방향은 보통 부모를 가리키도록 구현된다.

 

트리 : 뿌리와, 뿌리 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점들로 이루어진 구조. 부모 자식 관계는 변으로 표현된다. + 계층적 구조로, 루트 노드와 자식 노드로 구성

예>파일 시스템의 디렉터리 구조.

 

이진 트리 : 자식이 최대 두 개인 트리. + 각 노드가 최대 두 개의 자식을 가질 수 있는 트리

예>이진 탐색 트리는 정렬된 데이터를 탐색하는 데 유용

 

힙 : 이진트리의 일종으로 이진트리에 어떤 특성을 부여한 것이라 할 수 있다.

 

---

https://velog.io/@kmg2933/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%98-%EC%B0%A8%EC%9D%B4

자료구조와 알고리즘의 차이

https://jindream6128.tistory.com/16

자료구조와 알고리즘 이란?

---

위의 사이트를 참고하였으며 문제시 비공개 처리하도록하겠습니다.