[CS지식] 5. 자료 구조

김zunyange·2023년 6월 19일

CS Note

목록 보기

12/13

Chapter 5. 자료구조

자료구조란?
대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조

코드 상에서 데이터를 효율적으로 처리하기 위해 데이터 특성에 따라 체계적으로 데이터를 구조화해야 하며, 어떤 데이터 구조를 사용하느냐에 따라 코드의 효율이 달라질 수 있다.

효율적으로 데이터를 관리해야 하는 이유

예시 1. 우편번호: 5자리 우편번호로 국가의 기초구역을 제공
👉🏻 5자리 우편번호에서 앞 3자리는 시, 군, 자치구를 표기, 뒤 2자리는 일련번호로 구성

예시 2. 학생 관리: 학년, 반, 번호를 학생에게 부여해서 학생부를 관리
👉🏻 XX학년, X반, X번 학생

만약 위와 같은 관리 기법이 없다면, 5자리 수를 모두 확인해야 하고 3000명의 학생 중 특정 학생을 찾기 위해 전체 학생부를 모두 훑어야 한다.
즉 수많은 데이터들을 추가하고, 읽어오고, 제거해야 할 때 효율적으로 관리를 해야 시간을 줄일 수 있기 때문에 자료구조가 필요하다.

대표적인 자료구조

1) 선형 구조 (Linear Structure)

데이터들이 일렬로 쭉 저장되어 있는 형태

2) 비선형 구조 (Non-Linear Structure)

데이터가 트리 형태로 저장되어 있다고 생각하고 사용하는 자료구조

3) 리스트 (List)

데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조
(파이썬에서는 리스트 타입이 배열 기능을 제공)

🧐 리스트는 왜 필요한가?

같은 종류의 데이터를 효율적으로 관리하기 위해!
같은 종류의 데이터를 순차적으로 저장하기 위해!

🔥 장점

빠른 접근이 가능하다.
첫 데이터의 위치 [0]에서 상대적인 위치로 데이터에 접근이 가능하다. (인덱스 번호로 접근이 가능하다)

🔥 단점

데이터 추가/삭제가 어렵다.
미리 최대 길이를 지정해야 한다.

4) 스택 (Stack)

데이터를 제한적으로 접근할 수 있는 구조
한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조

큐(Queue)	스택(Stack)
F.I.F.O	L.I.F.O
First In First Out	Last In First Out

스택은 LIFO(Last In, Fisrt Out) 또는 FILO(First In, Last Out) 데이터 관리 방식을 따른다.
LIFO: 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책
FILO: 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책

주요 기능
push(): 데이터를 스택에 넣기 pop(): 데이터를 스택에서 꺼내기

🔥 장점

구조가 단순해서, 구현이 쉽다.
데이터 저장/읽기 속도가 빠르다.

🔥 단점

데이터 최대 개수를 미리 정해야 한다.
파이썬의 경우 재귀 함수 호출은 1000번까지 가능하다.
저장 공간의 낭비가 발생할 수 있다.
미리 최대 개수만큼 저장 공간을 확보해야 한다.

스택은 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적이다.

5) 큐 (Queue)

구조 : 줄을 서는 행위와 유사
가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 동일
FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과 꺼내는 순서가 반대

어디에 큐가 많이 쓰일까?

멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용된다.

6) 트리(Tree)

트리: 노드(node)와 브랜치(branch)를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조

트리는 항상 루트(root)에서부터 시작된다. 루트는 자식(child) 노드를 가지며, 간선(edge)으로 연결되어 있다.
자식 노드의 개수는 차수(degree)라고 하며, 크기(size)는 자신을 포함한 모든 자식 노드의 개수다. 높이(height)는 현재 위치에서부터 리프(leaf)까지의 거리, 깊이(depth)는 루트에서부터 현재 노드까지의 거리다.
트리는 그 자식도 트리인 서브트리(subtree) 구성을 띤다.
레벨(level)은 0부터 시작한다. 논문에 따라 1부터 시작하는 경우도 있으나, 0부터 시작하는 것이 좀 더 일반적이다.
트리는 항상 단방향(uni-directional)이기 때문에 간선의 화살표는 생략 가능하다. 그림에서도 마찬가지로 생략해서 표현했고 일반적으로 방향은 위에서 아래로 향한다.

🌲 어디에 트리가 많이 쓰일까?

