자료 구조

Parker.Park·2022년 8월 16일

개념

목록 보기

9/16

이번에 취업 준비를 하게 되면서 새롭게 알게된 개념에 대해 정리해보려고 한다. 이번 시간은 자료구조에 대해서 알아보자.

자료구조란

자료구조란 여러 데이터들을 묶음으로 저장하고, 사용하는 방법이라고 한다. 특정한 상황에 놓인 문제를 해결할 때 적합한 자료구조를 사용하여 데이터를 정리하고 활용하기 때문에 배워야 한다. 데이터를 체계적으로 정리해 두는 것이 데이터를 활용할 때 유리하다고 한다.

그림 출처 : Wikimedia Commons

자료 구조 7가지

기본적인 자료구조 인 배열, 스택, 큐, 열결 리스트, 해시 테이블, 그래프, 트리에 대해서 알아보도록하자. 사이트마다 조금씩 자료명에 대해 차이가 있으니 참고하도록 하자.

배열(Array)

배열은 가장 기본적인 데이터 구조라고 한다. 생성시에는 셀수가 고정되어 있으며 각 셀에는 인덱스 번호가 부여된다고 한다.

장점

복잡한 자료 구조의 기초가 될 수 있다.
원하는 데이터를 효율적으로 탐색/가져올 수 있다.
정렬이 용이하다.

단점
- 데이터를 저장 할 수 있는 메모리크기가 고정되어 있다.(Javascript 기준 2^32 - 1 개를 갖는다.)

데이터를 추가 / 삭제 방법이 비효율적이다.

스택(Stack)

스택은 순서가 보존되는 선형 데이터 구조 유형이라고 한다. 가장 마지막 요소를 제일 먼저 처리하는 LIFO(Last In First Out)매커니즘을 갖고 있다고 한다.

장점

동적인 메모리 크기를 갖고 있다.
데이터를 받는 순서대로 정렬한다.
빠른 런타임을 갖고 있다.
단점
가장 최신 요소만 가져온다.
한번에 하나의 데이터만 처리 가능하다.

큐(Queue)

큐는 먼저 입력된 요소가 먼저 처리되는 FIFO(First In First Out) 매커니즘 이라고 한다.

장점

동적인 메모리 크기를 갖고 있다.
데이터를 받는 순서대로 정렬된다.
빠른 런타임을 갖고 있다.
단점
- 가장 오래된 요소만 가져온다.
- 한번에 하나의 데이터만 처리 가능하다.

연결 리스트(Linked list)

연결 리스트는 메모리에 있는 데이터의 물리적 배치를 사용하지 않는 데이터 구조라고 한다. Index나 위치보다 참조 시스템을 사용한다고 한다. 각 요소를 노드라는 곳에 저장하고, 다음 노드연결에 대한 포인터 또는 주소가 포함된 또 다른 노드에 저장된다고 한다.
연결 리스트에는 단일 연결리스트(Singly-Linked List), 이중 연결 리스트(Doubly-Linked List)가 있다고 한다.

장점
- 새로운 요소들의 추가 및 삭제가 용이하고 효율적이다.
- 배열처럼 메모리에 연속적으로 위치하지 않는다.
- 배열처럼 구조의 재구성이 필요 없다.
- 동적인 메모리 크기를 갖는다.
- 메모리를 더 효율적으로 쓸 수 있기 때문에 대용량 데이터 처리에 적합하다고 한다.
단점
- 배열보다 메모리를 더 사용한다.
- 처음부터 끝까지 순회하기 때문에 원하는 값을 비효율적으로 가져온다.
- 노드를 반대 방향으로 검색할 때 비효율적이다.

해시 테이블 (Hash tables / Hash map)

해시 테이블은 대량의 정보를 저장하고 특정 요소를 효율적으로 검색할 수 있는 복잡한 데이터 구조라고 한다. 테이블 내에 더 작은 서브그룹인 버킷에 키 / 값 (key / value) 쌍(pair)를 저장 한다고 한다.
해시 테이블에서 키를 저장할 때 메모리 공간을 덜 사용하기 위해서 키를 해시 함수를 통해 나온 특정 숫자값인 Hash로 변환하여 저장한다고 한다.

장점
- 새로운 요소들의 추가 / 삭제가 용이하고 효율적이라고 한다.
- 원하는 값의 검색 / 가져오기가 빠르고 효율적이다.

단점
- 충돌이 일어날 수도 있다.(입력된 키의 해시값이 이미 데이터가 저장된 버킷을 가리킬 수 있다고 한다.)

그래프(Graph)

그래프는 정점(vertex)과 정점들을 연결하는 변(Edge)로 구성 되어 있다고 한다.

그림 출처 : [TIL] 자료구조 Graph 이해하기, https://medium.com/

일반적으로 정점은 원으로, 변은 화살표나 선분으로 표현한다고 한다. 변을 화살표로 표현하는 경우해당 방향으로만 이동할 수 있으며, 이러한 그래프를 유향 그래프(Directed graph)라고 한다. 반대로 선분으로 표현되는 경우 양방향 모두 이동이 가능하며 무향 그래프(Undirected graph)라고 한다. 그리고 변의 경우 특정한 수치를 가질 수 있다고 하는데 이를 가중치(Weighted value)라고 한다.

그래프 이론이 최근에 생긴 이론이라 용어가 제각각인 경우가 있다고 한다. 꼭지점을 vertex라고 하지만 컴퓨터 공학에서는 node로 표현되기도 하니 알 필요가 있다.

그림 출처 : Wikimedia Commons

꼭지점의 집합을 V라하고, 변의 집합을 E라고 했을 때 그래프 G는 V와 E의 순서쌍으로 정의 된다고 한다. 이 때 G = (V, E)라고하고 위 그림으로는 아래와 같이 정리 할 수 있겠다.
V = {1, 2, 3, 4, 5}
E = {{1,2}, {1,3}, {1,4}, {2,5}, {3,4}, {4,5}}
(그림을 바탕으로 썼기때문에 정확한 수식이 아닐 수도 있습니다.)

트리

앞에서 그래프가 서로 연결되어 순환 할 수 있다면 이와 반대로 순환하지 않는 그래프를 트리라고 한다. 트리는 노드로 구성된 계층적 자료구조라고 한다. 루트 노드에 child를 추가 하고 그 child에 다시 child를 추가하는 방식으로 트리 구조를 구현할 수 있다고한다.

나머지는 아래 링크에서 참조하도록 하자.
나무위키 : 트리