자료 구조 정리

자료 구조

• 상황과 문맥에 맞게 데이터를 담을 수 있는 적절한 구조를 말하며 데이터에 편리하게 접근하고 조작하기 위한 방법이다.

• 자료 구조는 크게 단순 구조와 비단순 구조로 나뉘는데, 단순 구조는 프로그래밍에서 사용되는 기본 데이터 타입을 의미하며, 비단순 구조는 단순한 데이터를 저장하는 구조가 아니라 여러 데이터를 목적에 맞게 효과적으로 저장하는 자료 구조이며, 선형 구조와 비선형 구조로 나뉜다.

  • 선형구조 : 저장되는 자료의 전후 관계가 1대 1(list, stack, queue)
  • 비선형 구조 : 데이터 항목 사이의 관계가 1:n 또는 n:m(graph, tree)

list(array)

• 순차적으로 데이터를 저장하며, 이미 생성된 리스트도 수정이 가능하다.(mutable)

• 동일한 값도 여러번 삽입이 가능하며, 순차적으로 인덱스를 갖고, 다중 차원 배열이 존재할 수 있다.

  • 다중 차원 배열 : multi-dimentional array로 array의 요소가 array가 될 수 있다.

• 실제 메모리 상에서 물리적으로 데이터가 순차적으로 저장되기 때문에 데이터에 순서가 있으며, index가 존재하고 indexing(index를 사용해 특정 요소를 리스트로 부터 읽어들인다.)이 가능하며, slicing(요소의 특정 부분을 따로 분리해 조작하는 것)이 가능하다.

단점

• 메모리의 실제 주소도 순차적으로 되어있기 때문에 여러 장점도 있지만, 단점도 존재한다.

• 중간의 특정 요소를 삭제해야 하는 경우 항상 메모리가 순차적으로 이어져 있어야 하기 때문에 삭제된 요소로부터 위에 있는 모든 요소들을 앞으로 이동시켜주어야 한다. 그렇기 때문에 배열에서 요소를 삭제하는 것은 다른 구조에 비해 느릴 수 있다.

• 처음 생성될 때 어느 정도 메모리를 미리 할당하기(pre-allocation) 때문에 요소들이 처음 할당한 메모리 이상으로 많아진다면 resizing이 필요하며 추가적으로 할당된 메모리 도한 순차적이어야 하기 때문에 배열의 resizing은 상대적으로 오래 걸리는 작업이다.

• array는 정보가 자주 삭제되거나 추가되는 데이터를 담기에는 적절하지 않다.
• 사이즈 예측이 잘 되지 않거나 급격하게 자주 늘어날 확률이 있는 데이터는 array 말고 더 적합한 자료 구조를 선택하는 것이 좋다.

언제 사용하는 것이 좋을까?

• 순차적인 데이터를 저장하며 값보다는 순서가 중요한 데이터
• 특정 요소를 빠르게 읽어야 할 때
• 데이터의 사이즈가 자주 변하지 않으며 요소가 자주 삭제되거나 추가되지 않을 때

Tuple

• 리스트와 마찬가지로 데이터를 순차적으로 저장할 수 있는 순열 자료 구조이지만 한번 정의되고 나면 수정할 수 없다.(immutable)

• 두 세개 정도의 적은 수의 소규모 데이터를 저장할 때 많아 사용하며, 함수에서 리턴값을 한개 이상 리턴하고 싶을 때 자주 사용한다,

장점

• 간단한 값을 빨리 표현하고 싶을 경우 많이 사용한다.

단점

• 객체처럼 key-value 쌍으로 이루어져있지 않고, 괄호 안에 데이터만 담겨있기 때문에 문맥을 보고 의미를 가정해야 한다.

언제 사용하는 것이 좋을까?

• 리스트에 비해 더 가볍고 메모리를 적게 사용하기 때문에 리스트를 사용하기에는 간단한 데이터들을 표현할 때 사용한다.

set

• 리스트와 같이 순열 자료 구조이지만 순서라는 개념이 존재하지 않는다.

• 삽입 순서대로 저장되지 않고 특정한 순서를 기대할 수 있는 자료구조이지만 수정은 가능하다.

