[자료구조] 자료구조의 필요성, 자료구조 정의 및 분류, 추상자료형이란?

 

0. 자료구조의 필요성 : 자료구조를 왜 배워야 하는가 ?

 

프로그램 개발은 건물 하나를 건축하는 것과 비슷하다.

함수를 하나씩 만들어가면서 프로그램을 만드는 것 ,

건물을 위해 하나씩 만드는것.

 

초보개발에서 고급 개발자가 되기 위해서 필요한 것이 자료구조다!

 

초보 개발단계에서는 대부분 주먹구구식으로 개발을 하는데

고급 개발은 체계적인 방법에따라서 개발을 하게 되는 것이므로

 

자료구조의 역할

- 컴퓨터 프로그래밍에 있어서 가장 기초적인 학문분야

- 컴퓨터 프로그램의 기본 골격이다

-> 프로그램이 효율적이고 안전하게(죽지않고) 동작하게 하기 위해서 반드시 필요하다.

 

프로그램의 크기가 작은 경우나 대형 프로젝트의 초기 단계에서 간과하기 쉽다.

이는 이후에 점점 진행되었을때에 구조적인 결함이 발생될 수 있다

그렇게 되면 결국 기본 골격 부터 다시 만들어야하는 문제가 발생한다.

 

---

1. 자료구조의 정의

- 프로그램의 구조 : 자료 + 명령

 

예를 들어,

윈도우 탐색기의 경우

파일의 복사 , 이동 및 삭제 라는 명령과

파일 및 폴더의 계층 구조 정보 라는 자료를 가지고 있다.

 

자료구조란 결국 이 자료를 더 효율적으로 저장하는 방식을 말한다.

 

효율적으로 저장하는 것 ? 

- 메모리(저장 공간) 절약

- 프로그램 수행 시간 단축

 

프로그램의 수행 시간 혹은 저장 공간을 고려한 효율적인 자료구조의 설계는

프로그램이 어떻게 사용되는지에 따라 결정되며

프로그램의 목적 및 기능에 부합하는 자료구조 설계를 해야한다.

 

예시 1) 윈도우 탐색기

- 폴더구조 ( 트리 )

- 파일 목록 ( 리스트 )

 

예시 2) 사전 프로그램 ( 검색 )

여러 자료들중 찾고 싶은 단어를 효율적으로 보다 빨리 찾을 수 있도록 하는 것.

---

2. 자료구조의 분류

- 자료(data)의 형태에 따른 분류

• 단순구조
• 선형구조
• 비선형 구조
• 파일 구조

1) 단순구조

: 프로그래밍 언어에서 제공하는 기본적인 데이터 타입(int, float, char 등)

주로 C언어에서 다루게 됨

 

2) 선형구조

: 자료들 사이의 앞 뒤 관계가 일대일인 경우

(list, stack, Queue, Deque 등)

 

null - [0] 첫번째 자료 - [1] 두번째자료 - [2] 세번째 자료 - null

→ 앞뒤 자료가 1:1 관계를 이루고 있음.

 

3) 비선형 구조

: 자료들 사이의 앞뒤 관계가 계층구조 혹은 망 구조를 가지는 경우

(tree, graph 등)

-앞뒤 관계가 1번째 Data의 경우 1: 2 ( 1:1이 아님) / * 2번째와 3번째 Data는 컴퓨터메모리 상에서 저장된다는 가정

 

4) 파일구조

: 보조기억장치에 저장되는 파일에 대한 자료구조

---

3. 추상자료형(Abstract Data Type, ADT)

: 자료구조를 표현(기술)하는 가장 대표적인 방법 중 하나

 

- 정보 은닉(Information Hiding)

: 중요한 정보만을 나타내고, 중요하지 않은 정보는 숨기는 것.

사용자 관점에서 내부구현 로직보다 실제로 사용하게 될 인터페이스가 중요!

 

-> 자료구조를 사용할 수 있는 인터페이스를 잘 정의 해야하는것 / 자료구조의 연산들의 정의

 

- 자료형(Data Type)

자료 + 연산(명령) = 자료형

 

- 추상자료형

: 추상적으로 정의된 자료형

 

추상(Abstaraction) =정보은닉과 비슷한 개념

- 세부적이고 복잡한 것을 생략

- 대표적인것, 중요한 것(인터페이스)만을 나타냄

 

- 자료구조를 이용하는 사용자 관점

자료구조의 내부 구현 소스에 대한 분석없이 신속하게 자료구조를이용 가능.

-> 이름, 입력 ,출력 등을 기술하여 전달.

 

- 자료구조를 공급하는 개발자 관점

자료구조를 구현하기 전에 설계도를 미리 그려보는 것.

자료구조의 개발자와 사용자 사이의 간섭 문제가 해결됨. 

설계도 예시

---