자료구조의 필요성 🏡

프로그램 개발은 건물을 건축하는 것과 비슷하다.
장난감 집이 초보 개발이라면 고층 아파트는 고급 개발과 같다. 초보 개발에서 고급 개발로 넘어가기 위해서는 자료구조가 필요하다. 초보자는 주먹구구 방식이지만, 고급 개발자는 체계적인 방법이 필요하기 때문이다.

자료구조 역할

컴퓨터 프로그래밍에 있어서 가장 기초적인 학문 분야이다.
물론 자료구조를 배운다고 해서 모든 것을 할 수 있는 것은 아니지만 컴퓨터 프로그램의 기본 골격이 된다.
프로그램을 효율적이고 안전하게 동작하기 위해서 반드시 필요하다. (여기서 효율적이라는 것은 빠르게 수행된다는 것이고, 안전하다는 것은 죽지 않는다는 의미이다.)

프로그래밍에 있어서 자료구조 공부는 반드시 필요하다.

자료구조가 없어도 개발을 잘 할 수 있다고 간과할 수 있다.
프로그램의 크기가 작은 경우(학교 과제, 미니 프로젝트), 대형 프로젝트의 초기 단계에는 자료구조가 없어도 개발할 수 있지만, 프로젝트가 커지는 경우 구조적인 결함이 발생할 수 있기 때문에 반드시 자료 구조가 필요하다.

예를 들면, 5층까지 건물을 지었는데 6층을 지으려니 건물이 흔들려서 무너질 수 있다. 처음에는 잘 모르지만 덩치가 커지면 문제가 갑자기 발생할 수 있다.
기본 골격부터 새로 만들어야 할 수 있으므로 반드시 자료구조가 필요하다.

자료구조의 정의

• 프로그램의 구조
  프로그램은 자료와 명령으로 구성된다.

예를 들면, 윈도우 탐색기는 파일 및 폴더의 계층 구조 정보 자료가 저장된다. 특정 폴더의 하위(자식)폴더로 어떤 폴더가 있는지, 각각 폴더에 어떤 파일이 저장되어 있는지에 대한 정보가 저장되어 있다.
파일 복사, 이동 및 삭제하는 등 명령을 수행할 수 있다.
전자사전을 예시로 보면 자료로 단어의 철자, 의미 등의 자료를 저장하고 있고 저장된 단어를 검색하는 명령을 수행한다.

자료구조는 컴퓨터 프로그램이 자료와 명령으로 구성되어 있다고 할 때 저장되는 자료를 보다 효율적으로 저장하는 방식이다.

자료를 아무렇게나 저장하는 것이 아니라 보다 효율적으로 저장한다.

효율적 이라는 것은

1. 메모리를 절약 (저장 공간 효율성)
   가능한 한 작은 메모리의 사이즈로 저장하는 것이 좋다.

2. 프로그램의 수행(실행) 시간 단축
   이왕이면 보다 빠르게 컴퓨터 프로그램이 수행되면 좋다.

프로그램의 수행 시간, 저장 공간을 고려한 효율적 자료구조의 설계를 어떻게 하면 될까 ?

• 프로그램이 어떻게 사용되는지에 따라 결정
  프로그램의 목적, 기능에 부합하는 자료구조를 설계해야 한다.

(예시) 윈도우 탐색기

폴더 구조를 어떻게 보다 효율적으로 저장할 수 있을까?
트리라는 자료구조를 이용하면 좋다.

폴더의 파일 목록은 여러가지 자료 구조가 있겠지만 일반적으로 리스트 자료구조를 많이 사용한다.

폴더 구조에 적합한 트리라는 자료구조가 있고, 목록 스타일에 적합한 리스트라는 자료구조가 있다.

(예시2) 사전 프로그램

사전 프로그램에는 여러가지 저장된 단어들이 있다.
찾고 싶은 단어를 어떻게 하면 신속하게, 효율적(수행 시간 대비)으로 수행하기 위해서 어떤 자료구조가 필요할까?
사전 프로그램과 같이 특정 단어를 찾을 때는 검색에서 제시하는 다양한 자료구조를 사용하면 보다 효율적인 실행이 가능하다.

자료구조의 분류

자료구조를 분류하는 방법은 여러가지가 있지만 일반적으로 형태에 따라 분류한다.

1. 단순구조 (primitive, simple)
2. 선형구조 (linear)
3. 비선형구조 (non-linear)
4. 파일 구조 (file organization)

네가지로 크게 분류할 수 있다.

1. 단순 구조

프로그래밍 언어에서 제공하는 기본적인 데이터 타입을 의미한다.
정수(int), 실수(float, double), 문자(char), 문자열 등.

일반적으로 자료구조에서 얘기하는 자료는 단순구조는 아니다. 보통 자료구조에서 얘기하는 가장 단순한 구조는 선형구조이다.

2. 선형 구조

자료들 사이의 앞뒤 관계가 일대일(1:1)인 경우를 의미한다.
예를 들면, 리스트, 스택, 큐, 덱과 같은 자료구조가 있다.

첫번째 자료 뒤에 두번째 자료가 1개만 있고 두번째 자료 뒤에 세번째 자료가 1개만 있어야 한다.
오직 하나씩 1:1 관계가 선형구조이다.

3. 비선형 구조

선형구조와 달리 자료들 사이의 앞뒤 관계가 계층 구조(트리와 같은 구조) 혹은 망 구조(네트워크 구조)를 가지는 경우
계층 구조에는 트리, 망 구조에는 그래프 등이 있다.