• 동일한 값을 여러변 삽입이 불가능하며 만일 여러번 삽입될 시 하나의 값만 저장된다.

• fast lookup이 필요할 때 주로 사용된다.

• 요소들이 저장될때의 순서는 다음과 같다
  1) 저장할 요소의 값의 hash값을 구하고
  2) hash 값에 해당하는 공간에 값을 저장한다.
  

• 저장하고자 하는 값의 해쉬값에 해당하는 공간에 값을 저장하기 때문에 순서가 없고 인덱싱도 불가능하며 중복된 값을 저장할 수 없고 look up이(특정 값을 포함하고 있는지 확인) 빠르다.

• 총 길이와 상관 없이 단순 해쉬값 계산 후 해당 공간을 확인하면 된다.

hash란?
단방향 암호화로 한번 암호화하면 복호화가 안되며 실제 길이와 상관 없이 hash값을 일정한 길이를 가지기 때문에 hash는 주로 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑할 때 사용된다.

언제 사용할까?

• 여러 배열들로부터 유일한 값을 가지는 배열을 재 생성할 수 있다.
• 빠른 look up이 필요하며 순서가 상관 없을 때

dictionary

• 다른 언어에서는 hashmap이나 hash table 이라고 하기도 하며, key-value 형태의 값을 저장할 수 있는 자료구조이다.

• 특정 순서대로 데이터를 리턴하지 않으며 key의 값은 중복 될 수 없다. 만일 중복될시 먼저 있는 key와 value를 대체하며 수정 가능하다.

• key값의 해쉬값을 수 한 후 해쉬값에 속해있는 공간에 값ㅇ르 저장하기 때문에 순서가 없고 중복된 key값은 허용되지 않는다.

언제 사용할까?

• 데이터베이스처럼 key와 value를 묶에서 데이터를 표현해야할 때 유용하며, 실제로 데이터베이스에서 읽어들인 값을 딕셔너리로 변환해서 자주 사용한다.

stack

• Last In First Out, 마지막으로 저장한 데이터가 처음으로 읽히며 삽입과 삭제가 저장소의 맨 위에서만 일어난다.

장점

• 참조 지역성이 높다. 즉 한번 참조된 곳은 다시 참조될 확률이 높다.

단점

• 데이터를 탐색하기 어렵다.

언제 사용할까?

• 프로그램에서 함수 호출 기록을 저장할 때(콜스텍)

• 웹 브라우저 흑등 내역인데 최신 내역이 먼저 나와야 하는 경우

• 웹 브라우저 방문기록(뒤로가기), 실행 취소

• 미로찾기 알고리즘(방문한 곳을 좌표로 표기하고 다음 방문할 곳을 탐색한 후 스택에 간 곳 전부를 push하고 다시 pop하면서 현재 경로로 변경하는 것을 반복)

콜스택이란?
함수의 호출을 기록하는 자료구조로, 어떤 함수를 실행할 때 스택 위에 push를 하게되고, 함수로부터 반환을 받을때 pop하게 된다.

queue

• First In First Out

• queue 말고도 double ended queue, prioritu queue등이 있다.

• 리스로 구현이 가능하지만 효율적이지 않다. 끝에 원소를 붙이거나 꺼내는 작업은 빠르지만 리스트의 처음에 원소를 추가하거나 빼는 것은 다른 원소들을 모두 한칸씩 이동시켜야 하기 때문에 느리다.

언제 사용할까?

• 맛집 예약, 티켓 카운터 등의 예약 시스템

• OS 프로세서 스케쥴링 시스템(priority queue 사용)

• CPU 의 프로세스 스케쥴링

• 프린터의 인쇄 대기 목록

• 데이터가 입력한 시간 순서대로 처리해아하는 경우

hash

• 단방향 암호화로 입력 데이터를 변화하여 원본 데이터로 복호화할 수 없도록 하는 과정

• hash값을 일정한 길이를 갖고, 주로 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑할 때 사용된다.

해시함수란?

