자료구조 및 자료구조의 유형, 자료구조를 알아야 하는 이유

데이터 구조(DSA_Data Structure Architecture) 및 데이터 구조의 유형, 알고리즘에서 데이터 구조를 왜 알아야 할까?

 

데이터 구조란 무엇인가?

1. 데이터 구조는 데이터를 저장하고 구성하는 데 사용되는 저장소이다.

2. 효율적으로 접근하고 변경할 수 있도록 컴퓨터에서 데이터를 할당하는 방법이다.

3. 요구 사항 및 프로젝트에 따라 프로젝트에 적합한 데이터 구조를 선택하는 것이 중요하다.

4. 예를 들어 데이터를 메모리에 순차적으로 저장하려는 경우 배열 데이터 구조로 이동할 수 있다.

5. 데이터 구조와 데이터 유형은 약간 다르다. (데이터 유형은 type이라고 생각하면 편하다)

6. 데이터 구조는 특정 순서로 정렬된 데이터 유형의 모음이다.

 

알고리즘에서 데이터 구조를 왜 알아야 할까?

1. 데이터 구조에 대한 지식은 각 데이터 구조의 작업을 이해하는 데 도움이 된다.

2. 메모리 및 시간 효율적인 코드를 작성하는 데 도움이 된다.

3. 위를 바탕으로 프로젝트에 적합한 데이터 구조를 선택할 수 있다.

 

---

 

데이터 구조의 유형

기본적으로 데이터 구조는 두 가지 범주로 나뉜다.

1. 선형 데이터 구조
2. 비선형 데이터 구조

1. 선형 데이터 구조

1. 선형 데이터 구조에서 요소는 차례로 순서대로 배열된다.

2. 요소(element)는 특정 순서로 배열되기 때문에 구현하기 쉽다.
3. 프로그램의 복잡성이 증가하면 운영 복잡성으로 인해 선형 데이터 구조가 최선의 선택이 아닐 수 있다.
4. 널리 사용되는 선형 데이터 구조는 다음과 같다.

 

1-1. 배열 데이터 구조

1. 배열에서 메모리의 요소는 연속 메모리에 배열된다.

2. 배열의 모든 요소는 동일한 유형이다.

3. 배열 형태로 저장할 수 있는 요소의 종류는 프로그래밍 언어에 따라 결정된다.

1-2. 스택 데이터 구조

1. 스택 데이터 구조에서 요소는 LIFO 원칙에 따라 저장된다.
2. 스택에 가장 빨리 저장된 요소가 마지막에 제거된다.

3. 스택에 마지막에 저장된 요소가 가장 먼저 제거된다.

4. 스택에서 작업은 한쪽 끝(보통 맨 위)에서만 수행할 수 있다.

5. 동전 넣은 통이나 일반적인 수건넣는 통을 생각하면 편하다.

 

1-3. 큐 데이터 구조

1. 스택과 달리 큐 데이터 구조는 큐에 저장된 첫 번째 요소가 먼저 제거되는 FIFO 원칙에서 작동한다.

2. 큐에 가장 빨리 저장된 요소가 가장 먼저 제거된다.

3. 큐에 마지막에 저장된 요소가 마지막에 제거된다.

4. 대기열의 첫 번째 사람이 먼저 티켓을 받는 매표소나 은행의 사람들 대기열처럼 작동한다.

 

1-4. 연결 리스트 데이터 구조

1. 연결된 목록 데이터 구조에서 데이터 요소는 일련의 노드를 통해 연결된다.

2. 각 노드에는 데이터 항목과 다음 노드에 대한 주소가 포함된다.

 

2. 비선형 데이터 구조

1. 선형 데이터 구조와 달리 비선형 데이터 구조의 요소는 순서가 없다.

2. 하나의 요소가 하나 이상의 요소에 연결되는 계층적 방식으로 배열된다.

3. 비선형 데이터 구조는 그래프 기반 데이터 구조와 트리 기반 데이터 구조로 더 나뉜다.

 

2-1. 그래프 데이터 구조

1. 그래프 데이터 구조에서 각 노드를 꼭지점이라고 하며 각 꼭지점은 간선을 통해 다른 꼭지점과 연결된다.

2. 인기 그래프 기반 데이터 구조: 스패닝 트리 및 최소 스패닝 트리, 강력하게 연결된 구성 요소, 인접 행렬, 인접 목록

 

2-2. 트리 데이터 구조

1. 그래프와 마찬가지로 트리도 꼭지점과 가장자리의 모음이다.

2. 트리 데이터 구조에서는 두 꼭지점 사이에 하나의 간선만 있을 수 있다.
3. 인기 트리 기반 데이터 구조: 이진 트리, 이진 검색 트리, AVL 트리 , B-트리 , B+ 트리 , 레드-블랙 트리 , 선형 대 비선형 데이터 구조

---

 

선형 데이터 구조 비선형 데이터 구조의 차이점

선형 데이터 구조	비선형 데이터 구조
데이터 항목은 차례로 순차적으로 정렬된다.	데이터 항목은 비순차적 순서(계층적 방식)로 정렬된다.
모든 항목은 단일 레이어에 있다.	데이터 항목은 서로 다른 계층에 있다.
한 번의 실행으로 통과할 수 있다.    첫 번째 요소에서 시작하면 단일 패스에서 모든 요소를 ​​순차적으로 순회할 수 있다.	여러 번의 실행이 필요하다.   첫 번째 요소에서 시작하면 한 번에 모든 요소를 ​​순회하는 것이 불가능할 수 있다.
메모리 사용률이 효율적이지 않다.	서로 다른 구조는 필요에 따라 서로 다른 효율적인 방식으로 메모리를 활용한다.
시간 복잡도는 데이터 크기에 따라 증가한다.	시간 복잡도는 동일하게 유지된다.
예: 배열, 스택, 대기열	예: 트리, 그래프, 지도