특히 이진 트리 (Binary Tree)형태의 구조가 탐색(검색) 알고리즘 구현을 위해 많이 사용된다.
트리 내부에 어떤 값을 가진 데이터가 존재하는지의 유무를 파악하기 쉽다.
배열을 통해 배열의 길이만큼 전부 순회하는 것 보다 기준(left right)을 가지고 탐색하므로 더욱 빠르다.

✏️ 알아둘 용어

Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
Root Node: 트리 맨 위(최 상단)에 있는 노드
Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
Parent Node: 어떤 노드의 다음 레벨에 연결된 노드
Child Node: 어떤 노드의 상위 레벨에 연결된 노드
Leaf Node (Terminal Node): Child Node가 하나도 없는 노드
Sibling (Brother Node): 동일한 Parent Node를 가진 노드
Depth: 트리에서 Node가 가질 수 있는 최대 Level (깊이를 나타냄)

7) 이진 트리와 이진 탐색트리

🌲 이진 트리(Binary Tree): 노드의 최대 브랜치가 2개인 트리

이진 트리구조에서 워낙 이진 탐색 트리 형식으로 많이 쓰기 때문에 이진 트리를 이진 탐색 트리라고 생각하는 경우도 있다.
하지만 둘은 같지 않음
이진 트리는 루트 노드의 최대 브랜치가 2개인 트리이며, 사이클을 이루지 않도록 구성한 데이터 구조

🌲 이진 탐색 트리(Binary Search Tree): 이진 트리에 다음과 같은 추가적인 조건이 있는 트리

이진 탐색 트리는 해당 이진 트리의 특징을 바탕으로 특정 조건을 붙인 트리이다.
왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음
주요 용도: 데이터 검색(탐색)
장점: 탐색 속도를 개선할 수 있음

8) 힙(Heap)

자료구조의 힙: 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
완전 이진 트리: 노드를 삽입할 때 최하단의 왼쪽 노드부터 차례대로 삽입하는 트리
트리를 기반으로 한 변형된 정책을 쓰고 있다고 생각하면 됨
js의 실행 컨텍스트에서 객체를 담아두는 공간인 Heap 메모리와 자료구조에서의 Heap은 다름

힙을 사용하는 이유

배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸린다 (전체를 순회해야 하기 때문)
이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면 $ O(log n) $ 이 걸림
우선 순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨

힙의 구조

힙은 최대값을 구하기 위한 구조 (최대 힙, Max Heap)와, 최소값을 구하기 위한 구조 (최소 힙, Min Heap)로 분류할 수 있음
힙은 다음과 같이 두 가지 조건을 가지고 있는 자료구조임
① 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우) - 최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작음
② 완전 이진 트리 형태를 가진다.

힙과 이진 탐색 트리(BST, Binary Search Tree)의 공통점과 차이점 🔥

공통점: 힙과 이진 탐색 트리는 모두 이진 트리이다. (자식 노드가 최대 2개가 있는 트리 구조)

차이점:

힙은 각 노드의 값이 자식 노드보다 크거나 같다. (Max Heap의 경우)
이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 - 다음 오른쪽 자식 노드 값이 가장 크다.
힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없다.
힙은 왼쪽 및 오른족 자식 노드의 값은 오른쪽이 클 수도 있고, 왼쪽이 클 수도 있다.
조건을 정해둔 것이 없다는 뜻(힙 구조에 들어오면서 판별한다)
이진 탐색 트리의 목적은 탐색을 위한 구조이다. (값의 유무 판별)
힙은 최대/최소값 검색을 위한 구조 중 하나로 이해하면 된다. (루트 노드에는 항상 최대/최소 값이 존재하므로)

9) 링크드 리스트 (Linked List)

연결 리스트라고도 한다.
배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조
링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
본래 C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원한다.

일반적인 링크드 리스트 형태

링크드 리스트의 장단점

🔥 장점

미리 데이터 공간을 할당하지 않아도 된다. <-> 배열은 미리 데이터 공간을 할당해야 한다.
데이터를 추가 할때마다 동적으로 크기가 늘어난다.
원소 검색 시 첫 번째 노드부터 마지막 노드까지 일일이 확인하기 때문에 O(n)의 시간 복잡도를 갖는다.
삽입 또는 삭제 연산 시에 해당 원소를 검색한 후 삭제, 삽입 연산이 이루어지므로 O(n)의 시간 복잡도를 갖는다.
즉, 삽입, 삭제가 잦은 경우 Linked List를 사용하는 것이 좋다.
why? 배열 경우 배열의 크기를 사전에 정해줘야 하기 때문!

🔥 단점

