CS 강의 8. 자료구조의 동작과 활용

출처 : 내일배움캠프

 

0. 자료와 자료구조

0 - 1. 텍스트 자료의 표현

1) 아스키 코드

2) 유니코드 & UTF-8

0 - 2. 숫자 자료의 표현

1) 부호 없는 정수

2) 부호 있는 정수

3) 실수

0 - 3. 선형/비선형 자료구조

텍스트와 숫자 자료보다 더 복잡한 데이터를 저장하고 연산하기 위해서 다양한 자료구조가 필요하다. 큰 데이터를 단순한 자료 구조에 할당이 어렵고, 저장해도 데이터의 삽입/삭제가 어려워 정렬도 어렵다. 그래서 등장한 자료구조를 선형/비선형 구조라고 한다

선형 자료구조

- 데이터가 저장 순서대로 저장되는 자료구조

- 배열, 연결 리스트, 스택, 큐

- 배열은 데이터를 연속적인 메모리 공간에 저장하는 자료구조

- 연결 리스트는 데이터가 노드로 연결된 형태로 저장되는 자료구조

- 스택은 데이터를 마지막에 삽입하고 마지막에 삭제하는 자료구조

- 큐는 데이터를 첫 번째에 삽입하고 첫 번째에 삭제하는 자료구조

 

비선형 자료구조

- 데이터가 저장 순서가 아닌 규칙에 따라 저장되는 자료 구조

- 트리, 그래프

- 트리는 데이터가 계층적으로 저장되는 자료구조

- 그래프는 데이터가 노드와 엣지로 연결된 형태로 저장되는 자료구조

1. 자료구조

1 - 1. 배열(Array)

연속적인 메모리 공간에 데이터를 저장한다. 순서를 유지할 수 있어 접근을 빠르게 할 수 있지만 배열의 크기가 불변이므로 데이터 할당 시 고려해야 한다

* 배열이 필요한 이유

- 임의로 연속적인 메모리 공간에 데이터를 저장한다고 해도, 배열과 다른 이유는

~ 배열로 만든 자료형에 따라 표현하기 위한 메모리 크기가 달라지고, 이는 운영체제,CPU 등 다양한 변수에 따라 달라진다

ex) boolean은 실제로 1비트만 필요하지만 때에 따라 1바이트 또는 int형과 동일한 크기를 차지하기도 한다.

언어에 따라, C에서 프로그램이 판단하는 만큼 크키를 할당하기도 하고 자바는 프로그램에 상관없이 크기가 결정되기 때문에 전부 다를 수 있기 때문이다

~ 배열이 아닌 모든 요소 데이터를 변수에 각각 할당해 저장한다면 모든 변수의 주소값과, 그 데이터까지 파악하고 있어야하지만 배열을 사용한다면 배열로 선언한 변수 하나의 주소값과 그 배열의 크기에 대한 정보만 있다면 표현할 수 있다

 

+ 자바 배열

int[] arr = {10, 13, 11, ..., 21};
arr[0]; // 변수 a 였던것
arr[1]; // 변수 b 였던것
arr[675]; // 변수 zz 였던것

메모리 공간에 연속적으로 데이터를 저장한다. 그 후 arr[n]을 호출할 때마다 곱셈 연산을 통해 메모리에 int 사이즈의 n배를 곱한 주소의 데이터를 가져온다

 

+ C언어 배열

int* arr = malloc(sizeof(int) * 676);
arr[0] = 10;
arr[1] = 13;
...
arr[675] = 21;

*arr;// 변수 a 였던것
*arr+1;// 변수 b 였던것
*arr+675;// 변수 zz 였던것

sizeOf 함수를 통해 int 데이터의 크기를 호출한다. 그 후 malloc 함수를 호출해 연속적인 메모리 공간에 데이터를 저장한다

 

참조형 타입 변수의 배열

- 자바에서 String은 할당을 마음대로 할 수 있는데, 배열은 그 크기가 한정되어 있음에도 String 배열을 만들 수 있다

- 어떻게? : 대부분의 언어는 자료형 타입을 원시형과 참조형으로 구분하고 있는데, 원시형의 경우가 메모리 상에 실제 값 그 자체가 저장된다

- 참조형 타입의 경우, 메모리 공간에 주소값을 저장한다. 즉, 실제 데이터는 연속적이지 않지만 실제 데이터가 있는 주소 값을 저장하는 부분이 연속적인 것이다

 

배열의 특징

- 순서가 있다(메모리 순서대로)

- 연속된 공간을 미리 정해서 사용해야 한다(확정된 메모리 공간을 할당받아 써야 하므로)

