[탑기공] 자료구조(Data Structure)

 

---

멘토링

 

자료구조에 대한 개념과 분류에 따른 종류를 아는게 중요합니다.
힙(Heap) 자료구조를 포함하여, 모두 충분히 학습하시길 권고 드립니다.
- 자료 구조별 특징, 문제점, 알고리즘 연계성, 동작 방식, Psuedo Code 등

 

자료구조의 개념

 

다양한 자료를 효율적으로 표현하고 활용할 수 있도록
자료의 특성과 사용 용도를 고려하여 조직적, 체계적으로 정의하고 
자료를 컴퓨터의 기억장치 내에 저장하는 방법 

 

자료구조의 분류

 

자료구조는 크게 선형 구조와 비선형 구조로 나눌 수 있습니다.

[두음] 배리스큐 트그

배열, 리스트, 스택, 큐, 트리, 그래프

정말 중요합니다. 필수 암기!!!

 

선형 구조

 

물리적 설계자료들이 직선 형태로 나열되어 자료들 간의 순서를 고려한 구조로
전후/인접/선후 자료들간의 1:1 관계로 나열되어 있는 형태
 - 배열, 선형 리스트, 연결 리스트, 스택, 큐, 데크 등

 

비선형 구조 

 

한 자료 뒤에 여러 개의 자료들이 존재하는 구조로 인접/전후 자료들 간의 
1:다 또는 다:다 관계로 배치되어 계층 구조나 망구조의 특별한 형태
- 트리, 그래프

 

자료 구조의 분류

 

출처 : 탑싯 에센스

 

순차 자료 구조와 연결 자료 구조의 비교

 

출처 : 탑싯 에센스

2022.12.15 - [(Pilot) 탑기공/소프트웨어 개발] - 스택(Stack) - "스리포 3!4!"

스택(Stack) - "스리포 3!4!"

 

2022.12.16 - [(Pilot) 탑기공/소프트웨어 개발] - 큐(Queue) - "큐피포"

큐(Queue) - "큐피포"

 

2022.12.18 - [(Pilot) 탑기공/소프트웨어 개발] - 트리(Tree) 자료구조

트리(Tree) 자료구조

 

2022.12.19 - [(Pilot) 탑기공/소프트웨어 개발] - 그래프(Graph) 자료구조

그래프(Graph) 자료구조

 

자료 구조의 활용

 

데이터의 정렬(Sort), 검색(Search), 파일 편성 및 인덱스 등에서 주로 활용

 

자료 구조 유형별 활용

 

스택 - 깊이 우선 탐색(DFS), 큐 - 너비 우선 탐색(BFS), 힙 - 우선순위 큐, 
트리 - 이진 탐색 트리 (BST)
그래프 - 최단 경로 알고리즘

 

리스트 : 배열의 구현, DBMS 인덱스, 탐색이나 정렬과 같은 문제 등

스택(Stack) : 인터럽트 처리, 재귀 프로그램의 순서 제어, 서브루틴의 복귀 번지 저장, 
후위(Postfix) 표기법으로 표현된 수식의 연산, 덱스트 에디터 Undo 기능 등

큐(Queue) : 운영 체제의 작업 스케쥴링, 대기 행렬의 처리, 
비동기 데이터 교화(파일 I/O, Pipes, Sockets), 키보드 버퍼 이용, 스풀(Spool) 운용 등

데크(Deque) : 스택과 큐의 장점만 활용한 자료구조로 스택과 큐 관련 분야에서 활용

트리 : 탐색이나 정렬과 같은 문제, 문법의 파싱, 허프만 코드, 결정 트리, 게임 등

그래프 : 컴퓨터 네트워크(근거리 통신망, 인터넷, 웹 등), 전기회로 분석,
이항 관계, 연립 방정식 등

출처 : 탑싯 에센스

---

기출 문제

 

(관리 125-1-4)
선형 자료구조와 비선형 자료구조

 

(관리 124-3-2)
자료구조 Heap의 2가지 유형인 Max-heap과 Min-heap을 설명하시오.

 

(관리 90-1-10)
자료구조 Heap을 설명하고, Heap의 2가지 유형인 max-heap과 min-heap의 차이점을 
설명하시오.

 

참고 자료

탑싯 에센스 - 소프트웨어 개발

자료 구조 힙(heap)에 대해 잘 정리되어 있는 블로그입니다. 
우선 순위 큐를 구현할때 가장 효율적인 자료구조가 힙(heap)입니다.
힙(heap)은 완전 이진 트리의 일종으로 여러 개의 값들 중에서 
최대값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이며, 
종류로는 최대 힙(Max-heap)과 최소 힙(Min-heap) 있습니다.

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

[자료구조] 힙(heap)이란 - Heee's Development Blog

순차 자료 구조와 연결 자료 구조에 대해 잘 설명되어 있는 블로그입니다.

https://computer-science-student.tistory.com/72

[c++] 순차 자료 구조와 연결 자료 구조

https://itwiki.kr/w/자료%20구조 

IT위키

자료구조 분류에 대해 설명되어 있는 블로그입니다.
[두음] 단선비파
단순구조, 선형 구조, 비선형 구조, 파일 구조 4개로 분류되어 있습니다.

https://0verc10ck.tistory.com/1

DS01 - 자료구조의 정의와 분류