연결을 위한 별도 데이터 공간이 필요하므로, 저장 공간 효율이 높지 않음
연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업이 필요하다
검색이 잦은 경우 배열을 사용하는 것이 좋다

더블 링크드 리스트 구조 (Doubly linked list)

단방향 링크드 리스트의 경우 반드시 우리가 설정한 head 차례로 데이터를 찾아갔음
더블 링크드 리스트는 앞 뒤 방향 모두 노드 탐색이 가능함
이중 연결 리스트라고도 함
장점: 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능
더블 링크드 리스트 구조

10) Array vs Linked List

Array

가장 기본적인 자료구조인 Array 자료구조는, 논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서 인덱스(index)로 해당 원소(element)에 접근할 수 있다. 그렇기 때문에 찾고자 하는 원소의 인덱스 값을 알고 있으면 Big-O(1)에 해당 원소로 접근할 수 있다. 즉 random access 가 가능하다는 장점이 있는 것이다.

하지만 삭제 또는 삽입의 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤(O(1)), 또 한 가지의 작업을 추가적으로 해줘야 하기 때문에, 시간이 더 걸린다. 만약 배열의 원소 중 어느 원소를 삭제했다고 했을 때, 배열의 연속적인 특징이 깨지게 된다. 즉 빈 공간이 생기는 것이다. 따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift해줘야 하는 비용(cost)이 발생하고 이 경우의 시간 복잡도는 O(n)가 된다. 그렇기 때문에 Array 자료구조에서 삭제 기능에 대한 time complexity 의 worst case 는 O(n)이 된다.

삽입의 경우도 마찬가지이다. 만약 첫번째 자리에 새로운 원소를 추가하고자 한다면 모든 원소들의 인덱스를 1 씩 shift 해줘야 하므로 이 경우도 O(n)의 시간을 요구하게 된다.

💎 요약

데이터들이 순서대로 쭉 늘어선 배열의 형식을 취함.
논리적 저장 순서와 물리적 저장 순서가 일치한다.
인덱스로 해당 원소에 접근이 가능하다. O(1)
Random access(임의접근)가 가능하다.
삭제 또는 삽입의 과정 시 원소들을 shift 해줘야 하므로 시간이 오래 걸린다. O(n)
제한적인 크기를 갖는다.
stack영역에 할당

Linked List

이 부분에 대한 문제점을 해결하기 위한 자료구조가 linked list 이다. 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다. 따라서 이 부분만 다른 값으로 바꿔주면 삭제와 삽입을 O(1) 만에 해결할 수 있는 것이다.

하지만 Linked List 역시 한 가지 문제가 있다. 원하는 위치에 삽입을 하고자 하면 원하는 위치를 Search 과정에 있어서 첫번째 원소부터 다 확인해봐야 한다는 것이다. Array 와는 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문이다. 이것은 일단 삽입하고 정렬하는 것과 마찬가지이다. 이 과정 때문에, 어떠한 원소를 삭제 또는 추가하고자 했을 때, 그 원소를 찾기 위해서 O(n)의 시간이 추가적으로 발생하게 된다.

결국 linked list 자료구조는 search 에도 O(n)의 time complexity 를 갖고, 삽입, 삭제에 대해서도 O(n)의 time complexity 를 갖는다. 그렇다고 해서 아주 쓸모없는 자료구조는 아니기에, 우리가 학습하는 것이다. 이 Linked List 는 Tree 구조의 근간이 되는 자료구조이며, Tree 에서 사용되었을 때 그 유용성이 드러난다.

💎 요약

자료의 주소 값으로 서로 연결되어 있는 구조를 갖는다.
특정 원소에 접근하기 위해서는 첫 번째 원소부터 다 확인해야 해서 O(n)
sequential access(순차접근)
삭제, 삽입 시 뒤로 밀거나 채우는 과정 없이 단지 주소만 서로 연결시켜 주면 되기 때문에 Array보다 빠르다. O(n)
맨 앞 혹은 맨 뒤에 삭제, 삽입 시 O(1)
heap영역에 할당

배열과 연결 리스트의 차이

둘의 차이점을 정리하자면 이렇다.

배열(Array)	연결 리스트(Linked List)
정적 자료구조	동적 자료구조
미리 크기를 정해 놓음	크기를 정할 필요가 없음
연속된 메모리 주소를 할당 받음	연속된 메모리 주소를 할당 받지 않음
접근, 탐색 용이	추가, 삭제 용이
index 존재	Node 존재