- N번째 데이터에 접근하기 위해 복잡한 과정이 필요없이 것셈과 곱셈 한번이면 가능하다(n번째 데이터 접근 : 시작주소 + (n-1) * 해당 자료형 크기)

 

CRUD에서 동작

Create : 만들어져 있는 배열에 바로 이어져 있는 공간에 데이터를 저장하려고 해도, 그 공간이 현재 사용 중인지 알 수 없고, 자바에서는 불가능하다. 다만 C에서 가능하긴 하지만 디스크에 할당 연산을 몇 만번이나 하게 되면 메모리 충돌이 일어난다

-> 새로운 연속된 공간을 다시 할당받고 기존 데이터와 새 데이터를 새 공간에 할당해야 한다

int[] arr = new int[5];
arr[0] = 1;
...// 무언가 넣음int[] tmp = new int[6];
for (int i = 0; i < arr.length; i++) {
    tmp[i] = arr[i];
}
arr = tmp;

Read : 덧셈과 곱셈 한번씩이면 데이터에 접근하므로 매우 빠르다

Update : Read와 같이 접근이 빨라 간단하다

Delete : 배열의 데이터를 삭제하는 경우, 삭제하려는 데이터의 공간에 새로운 데이터를 복사해 넣거나 삭제한 데이터만큼 이후의 데이터를 앞으로 땡겨야 한다(예외로 배열에 빈 공간이 존재하는 걸 허용하며 마지막 요소를 삭제하는 경우엔 이런 작업이 필요없다)

 

배열의 시간복잡도

- 읽기, 수정 : O(1)

- 생성, 삭제 : O(N), 삭제 예외 : O(1)

1 - 2. 연결 리스트(Linked List)

노드로 연결된 데이터를 저장하는 자료구조로, 데이터의 순서를 유지할 수 없지만 데이터의 추가나 삭제가 쉽다. 또한 배열의 크기를 지정하거나 변경할 필요가 없다

 

* 배열과 리스트의 공통점 : 해당 자료구조로 할당한 변수는 첫 번째 데이터가 저장된 위치다. 배열은 연속적이기 때문에 다음 데이터에도 접근이 빠르지만, 리스트는 다음 데이터의 위치를 바로 알 수 없다

 

CRUD

1) Create

리스트는 데이터의 위치가 서로 다르기 때문에 데이터 간 연결만 수정하면 데이터의 생성을 할 수 있다. 다만 리스트의 중간에 데이터를 생성하는 경우엔 앞선 데이터의 위치를 전부 파악한 후 가능하기 때문에 O(N)의 시간복잡도를 가진다

~ 처음이나 끝에 데이터를 생성하는 경우 : O(1), 바로 가능하다

 

2) Read, Update : 데이터의 값을 확인하거나 바꾸는 경우

- Create와 마찬가지로 데이터의 위치를 바로 파악할 수 없으므로 중간에 위치한 데이터를 확인, 수정하는 경우 O(N)의 시간복잡도를 가진다

- 맨 앞이나 맨 뒤의 값에 대한 연산은 O(1)

 

3) Delete

- 삭제하려는 데이터를 찾아간 후, 연결을 해제하고 다음 데이터에 연결하면 자바의 경우 GC가 제거한다

~ 시간 복잡도 : 중간 데이터 삭제 - O(N)/ 처음이나 마지막 : O(1)

1 - 3. 벡터(ArrayList)

* 자바 : ArrayList와 Linked List는 다르다!

자바의 ArrayList는 Collection 프레임워크의 List 인터페이스를 구현하는 타입이다. 거기에 배열처럼 크기를 설정하지 않고 사용할 수 있으며 크기가 가변적이다(메모리 효율은 떨어지지만 크기를 자유롭게 변경할 수 있는 배열이다)

 

ArrayList

- 기본 동작원리 및 CRUD 효율성은 배열과 동일하다

- Linked List vs ArrayList의 CRUD 효율이 매우 다르기 때문에 고려하지 않고 사용하면 매우 비효율적일 수 있다

ArrayLIst의 기본 크기 설정 : 10개

객체 생성 시, 벡터의 크기를 직접 설정할 수도 있다

ArrayList의 크기가 가득 찬 경우 배열을 새로 할당받아 복사한다

* n >> 1은 모든 비트를 오른쪽으로 한 칸 옮겼다는 의미로, n/2를 뜻한다

( n << 1 : n * 2)

따라서 grow 메서드를 통해 자바는 기존 배열의 1.5배 크기로 새 배열을 만든 후  Arrays.copyOf 메서드로 새 배열에 기존 배열을 복사한다

 

* 자바는 벡터 자료구조가 별도로 존재한다

