자료 구조(Data Structure) 꼭 알아야 하는가

 

자료 구조란?

자료 구조는 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 말한다.

또는 특정 모양 자체를 자료구조라고도 부른다!

백엔드를 지망한다면 한번쯤 자료구조에 대해 들어봤을 것이다. 그렇다면 자료 구조를 실제로 적용한 경험이 있는가?

분명 개발에 입문한지 얼마 안된 사람들은 그런 경험이 없을 것이라 생각된다.

 그렇다면 배울 필요가 없는가?

 

이에 대한 대답은 "꼭 알고 있어야 한다!" 이다

 

물론 나도 아직까지 코드를 칠 때나, 문제를 풀 때 자료 구조를 많이 적용해본 경험은 없다.

하지만 앞으로 큰 프로젝트를 진행한다거나 많은 양의 데이터를 다룰 때, 효율적으로 관리하기 위해 자료 구조의 지식은 꼭 필요해진다!

 

그 이유를 다음 예에서 찾아보자

 

당신은 공간이 한정된 책장에 여러가지의 종류의 책을 꽂으려고 한다.

이 책장을 효율적으로 사용하기 위한 방법은 여러가지가 있다. 

규칙없이 책을 다 집어 넣는다면, 당신은 책을 찾기위해서 책장을 처음부터 끝까지 훑어봐야 할것이다.

좀 더 효율적으로 책을 찾고 싶다면, 글자 순서대로 책을 꽂으면 된다. 책의 제목만 알고있다면 책을 찾기가 수월할 것이다.

하지만 어떤 장르의 책을 찾고싶을 때 위의 방법은 크게 도움이 되지 않을 수 있다.

이때는 책을 분야별로 책장에 정리해서 넣으면 된다!

 

위의 예시는 책장 = 메모리, 책 = 데이터 으로 유사하게 비유할 수 있다.

 

모든 목적에 맞는 자료구조는 없다. 따라서 각 자료 구조가 갖는 장점과 한계를 잘 아는 것이 중요하다

예시에서도 책장 안에 다양한 이유와 목적을 가지고 책을 진열할 수 있었다

단, 자료 구조에서는 메모리 공간의 효율뿐만 아니라 실행 시간의 효율성(시간 복잡도)도 따진다.

 

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

알고리즘은 어떤 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것. 문제 풀이에 필요한 계산절차 또는 처리과정의 순서다.

알고리즘의 중요한 특징은 같은 지식수준을 가진 사람이라면 그 알고리즘을 보고 누구나 같은 결과를 낼 수 있어야 한다.

 

보통 자료 구조가 선택되면 그에 적용할 알고리즘은 거의 명확해진다. 즉. 자료 구조가 효율적인 알고리즘을 사용할 수 있게 함으로 자료 구조와 알고리즘은 매우 밀접한 관계를 가질 수 밖에 없다.

 

위의 예를 다시 생각해 보면, 책장에 진열된 책들을 어떤 순서나 규칙을 가지고 찾을 지에 대한 방법이라고 생각하면 된다. 왼쪽부터 순서대로 찾을 수도 있고, 역순으로 찾을 수도 있고, 중간부터 찾을 수도 있다.

 

여기서 만약 "코어 자바스크립트"라는 책을 찾아야 할 때 책장에 진열되어 있는 구조에 따라 효율적으로 책을 찾는 방법이 달라지게 된다.

제목 순으로 진열되어 있다면 역순으로 찾는 방법을 선택하게 되고, 분야 별로 진열되어 있다면 it 서적 쪽을 먼저 찾게 될 것이다.

 

즉, 위와 같이 보통은 자료 구조의 선택 -> 효율적인 알고리즘의 선택이 된다.

또한 알고리즘을 프로그램 명령어들의 집합이라고도 한다.

프로그램은 특정 문제를 해결하기 위한 처리 방법과 순서를 기록한 명령어들의 모음이다. 이 프로그램이 실행되기 위해서는 메모리에 올릴 데이터가 필요하며 이 데이터들을 담아내는 방식은 자료구조다.

 

즉, 넓은 의미에서 자료구조 + 알고리즘(+a) = 프로그램이라고 할 수 있다.

 