• 해시함수는 임의의 길이의 데이터를 입력받아 일정한 길이의 비트열로 반환 시켜주는 함수이며 입력값의 길이가 달라도 출력값은 언제나 고정된 길이로 반환한다.
• 같은 문자열에 대해서는 같은 인덱스를 구할 수 있어야 해시 함수로 구한 버킷의 인덱스를 저장 후에도 구할 수 있다.

tree

• 데이터를 거꾸로 된 나무 형태로 저장하는 모양으로 노드로 이루어진 자료구조이다.

• 트리는 하나의 루트 노드를 갖고 있고 루트 노드는 0개 이상의 자식 노드를 갖고있다.

• 자식 노드 또한 0개 이상의 자식노드를 갖고 있으며 반복적으로 정의된다.

• 대상 정보의 항목들을 계층적을 연관 되도록 구조화 시킬 때 하용하며 데이터 요소들의 단순한 나열이 아닌 부모 자식 관계의 계층적 구조로 표현한다.

• 이진 트리(두개의 자식 노드를 가진 트리)가 구조가 대표적이며 그래프의 한 종류로 사이클이 없다.

• 루트 노드를 제외한 모든 노드는 단 하나의 부모 노드를 갖는다.

언제 사용할까?

• 계층적 관계의 표현에 사용
• 윈도우와 리눅스의 파일 시스템 구조
• 대용량의 데이터를 저장할 때 많이 쓰인다.

이진트리

• 최대의 차수가 2인 트리로 하나의 노드에 left, right만 존재한다.

이진탐색트리

• 항상 부모 노드가 왼쪽 자식보다 크고 오른쪼 자식보다는 작기 때문에 한번 확인할 때마다 봐야하는 원소의 개수가 절반씩 줄어든다.

• 탐색할 경우 찾고자하는 값이 부모 노드보다 작을 경우 왼쪽 자식으로, 클 경우 오른쪽 자식으로 이어 나가며 방문한다.

• 이진 탐색이 항상 동작하도록 구현하여 탐색 속도를 극대화시킨 자료구조이다.

linked list

• 노드(데이터와 다음 노드의 주소를 담고 있다.)들이 한줄로 연결되어있는 방식의 자료구조로 연결 방향에 따라 단일 연결 리스트(singly linked list), 이중 연결 리스트(doubly linked list), 환형 연결 리스트(circular linked list)가 있다.

• 리스트처럼 선형 데이터 자료구조이지만 배열은 물리적인 배치 구조 자체가 연속적으로 저장되어있고 linked는 노드의 next 부분에 다음 노드의 위치를 저장함으로써 선형적인 데이터 자료구조를 가진다.

• 사이즈가 무한하며 포인터로 다음 노드를 알 수 있다.

• 연결되어있는 구조이기 때문에 특정 위치의 데이터를 탐색하기 위해서는 첫 노드부터 탐색을 시작하여 순차 접근만 가능하다.

• 주소만 연결하면 되기 때문에 삽입, 삭제가 리스트에 비해 빠르고 쉽다.

• 불연속적 단위로 저장되기 때문에 조회에 불리하며 포인터로 인해 저장공간을 더 쓰게된다.

장점

• 리스트의 길이를 동적으로 조절 가능하며 데이터의 삽입과 삭제가 쉽다.

단점

• 임의의 노드에 바로 접근할 수 없고 다음 노드의 위치를 저장하기 위한 추가 공간이 필요하다

hash table

• key-value 1:1 매핑에 사용되는 자료구조로 해시 테이블은 해시 함수를 사용해 인덱스를 저장소의 배열로 계산한다. 이떄 값을 알고 싶다면 키를 해시하여 인덱스를 구혀면 되기 떄문에 탐색에 유리하다.

• 키값을 해시함수로 해시하고 길이를 단일화시켜 저장소를 효율적으로 운영할 수 있따. 서로 다른 키가 같은 해시를 가질경우 충돌이 생기기 때문에 키는 중복될 수 없다.

• 키로 값을 빠르게 접근하고 조작이 가능하다.

---

http://www.nextree.co.kr/p6506/
https://hyungjoon6876.github.io/jlog/2018/07/20/btree.html