-> ArrayList보다 성능이 좋지 않기 때문에 ArrayList를 쓰는 것이 낫다

- 벡터는 한 번에 하나의 쓰레드에서만 쓸 수 있지만, 어레이리스트는 여러 쓰레드에서 사용 가능하다

1 - 4. 큐, 스택(Queue, Stack) + 덱

리스트를 사용하기 때문에 시간복잡도가 리스트와 동일하다. 따라서 리스트에 이 세가지 자료구조가 포함된다고 말할 수도 있지만, 차이점이 분명히 존재한다

1) 큐(Queue)

큐는 선입선출(FIFO)의 특징을 가지는 자료구조로 먼저 들어가는 데이터가 먼저 나온다

- 중간 데이터 조회 & 수정 : 불가능하다

- 사용하는 함수, 모든 함수의 시간복잡도는 O(1)이어야 한다

1. enqueue() ~ add() : 한 쪽 방향으로 데이터를 넣는다

2. dequeue() ~ poll() : 다른 방향으로 데이터를 뺀다 (dequeue vs deque ~ deque는 double ended queue)

3. peek() : 가장 앞에 있는(제거될) 데이터를 확인

4. isEmpty() : 데이터 유무 확인

5. size() : 큐의 데이터 개수

import java.util.LinkedList;

public class MyQueue<T> {
    LinkedList<T> list;

    public MyQueue() {
        list = new LinkedList<>();
    }

    public void enqueue(T data) {
        list.addFirst(data);
    }

    public T dequeue() {
        return list.pollLast();
    }

    public T peek() {
        return list.peekLast();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

    public int size() {
        return list.size();
    }
}

연결 리스트로 큐를 구현하면 이렇게 된다

* 언어별 큐 구현법

1) 자바 : Queue<> q = new LinkedList();

2) 파이썬 : 따로 큐를 제공하지 않는다. 배열도 없고 파이썬의 리스트는 연결 리스트가 아니고 벡터(arrayList)로 동작하므로 dequeue의 시간복잡도가 높아져 비효율적이다 ~ deque을 사용해 큐를 구현한다

3) C++ : STL

4) C : 전부 직접 구현

 

2) 스택(Stack)

LIFO의 구조를 가지고 있어 나중에 들어간 데이터가 먼저 나오는 구조를 가지고 있다

- 중간 데이터 조회 & 수정 불가능

- 함수 : 시간복잡도 O(1)

1. push() : 데이터 쌓기

2. pop() :데이터 빼기

3. peek() : 가장 위에 있는(마지막에 들어간) 데이터 조회

4. isEmpty()

5. size()

import java.util.LinkedList;

public class MyStack<T> {
    LinkedList<T> list;

    public MyStack() {
        list = new LinkedList<>();
    }

    public void push(T data) {
        list.addFirst(data);
    }

    public T pop() {
        return list.pollFirst();
    }

    public T peek() {
        return list.peekFirst();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

    public int size() {
        return list.size();
    }
}

* 자바 : Stack<> stk = new LinkedList<>();

파이썬 : 리스트 활용 ~ stack = []

C++ : STL

C : 직접 구현

https://github.com/NaHwaSa/C_LanguagePractice/tree/main/stack%20(data%20structure)

 

Stack ~ Ctrl + z를 연상하면 쉽다

 

3) 덱(Deque)

양쪽으로 넣고 뺄 수 있는 큐, 양 쪽을 스택으로 활용하거나 한 쪽은 스택, 한 쪽은 큐로 구분해 사용할 수도 있다

중간 데이터는 마찬가지로 접근, 수정할 수 없다

- 함수, O(1)

1. addFirst() : 덱의 한 쪽에 데이터 추가

2. pollFirst() : 덱의 한 쪽에 데이터 빼기

3. peekFirst() : 덱의 한 쪽에서 데이터 조회

4. addLast() : 다른 쪽 데이터 추가

5. pollLast() : 다른 쪽 데이터 빼기

6. peekLast() : 다른 쪽 데이터 조회

7. isEmpty()

8. size()

import java.util.LinkedList;

public class MyDeque<T> {
    LinkedList<T> list;

    public MyDeque() {
        list = new LinkedList<>();
    }

    public void addFirst(T data)    { list.addFirst(data); }
    public T pollFirst()            { return list.pollFirst(); }
    public T peekFirst()            { return list.peekFirst(); }

    public void addLast(T data)     { list.addLast(data); }
    public T pollLast()             { return list.pollLast(); }
    public T peekLast()             { return list.peekLast(); }

    public boolean isEmpty()        { return list.isEmpty(); }
    public int size()               { return list.size(); }
}

 

