✔ 20241220_과제(자료구조의 종류와 특징 조사 레포트)

자료구조란?

데이터값의 모음이라 함. 정의된 규칙에 의해 나열되며, 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것. 메모리 공간을 효율적으로 사용하는데 필요한 것.

---

프로그램과 자료구조

알고리즘을 작성하고 그에 맞는 자료구조를 선택하는 것으로 나타남. 알고리즘+자료구조=프로그램.

*알고리즘 : 컴퓨터가 무슨 일을 해야 할 지 지시함

*자료구조 : 컴퓨터에게 알고리즘에서 사용하는 자료를 어떻게 저장할지 지시함

---

자료구조와 알고리즘의 관계

알고리즘은 어떤 문제를 해결하기 위해 일련의 절차나 방법을 공식화한 형태로 표현한 것.

문제풀이에 필요한 계산절차 또는 처리과정의 순서를 의미함. (같은 지식 수준을 가진 사람이라면 알고리즘을 보고 같은 결과를 낼 수 있어야 함)

자료구조가 선택되면 그에 적용할 알고리즘이 명확해지기에 자료구조는 효율적인 알고리즘을 사용할 수 있게 함. (알고리즘은 프로그램 명령어들의 집합 이라고도 함)

 

프로그램은 특정 문제를 해결하기 위한 처리 방법과 순서를 기록한 명령어들의 모음.

프로그램이 실행되기 위해 메모리에 올릴 데이터가 필요하고, 이 데이터를 담아내는 방식은 알고리즘.

알고리즘 != 자료구조
알고리즘은 항상 같은 결과를 보장하지만 프로그램은 그렇지 않음.

---

자료구조의 종류

선형 자료구조 - 데이터 요소를 순서대로 정렬

비선형 자료구조 - 데이터를 비연속적으로 연결

---

1. Array (배열)

동일한 타입의 데이터들을 저장하며 고정된 크기를 가짐.

인덱싱이 되어 있어 인덱스 번호로 데이터에 접근할 수 있음. (모든 요소에 빠르게 접근 가능)

배열의 용도
- 특정 요소를 빠르게 읽어야 할 때
- 다차원 데이터를 다룰 때

---

2. Linked List (연결 리스트)

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식. 데이터를 저장하는 자료구조

배열의 크기를 미리 선언해야 하는 배열 리스트와 달리 연결 리스트는 데이터의 숫자만큼만 메모리를 사용하면 되어 메모리 낭비가 적음.

연결 리스트의 용도
- Alt + Tab 을 사용하여 프로그램 간 전환
- 갤러리

---

3. Stack (스택)

"쌓다"라는 의미를 가진 스택은 한 방향으로만 입력할 수 있으며 구조 중간에 값을 끼워 넣어 저장할 수 없음. 같은 크기의 자료를 정해진 한 방향으로만 입력, 저장, 삭제가 가능함.

선입선출 구조로 가장 마지막에 들어온 데이터가 가장 먼저 리턴, 삭제됨.

스택의 용도
- 브라우저이 뒤로가기
- 실행 취소
- 후위 표기법 계산

---

4. Queue (큐)

양 방향에서 입출력이 진행되는 자료구조

선입선출 구조로 가장 먼저 들어온 데이터가 가장 먼저 리턴, 출력됨.

큐의 용도
- 프로세스 관리
- 윈도우 시스템 메세지 처리
- 캐시
- 너비 우선 탐색

---

5. Tree (트리)

노드들이 가지처럼 계층적으로 연결된 비선형 자료구조

최상위 노드, 아래에 다른 하위 노드, 하위노드 아래 또 다른 하위노드가 있는 부모자식 형태

트리의 용도
- 컴퓨터의 디렉터리 구조
- 조직도

---

6. Heap (힙)

이진 트리의 형태로 만들어진 자료구조

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

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

힙의 용도
- 최댓값 혹은 최솟값을 빠르게 찾아내기 위해 사용

---

7. Hash table (해시 테이블)

해시함수를 사용해 변환한 값을 색인으로 삼아 키와 데이터를 저장하는 자료구조

데이터의 크기에 관계없이 삽입 및 검색에 매우 효율적

해시 테이블의 용도
- 데이터베이스 인덱스 구현
- 사용자 로그인 인증

---

8. Graph (그래프)

정점과 간선으로 이루어진 자료구조 (정점간의 관계를 표현하는 조직도)

간선 의 유무는 상황마다 다르며 루트 노드, 부모 자식의 개념이 존재하지 않는 부분에서 트리와 차별점을 둠

* 정점 : 노드라고도 하며 정점에는 데이터가 저장됨. (0, 1, 2, 3)

* 간선 : 링크라고도 하며 노드간의 관계를 나타냄.

그래프의 용도
- GPS에서 위치와 경로를 나타내는데 사용
- 검색 엔진에 의해 웹페이지 및 링크를 나타내는데 사용