1번째 자료 뒤에 2번째 자료, 3번째 자료가 있다고 가정해보자. 1:2 구조가 된다.
4번째 자료 다음에는 NULL이 있다고 가정하면 이 관계는 1:1이 되지만, 4번째 자료 앞에 2번째와 3번째 자료가 함께 있기 때문에 2:1이 된다.
이처럼 자료들 사이에 1:1이 아닌 경우를 비선형 구조라고 칭한다.

*선형구조와 비선형 구조는 컴퓨터 메모리 상에 저장된다는 가정

4. 파일 구조

보조기억 장치(예를 들면 하드디스크)에 저장되는 파일에 대한 자료구조이다.

---

추상 자료형(ADT)

추상 자료형(Abstract Data Type)은 자료구조를 기술(표현)하는 가장 대표적인 방법 중 하나이다.

정보 은닉(Inforamtion hiding)

• 정보 은닉은 중요한 정보만을 나타내고 중요하지 않은 정보는 숨기는 것이다.

자료구조와 관련해서 정보 은닉은 어디에 필요할까?
개발자 A가 '가'라는 자료구조를 개발했다고 가정해보자.
이런 경우에 개발자 A의 '가' 자료구조를 개발자 B가 사용하고자 한다. 여기서 개발자B는 사용자가 된다.

사용자 관점에서 '가' 자료구조를 사용할 때 무엇이 가장 중요할까? 인터페이스가 가장 중요할 것이다.

그러면, 사용자 관점에서 어떤 것이 가장 중요하지 않을까? 바로 복잡한 내부 구현 로직은 사용자 관점에서 중요하지 않을 것이다.

자신이 실제로 사용하게 될 인터페이스가 중요하지 내부가 어떻게 구현되었는지는 사용자 관점에서는 그다지 중요하지 않다.

자료구조를 기술(표현)한다고 했을 때 어떤 것을 표현해야 할까?

자료구조를 사용할 수 있는 인터페이스를 정의 해야 한다. 혹은 자료구조의 연산들을 정의해야 한다. 내부 로직은 사용자 관점에서는 필요없기 때문이다.

즉, 추상자료형은 정보 은닉! 중요한 정보만 나타내고 중요하지 않은 정보는 숨기는 자료구조를 표현하는 가장 대표적인 방법중 하나이다.

자료형(Data Type)

자료형은 자료와 연산(명령)이 합쳐진 것을 의미한다.

정수 자료형

구분		예
정수 자료형	자료	-2, -1, 0, 1, 2 ..
	명령	더하기, 빼기, 곱하기, 나누기, 나머지 연산

추상 자료형

추상적으로 정의된 자료형을 의미한다.
추상이란? 앞에서 살펴본 정보은닉과 동일하다.
세부적이고 복잡한 것을 생략하고 대표적이고 중요한 것만 나타내는 것이다.

추상 자료형은 자료+연산이면서 중요한 것만 나타낸다.

---

추상 자료형 예시

예를 들어, MyPosition이라는 추상 자료형이 있다고 할 때
이 추상 자료형은 GPS로 사용될 자료 2개(X 좌표와 Y좌표를 정수로 저장하고) 어떠한 명령(연산)을 크게 3가지를 한다.

MyPosition 이라는 추상 자료형을 만들었다.

1. 변경 - modify()

• (INPUT) 위치 자료p, x축 변경 거리, y축 변경 거리 3가지 입력을 받는다.
• (OUTPUT) 출력값은 없다.
• 위치 p에서 x축으로 x만큼 y축으로 y만큼 변경시킨다.

2. 위치 사이 거리 계산 - distance()

• (INPUT) 위치 자료 p1, 위치자료 p2를 입력받는다.
• (OUTPUT) 두 위치 사이의 거리를 출력한다.
• 두 위치 p1, p2 사이의 거리를 구한다.

3. 위치비교 - equal()

• (INPUT) 위치자료 p1, 위치자료 p2를 입력받는다.
• (OUTPUT) TRUE 혹은 FALSE를 반환한다.
• 두 위치 p1, p2가 같은 위치인지 비교한다.

만약에 위에 작성한 MyPosition이라는 자료구조를 개발하는 개발자가 다른 개발자에게 MyPosition 자료구조를 전달했다고 가정해보자.
MyPosition에 대한 추상 자료형을 전달했다면 전달 받은 개발자는 개발을 잘 할 수 있을까? 잘 사용할 수 있다. 이름, 입력, 출력, 설명 명령이 잘 전달되었기 때문에 전달받은 사용자는 잘 사용할 수 있게 된다.

자료구조를 이용하는 사용자 관점에서 장점

• 자료구조의 내부 구현 소스에 대한 분석없이 신속하게 자료구조를 이용할 수 있다.
  예를 들면, 이름, 입력, 출력, 설명 등이 있다.
  가장 중요한 인터페이스 에 대해서만 설명되어 있기 때문이다.

자료구조를 공급하는 개발자 관점에서 장점

• 자료구조를 구현하기 전에 설계도를 미리 그려보는 것이다. (인터페이스에 해당된다)
• 자료구조의 개발자와 사용자 사이의 간섭 문제가 해결된다. (전체 자료구조가 있다면, 추상 자료형은 인터페이스에 해당되는데 개발자와 사용자가 서로 같이 일을 한다면 사용자는 인터페이스만 가지고 일을 하고 개발자는 내부 함수들을 가지고 일을 하기 때문에 간섭 문제가 해결된다.)

---

참고 자료
[자료구조] #01 1장 - 자료구조의 시작