자료 구조

Parker.Park·2022년 8월 16일
0

개념

목록 보기
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를 추가하는 방식으로 트리 구조를 구현할 수 있다고한다.

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

마치면서

자료 구조 몇가지에 대해서는 알고 있었던 것도 있었고, 이번에 새롭게 알게된 내용도 있었다. 이걸 알고리즘으로 사용하는 것은 새로운 방법일 것이다.

참조

[[자료구조] 자료구조란? (자료구조를 배우는 이유), HANAMON, 2022년08월22일 접속]
https://hanamon.kr/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EB%9E%80-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EB%A5%BC-%EB%B0%B0%EC%9A%B0%EB%8A%94-%EC%9D%B4%EC%9C%A0/

[[Data structure] 개발자라면 꼭 알아야 할 7가지 자료구조, velog, 2022년08월22일 접속]
https://velog.io/@jha0402/Data-structure-%EA%B0%9C%EB%B0%9C%EC%9E%90%EB%9D%BC%EB%A9%B4-%EA%BC%AD-%EC%95%8C%EC%95%84%EC%95%BC-%ED%95%A0-7%EA%B0%80%EC%A7%80-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0

[그래프, 나무위키, 2022년08월22일 접속]
https://namu.wiki/w/%EA%B7%B8%EB%9E%98%ED%94%84(%EC%9D%B4%EC%82%B0%EC%88%98%ED%95%99)

[자료구조, 나무위키, 2022년08월22일 접속]
https://namu.wiki/w/%ED%8A%B8%EB%A6%AC(%EA%B7%B8%EB%9E%98%ED%94%84)

profile
개발자준비중

0개의 댓글