Data Structure Intro

스프린트는 크게 네 가지 부분으로 나뉘어 진행됩니다.

1. 스택과 큐

   스택과 큐는 실생활에서도 흔히 볼 수 있는 형태의 자료구조로, 이번 스프린트에서 접하게 될 자료구조들 중 가장 간단한 자료구조입니다. 서로 비슷하면서도 다른 쌍둥이 같은 두 자료구조는, 간단한 만큼 많은 부분에서 활용 되므로 중요도는 가장 높습니다.

2. 연결 리스트와 해시 테이블

   배열처럼 여러 데이터를 선형적으로 담을 수 있는 연결 리스트에 대해 배워봅니다. 배열과 어떤 부분이 다른지에 대해 생각하면서 공부하면 도움이 될 것입니다. 또한 해시 테이블은 이번 스프린트에서 배울 자료구조들 중 가장 어렵고 다른 성격을 가지는 자료구조입니다. 공부하고 직접 구현할 땐 어렵게 느껴지겠지만, 해시 테이블의 장점을 직접 경험하게 된다면 모든 곳에서 해시 테이블을 남용하게 될 지도 모릅니다.

3. 그래프, 트리, 이진 탐색 트리

   그래프, 트리, 이진 탐색 트리는 모두 그래프의 형태를 가지는 자료구조입니다. 그래프는 그 형태의 특성 때문인지, 수학적인 부분에서만 사용되며 사용하기 어렵다는 오해를 자주 받습니다. 그래프와 트리를 공부하며 이런 오해들을 풀고 실생활의 무수히 많은 문제를 해결하는데 적용할 수 있다는 것을 느껴 보시기 바랍니다.

4. 시간 복잡도

   Pre Course 마지막에 배웠던 시간 복잡도는 단순한 이론적인 지식이 아닙니다. 알고리즘을 표현하는 도구입니다. 우리가 다양한 자료구조와, 자료구조에서 일어나는 특정 작업들을 작성하고 나면, 이게 어떠한 (시간적) 효율을 갖고 있는지 알 수 있어야 합니다. 그러기 위해서는 시간 복잡도에 대한 이해가 필요합니다.

설정한 것에 대한 질문을 잘 할 수 있게 하는 것을 목표로 정하여 글을 정리하려고 한다.

 

우선 배우기 전에 PRE에서 배운 Class에 대한 이해를 하는지 봐야한다.

Data Structures

자료(Data)

문자, 숫자, 소리, 그림, 영상 단어 등의 형태로 된 의미 단위이다. 자료를 의미있게 정리하면 정보가 된다.

 

자료 구조란 ?

사전적인 의미는 자료의 집합을 의미하며, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며, 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것이다. 짧게 표현한다면 여러 데이터들의 묶음을 어떻게 저장하고 사용할지 정의한 것으로 보면된다.

그렇다면 "왜 사용하는가?"에 대한 질문을 할수있다. 목적은 명확하다. 자료를 더 효율적으로 저장하고, 관리하기 위해 사용하며, 잘 선택된 자료구조는 실행시간을 단축시켜주거나 메모리 용량의 절약을 이끌어 낼 수 있다.

 

자료구조의 특징

1. 효율성

자료구조를 사용하는 목적은 효율적인 데이터의 관리 및 사용입니다. 따라서 적절한 자료구조를 선택하여 사용한다면 업무의 효율이 올라갈 것입니다. 한가지 예를 들어보자면 검색에 대한 알고리즘을 구현할때, 데이터의 양이 많다면 순차 검색(Linear Search)를 사용하는 것 보다 이분 검색(Binary Search)를 활용하는것이 더 효율 적일 것입니다. 왜냐하면 학생이라는 테이블에 학생에 대한 데이터가 100만개 있다고 할때, 순차 검색으로 데이터를 검색하게 되면 운이 좋을때는 1번의 연산으로 찾을 수 있겠지만, 운이 없을경우에는 100만번의연산을 거쳐야 할 것입니다. 이에 반해 이분 검색은 연산의 횟수가 훨씬 줄어들죠. 이와같이 목적에 맞는 자료구조를 사용하는것이 효율적입니다.

 

2. 추상화

추상화란 복잡한 자료, 모듈, 시스템 등으로 부터 핵심적인 개념만 간추려 내는 것입니다. 자료구조를 구현할 때 중요한 것은 어느 시점에 데이터를 삽입할 것이며, 어느 시점에 이러한 데이터를 어떻게 사용할것인지에 대해서 초점을 맞출수 있기 때문에 구현 외적인 부분에 더 시간을 쏟을 수 있습니다. 알고리즘 자체에는 중점을 두지 않습니다.

 

마찬가지로 자료구조 내부의 구현은 중요하지 않습니다. 어떻게 구현했는지 보다 어떻게 사용해야 하는지를 알고 있어야 합니다.

 

예를들어 스택(Stack)의 경우 먼저 들어간것이 나중에 나오는 FILO(First In Last Out)의 형태를 가지고 있습니다. 그리고 push() 함수를 이용해서 데이터를 삽입할 수 있고, pop() 함수를 이용해서 데이터를 추출할 수 있습니다. 그 함수 내부 구현이 어떻게 되었는지는 중요하지 않습니다. 사람마다 다른 코드를 작성할 것이고, 사용 언어, 개발 툴등 환경적인 변수에 의해서 다른 코드가 나올 것이기 때문에 추상적인 개념에 대해서만 이해하고 있다면 사용할 수 있습니다.

 

3. 재사용성

자료구조를 설계할때 특정 프로그램에서만 동작하게 설계하지는 않습니다. 다양한 프로그램에서 동작할 수 있도록 범용성 있게 설계하기 때문에 해당 프로젝트가 아닌 다른 프로젝트에서도 사용할 수 있습니다.

 

자료구조의 분류

자료구조는 크게 선형 자료구조와 비선형 자료구조로 나뉩니다. 선형 자료구조의 경우 데이터가 일렬로 나열되어 있는 것을 뜻하고, 비 선형 자료구조는 특정한 형태를 띄고 있는 것을 뜻하는데, 각각에 해당하는 자료구조는 아래와 같습니다.

어떤 자료 구조가 있는가?

Stack, Queue, Linked List, Hash Table, Graph, Tree, Binary Search Tree 이 있다.

 

선형구조로 되어있는 것은 배열, 연결 리스트, 스택, 큐등이있으며, 비선형 구조에는 트리, 그래프가 있다..