🤔 목적
컴퓨터공학의 기초가 되는 cs지식을 되새기면서 이 후 있을 기술면접을 대비 하고자한다.
자료구조(DataStructure)의 시리즈를 포스트하기 전에 자료구조의 정의와 개념을 정리하고 필요한 이유를 정리하고 시작하려고 한다.
자료구조(DataStructure) 란?
정의: 컴퓨터과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다.
즉, 자료구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다.
신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다. 이러한 자료구조의 선택문제는 대개 추상 자료형의 선택으로부터 시작하는 경우가 많다고 한다.
효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다.
자료구조의 필요성
자료구조는 적은 수의 데이터를 관리하기 위해 고안된 것이 아닌 수 많은 데이터를 처리하기 위해 고안된 것이다 왜냐하면 데이터를 처리하는 시간과 크기를 줄여 데이터를 처리하는데 더 적은 크기와 더 적은 시간이 필요하게 하는 역할을 수행하기 때문이다.
따라서 자료구조가 중요한 이유는 프로그램 내에서 자료를 가장 효율적으로 처리하기 위함이고, 보다 좋은 프로그래밍을 하기 위함이다.
자료구조의 종류
자료의 특성과 크기, 주요 사용법과 수행하는 연산의 종류, 구현에 필요한 기억 공간 크기에 따라 여러 가지 종류의 자료구조 중 하나를 선택할 수 있다. 자료구조의 종류로는 자료형의 따라 분류하는 단순 구조와 자료간 관계가 1 대 1인 선형구조, 1 대 다 혹은 다 대 다 구조인 비선형 구조, 마지막으로 파일 구조가 존재한다.
자료 구조의 종류를 설명하기전 선형 구조와 비선형 구조를 알 필요가 있다.
선형 구조와 비선형이란?
선형 구조
- 자료를 구성하는 데이터를 순차적으로 나열시킨 형태
비선형 구조
- 하나의 자료 뒤(안)에 여러개의 자료가 존재할 수 있는 형태
자료구조의 종류를 선형 구조와 비선형 구조로 나누어 종류를 말하자면 아래와 같이 나오게 분류된다.
(자세한 사항은 [cs] DataStructure 시리즈의 포스트를 참고하면된다.)
1. 선형 구조
배열(Array)
가장 일반적인 구조이며, 메모리 상에 같은 타입의 자료가 연속적으로 저장된다. 자료값을 나타내는 가장 작은 단위가 자료를 다루는 단위이다.
연결리스트(Linked List)
노드를 단위로 하며, 노드는 자료와 다음 노드를 가리키는 참조값으로 구성되어 있다. 노드가 다음노드로 아무것도 가리키지 않으면 리스트의 끝이다.
스택(Stack)
스택 자료구조에 먼저 저장된 것이 꺼내어 쓸 때는 제일 나중에 나온다. 반대로, 가장 최근에 저장된 것이 꺼내어 쓸 때는 제일먼저 나온다. 만약, 자료들의 나열 순서를 바꾸고 싶다면 스택에 집어 넣었다가 꺼내면 역순으로 바뀐다.
큐(Queue)
스택과 반대로 큐 자료구조에 먼저 저장된 것이 제일 먼저 나온다. 반대로, 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나온다.
데크(Deque)
두 개의 포인터를 사용하여 양쪽에서 삭제와 삽입을 발생 시킬 수 있다.
즉, 양쪽에서 넣기와 빼기를 할 수 있는 일반화된 선형 구조이고, 큐와 스택을 합친 형태로 생각할 수 있다.
해쉬(Hash)
해시 테이블(hash table), 해시 맵(hash map), 해시 표는 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다.
기본적으로 선형 구조로 구현되지만, collision 등의 문제를 해결하기 위해서 구현에 따라서 비선형 구조로 구현되기도 한다.
2. 비선형 구조
그래프(Graph)
꼭짓점과 꼭짓점을 잇는 변으로 구성되며, 단순히 노드(node,N)와 그래프를 연결하는 간선(edge, E)을 하나로 모아놓은 자료구조
즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조이다.
- 방향성(Directed) / 무방향성(Undirected)
변이 반향성을 갖는지, 갖지 않는지에 따른 그래프의 분류이다. 무향 그래프의 경우, 순환이 없는 연결 그래프를 뜻한다. 유향 그래프의 경우 변의 방향은 보통 부모를 가리키도록 구현된다.
트리(Tree)
뿌리와 뿌리 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점들로 이루어진 구조, 부모 자식관계는 변으로 표현된다.
- 이진트리(Binary Tree)
자식이 최대 두 개인 트리 - 힙(Heap)
이진트리의 일종으로 이진트리에 어떤 특성을 부여한 것이라 할 수 있다.
References (참고 자료)