자바에서 리스트를 구현한 덱 코드

자바 : Deque<> dq = new LinkedList<>();

파이썬 : from collections import deque를 통헤 임포트(import)

C : 직접 구현

 

** 스택은 한 번에 하나의 작업만 추가/ 제거할 수 있기 때문에 스택에 너무 많은 데이터가 한 번에 쌓이면 처리 속도가 느려지지만, 덱을 활용하면 pollLast()를 통해 덱 전체 데이터의 개수를 관리할 수 있다

1 - 5. 해시 테이블(Hash Table)

해시 테이블(맵)은 키와 값의 쌍을 저장하는 자료구조로, 해시 테이블은 키를 사용해 데이터를 빠르게 찾을 수 있다. 그러나 데이터가 많아지면 성능 저하로 이어지는 자료구조이기도 하다

- 키를 통해 바로 데이터를 받아올 수 있어 속도가 빠르다

- 해시 : 임의 값을 고정 길이로 변환

- 해시 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조

- 해시 함수 : 키에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수

- 해시 값 / 해시 주소 : 키를 해싱 함수로 연산해 해시 값을 알아내고 이를 기반으로 해시 테이블에서 해당 키에 대한 데이터 위치를 일관성있게 찾을 수 있다

- 슬롯 : 한 개의 데이터를 저장할 수 있는 공간

- 저장할 데이터에 대해 키를 추출할 수 있는 별도 함수도 존재할 수 있다

 

해시

- 데이터를 효율적으로 관리하기 위해 임의의 길이인 데이터를 고정 길이의 해시 값으로 매핑

- 해시 함수를 구현해 데이터 값을 해시 값으로 매핑

- 데이터가 많아지는 경우 해시 값의 중복이 발생할 수 있어 충돌이 발생할 수 있다 ~ collision

 

해시를 사용하는 이유

- 적은 자원으로 많은 데이터를 효율적으로 관리하기 위해

=> 하드디스크나 클라우드에 존재하는 무한한 데이터를 유한한 개수의 해시 값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능해진다

- 항상 동일한 해시 값 리턴, index를 알면 데이터 검색 속도가 빨라진다

- 해시 테이블의 시간복잡도는 O(1) + 이진탐색 트리는 O(logN))

 

* collision 문제 해결

1. 체이닝 : 연결리스트로 노드를 계속 추가하는 방식 ~ 제한 없이 계속 연결이 가능하지만 메모리 문제가 있다

2. Open Addressing : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용 (해당 키 값에 저장되어 있으면 다음 주소에 저장)

3. 선형 탐사 : 정해진 고정 폭으로 옮겨 해시 값의 중복을 피한다

4. 제곱 탐사 : 정해진 고정 폭을 제곱수로 옮겨 해시 값의 중복을 피한다

1 - 6. 셋(Set)

Set은 배열이나 리스트처럼 연결 자료구조(Collection)이지만 "순서"의 개념이 없다

 

특징

- 데이터를 순서 없이 저장할 수 있다

- 집합

- 데이터 삽입 순서대로 저장되지 않는다

- 수정 가능하다

- 동일한 데이터를 다시 추가할 수 없다 ~ 하나의 값만 저장된다

- Fast Lookup의 방법 중 하나(다른 방법 : 이진탐색 트리, 인덱스 등)

- 자바의 경우 대표적인 3가지의 Set : HashSet, TreeSet, LinkedHashSet이 있고, 이 순서대로 빠르다

~ Hash 알고리즘 사용 : HashSet, 이진탐색 트리를 사용해 오름차순 정렬해주는 TreeSet, 순서 부여하는 LinkedHashSet

 

구조

- 요소 저장 순서

1) 저장할 요소의 Hash 값을 구한다

2) 해시 값에 해당하는 공간에 값을 저장한다

- Set은 저장하려는 데이터의 해시 값에 해당하는 bucket에 값을 저장하므로 순서가 없고, 인덱스도 없다

- bucket에 저장하므로 중복 값도 없다

- 해시 값이 기반이므로 look up이 빠르다 ~ look up : 특정 값 포함인지 확인

- O(1) : Set의 총 길이와 관계없이 해시 값 계산 후 해당 bucket을 확인

 

HashSet

- 내부적으로 HashMap을 사용해 값을 저장

- 값의 중복을 허용하지 않는다

- 값이 저장된 순서를 보장하지 않는다

- null 허용

 

Set의 사용

- 순서보장이 필요없고 중복이 있어선 안되는 "이벤트 응모자 목록"과 같은 자료를 저장할 때 유용하다

- 해시 값 기반으로 조회속도가 빨라 실시간 데이터 처리에도 사용 가능