저번엔 DOM이 뭔지 몰랐는데 이번엔 자료구조가 뭔지 몰라
그래서 공부합니다 "자료구조"
자료구조
컴퓨터 과학에서 대량의 데이터를 효율적인 접근 및 수정을 가능하게 하는 자료의 조직, 관리, 저장(데이터의 구조)을 의미한다.
▪️ 데이터 값의 모임, 데이터 간의 관계, 데이터에 적용할 수 있는 함수나 명령 등
❓ 자료구조를 쓰는 이유
자료 구조는 보다 효율적인 알고리즘을 사용할 수 있게하며, 효과적으로 설계된 자료구조는 실행시간이나 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행할 수 있도록 한다.
▪️ 자료구조의 종류는 각자의 연산 및 목적에 맞추어져 있다.
📚 분류
자료의 특성과 크기, 주요 사용법과 수행하는 연산의 종류, 구현에 필요한 공간 크기에 따라 선택하여 사용한다.
자료 구조의 종류로는 자료형의 따라 분류하는 단순 구조와 자료 간 관계가 1 대 1인 선형 구조, 1 대 다, 다 대 다 구조인 비선형 구조, 파일 구조가 있다.
✔️ 구현에 따라
배열, 튜플, 연결 리스트, 원형 연결 리스트, 이중 연결 리스트, 해시 테이블
✔️ 형태에 따라
▪️ 선형 구조 : 데이터들이 일렬로 쭉 저장되어 있는 형태
→ 스택, 큐, 덱
▪️ 비선형 구조 : 데이터가 트리 형태로 저장되어 있다고 생각하고 사용하는 자료구조
→ 그래프(방향 그래프, 무방향 그래프), 트리(이진 트리, 힙)
⭐ 공부하면서 접한 자료구조
연결 리스트
❓ 그 전에 리스트가 무엇일까?
데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조
리스트는 같은 종류의 데이터를 효율적으로 관리하고, 순차적으로 저장하기 위해 필요하다.
장점 : 빠른 접근 가능, 첫 데이터 위치에서 상대적인 위치로 데이터에 접근이 가능(인덱스 번호 접근)
단점 : 데이터 추가/삭제의 어려움, 미리 최대 길이를 지정해야 함(C언어)
→ 파이썬과 JS의 배열은 길이를 사전에 정하지 않아도 동작하기 때문에 자료구조의 배열과 같지 않다.
링크드 리스트라고도 불린다. 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조이다.
(배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조이다.)
❓ 용어
노드(Node) : 데이터 저장 단위 (데이터 값, 포인터)로 구성
포인터(Pointer) : 각 노드 안에서, 다음이나 이전의 노드와 연결 정보를 가지고 있는 공간
시간 복잡도 : 문제를 해결하는데 걸리는 시간과 입력의 함수 관계
✔️ 장점
- 미리 데이터 공간을 할당하지 않아도 된다.
→ 배열은 미리 데이터 공간을 할당해야 한다. - 데이터를 추가 할 때마다 동적으로 크기가 늘어난다.
- 원소 검색 시 첫 번째 노드부터 마지막 노드까지 일일이 확인하기 때문에 O(n)의 시간 복잡도를 갖는다.
- 삽입 또는 삭제 연산 시에 해당 원소를 검색한 후 삽입, 삭제 연산이 이루어지므로 O(n)의 시간 복잡도를 갖는다.
→ 삽입, 삭제가 잦은 경우 링크드 리스트를 사용하는 것이 좋다.
✔️ 단점
- 연결을 위한 별도 데이터 공간이 필요하므로 저장 공간 효율이 높지 않다.
- 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느리다.
- 중간 데이터 삭제 시 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업이 필요하다.
- 검색이 잦은 경우 배열을 사용하는 것이 좋다.
이중 연결 리스트
이중 연결 리스트의 경우 앞 뒤 방향 모두 노드 탐색이 가능하다.
단방향 연결 리스트의 경우 반드시 우리가 설정한 head 차례로 데이터를 찾아간다.
이중 연결 리스트의 경우 노드를 추가하거나 제거하려면, 단방향 연결 리스트보다 더 많은 링크를 변경해야 하지만, 첫 번째 노드 이외의 노드인 경우 작업을 추적할 필요가 없어 작업이 단순해진다. 또한 이전 노드 또는 링크를 수정 또는 찾기 위해 리스트를 순회할 필요가 없다.
큐
가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 선형 구조이다. (FIFO, 선입선출)
❓ 용어
Enqueue : 큐에 데이터를 넣는 기능 (JS : push)
Dequeue : 큐에서 데이터를 추출하는 기능 (JS : shift)
우선 순위 큐 : 가장 우선 순위가 높은 데이터
✔️ 활용
순서대로 처리해야 하는 작업을 임시로 저장해두는 버퍼(buffer)로서 많이 사용된다.
멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 사용된다.
스택
가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있느 데이터 구조이다. (LIFO, 후입선출)
한쪽 끝에서만 자료를 넣거나 뺄 수 있어, 데이터를 제한적으로 접근할 수 있는 구조다.
▪️ 스택은 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용하여 구현한다.
✔️ 활용
컴퓨터 내부의 프로세스 구조의 함수 동작 방식으로 사용된다.
서로 관계가 있는 여러 작업을 연달아 수행하면서 이전의 작업 내용을 저장할 필요가 있을 때 사용된다.
✔️ 주요 기능
push : 데이터를 스택에 넣기
pop : 데이터를 스택에서 추출하기
✔️ 장점
- 구조가 단순하여 구현이 쉽다.
- 데이터 저장/읽기 속도가 빠르다.
✔️ 단점
- 데이터 최대 개수를 미리 정해야 한다.
→ 미리 최대 개수만큼 저장 공간을 확보해야 한다 - 저장 공간의 낭비가 발생할 수 있다.
해시 테이블
키(Key)에 데이터(Value)를 저장하는 데이터 구조
Key를 통해 바로 데이터를 받아올 수 있으므로 특정 조건에 맞춰 배열을 모두 순회할 필요가 없다. → 속도가 빨라짐
보통 배열로 미리 해시 테이블 사이즈만큼 생성 후에 사용한다.
▪️ 파이썬에선 딕셔너리 타입이 제공되어 해쉬를 별도로 구현하지 않아도 된다.
▪️ 마찬가지로 JS에서도 객체 타입을 제공하기 때문에 구현하지 않아도 된다.
{Key: 'Value'}
두 개 이상의 키에 대해 동일한 인덱스를 생성하는 해시 충돌이 발생할 경우 반드시 해결해야 한다.
❓ 용어
해쉬(Hash) : 임의 값을 고정 길이로 변환하는 것
해쉬 테이블(Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
해싱 함수(Hashing Function) : 키를 해싱 함수로 연산해서 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 키에 대한 데이터 위치를 일관성있게 찾을 수 있게 함
슬롯(Slot) : 한 개의 데이터를 저장할 수 있는 공간
▪️ 저장할 데이터에 대해 키를 추출할 수 있는 별도 함수도 존재할 수 있다.
✔️ 장점
- 데이터 저장/읽기(검색) 속도가 빠르다.
- 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉽다.
- 해쉬는 키를 바탕으로 한 데이터의 여부(유무)를 파악하기 쉽다.
✔️ 단점
- 일반적으로 저장공간이 좀 더 필요하다.
- 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요하다.
- 해시 함수를 통해 나눠져 저장되는 해쉬 테이블의 주소가 같은데, 별도의 처리를 하지 않을 경우 키를 바탕으로 한 데이터가 덮어씌워질 가능성이 있다.
→ 중복이 일어나지 않도록 해시 테이블의 공간을 넓게 설계해야 한다.
✔️ 용도
- 검색이 많이 필요한 경우
- 저장, 삭제, 읽기가 빈번한 경우
- 캐쉬 구현 시 (중복 확인)
❓ 캐쉬 : 동일한 페이지를 불러오는 경우 변경되는 데이터 이외에 사용자의 캐쉬 메모리에 저장하여 서버로부터 불러오는 데이터의 양을 관리하기 위한 메모리이다.
트리
노드(node)와 브랜치(branch)를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
❓ 사이클은 원을 그리며 탐색하는 것을 의미
▪️ 트리 구조에서 siblings 끼리는 브랜치로 이어지지 않는다.
✔️ 사용
트리 중 이진 트리 형태의 구조로 탐색(검색) 알고리즘 구현을 위해 사용
트리 내부에 어떤 값을 가진 데이터가 존재하는지의 유무를 파악하기 쉽다.
배열을 통해 배열의 길이만큼 전부 순회하는 것보다 기준을 가지고 탐색하므로 더욱 빠르다.
❓ 용어
Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 브랜치 정보 포함)
Root Node : 트래 최 상단 노드
Level : 최상위 노드를 Level 0으로 하였을 때, 하위 브랜치로 연결된 노드의 깊이
Parent Node : 노드의 다음 레벨에 연결된 노드
Child Node : 노드의 상위 레벨에 연결된 노드
Leaf Node : Child Node가 하나도 없는 노드
Sibling : 동일한 Parent Node를 가진 노드
Depth : 트리에서 Node가 가질 수 있는 최대 Level(깊이)
이진 트리 : 노드의 최대 브랜치가 2개인 트리
이진 탐색 트리 : 이진 트리에 추가적인 조건이 있는 트리
→ 추가 조건 : 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값
힙
데이터에서 최대값과 최소 값을 빠르게 찾기 위해 고안된 완전 이진 트리
❓ 완전 이진 트리 : 노드를 삽입할 때 최하단의 왼쪽 노드부터 차례대로 삽입하는 트리
힙의 구조
1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다.
→ 최대 힙의 경우
2. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작다.
→ 최소 힙의 경우
3. 완전 이진 트리 형태를 가진다.
✔️ 사용
배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸리지만, 힙에 데이터를 넣고 찾으면 O( 𝑙𝑜𝑔𝑛 )이 걸린다.
우선 순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에서 활용된다.
❓ 시간 복잡도 순서
O(1) < O( 𝑙𝑜𝑔𝑛 ) < O(n) < O(n 𝑙𝑜𝑔𝑛 ) < O( 𝑛2 ) < O( 2𝑛 ) < O(n!)⚠️ JS의 실행 컨텍스트에서 객체를 담아두는 공간인 Heap 메모리와 자료구조에서의 Heap은 다르다.
→ 메모리 Heap은 객체, 배열, 함수와 같이 크기가 동적으로 변할 수 있는 참조타입 값을 저장한다.
참고