그렇다고 프로그램 = 알고리즘은 아니다. 간단한 예로 알고리즘은 항상 같은 결과를 보장하지만 프로그램은 그렇지 않을 수 있다.

 

---

 

자료 구조의 특징

 작업의 효율성, 추상화, 재사용성을 증가시키기 위하여 상황에 따른 적절한 자료구조를 선택할 필요가 있다. 대규모 데이터를 관리 및 활용하는 경우에는 특히 더 중요하다고 볼 수 있다.

(1) 효율성 

- 상황에 맞는 자료구조를 사용하면 데이터 처리의 효율성이 높아진다.

예를 들어, 자동차 테이블에 자동차 데이터가 10만개가 있다고 하자. 원하는 자동차를 찾기위해서 검색에 대한 알고리즘을 구현해야 하는데, 첫 번째 부터 마지막 인덱스까지 순차적으로 검색하는 순차 검색(Linear Search)보다 이분 검색(Binary Search)를 활용하는 것이 훨씬 더 효율적일 것이다. 만약에 찾는 데이터가 가장 마지막 인덱스에 있다면 순차 검색은 10만번의 연산을 거쳐야 한다. 그에 반해 이분 검색은 연산의 횟수가 훨씬 줄어든다. 이와같이 목적에 맞는 자료구조를 사용하는 것이 효울적이다.

(2) 추상화

-  추상화란 복잡한 자료, 모듈, 시스템 등으로부터 핵심적인 개념 또는 기능을 간추리는 것을 말한다. 자료구조를 이용할 때 자료구조를 구현하는 자세한 작동원리보다는 사용 방법에 대해서 알고만 있으면 된다. 즉, 언어에 따라 구현한 코드가 차이가 있어도 자료구조의 핵심적인 기능에 대해서 알고 있으면 되기 때문에 언어에 종속적이지 않다는 특징을 갖는다. 

(3) 재사용성

-  자료구조를 이용하여 데이터를 처리할 경우 해당 자료구조의 인터페이스만 이용하여 데이터를 처리하도록 하므로 모듈화가 가능하다. 이는 자료구조를 설계할 때 특정 프로그램에 맞춰 설계하지 않고, 다양한 프로그램에서 사용될 수 있도록 범용화에서 설계했기 때문에 가능하다.

 

자료구조 종류

자료구조는 크게 선형과 비선형으로 나뉜다.
선형 자료구조의 경우 데이터가 일렬로 나열되어 있는 것을 의미한다.
비선형 자료구조의 경우 특정한 형태를 띄는 것을 의미한다.

자료구조 분류

단순 데이터 구조

- 프로그래밍에서 사용되는 기본 데이터 타입

• 정수(int)
• 실수(float)
• 문자(char)
• 문자열(double)

 

선형 구조

• 배열(Array)
  가장 일반적인 구조이며, 메모리 상에 같은타입의 자료가 연속적으로 저장된다. 자료값을 나타내는 가장 작은 단위가 자료를 다루는 단위이다.

 

• 스택(Stack)
  스택은 박스쌓기에 비유할 수 있다. 아래에서부터 위로 차곡차곡 쌓은 후 데이터를 삭제하기 위해서는 위에서부터 먼저 제거해야 한다. 이런 구조를 선입후출(FILO) 혹은 후입선출(LIFO) 구조라고 한다.

 

• 큐(Queue)
  큐는 대기줄과 같이 먼저 온 사람이 먼저 들어가는 것처럼 선입선출(FIFO) 구조를 가지고 있다.

 

• 연결리스트(Linked List)
  연결 리스트는 동적 데이터 구조이다. 목록의 노드 수는 고정되어 있지 않으며 필요에 따라 늘리거나 줄일 수 있다. 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝이다.

 

비선형 구조

• 트리(Tree)
  부모 노드 밑에 여러 자식 노드가 연결되고, 자식 노드가 다시 부모 노드가 되어 각각의 자식 노드에게 연결되는 재귀적인 형식의 자료구조

• 그래프(Graph)
  그래프는 노드(Node)와 간선(Edge)로 표현되며 이때 노드를 정점(Vertex)이라고도 한다.

 

 

 

 

 

 

 

참조 - https://bnzn2426.tistory.com/115