비선형 자료형
각 요소가 선형적인 순서가 아닌 계층적이거나 상호 연결된 구조를 갖는 자료구조를 의미
선형 자료구조는 리스트나 배열처럼 요소들이 선형적으로 연결된 것과 달리 비선형 자료구조는 계층적인 구조를 가지거나 각 요소들이 서로 연결되어 있는 구조
[ 그래프(Graph) ]
다양한 형태의 객체 간 연결 관계를 표현하는 데 사용
각종 네트워크(소셜/컴퓨터 네트워크), 도로망 등을 모델링하는 데 유용
그래프는 정점과 간선으로 이루어진 자료 구조
어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다고 했을 때 어떠한 곳은 정점(vertax)이 되고, 무언가는 간선(edge)이 됨
▶ 그래프의 구성 요소
정점(Vertax / Node)
정점(또는 노드)은 객체나 개체를 나타냄
Ex) 소셜 네트워크에서 각 사용자, 도로망에서 각 교차로, 컴퓨터 네트워크에서 각 컴퓨터는 정점으로 표현될 수 있음
간선(Edge)
간선(엣지)은 정점(노드)들을 연결하는 선으로 그래프 내의 두 정점 간의 관계를 나타냄
두 정점 간의 관계는 양방향 혹은 단방향
가중치(Weight)
가중 그래프에서 간선은 가중치를 가질 수 있음. 가중치는 간선과 정점 사이에 드는 비용을 의미
가중 그래프는 실제 세계의 다양한 상황을 모델링하는 데 유용한데 최단 경로 문제, 네트워크 흐름 최적화, 스패닝 트리 등의 다양한 문제에 응용됨
▶ 그래프의 종류
무방향 그래프(Undirected Graph)
간선에 방향이 없는 그래프로, 간선은 두 정점을 양방향으로 연결
사용 예시
- 소셜 네트워크 그래프: 여러 사용자 간의 친구 관계를 표현할 때 사용자를 정점으로 친구 관계를 무방향 간선으로 나타낼 수 있음. 간선의 방향성이 없으며 친구 관계는 양방향
- 도로 네트워크: 도로와 교차로를 정점으로 나타내고 도로를 무방향 간선으로 표현. 차량은 양방향으로 이동할 수 있으므로 간선의 방향성이 없음
방향 그래프 (Directed Graph / Digraph)
간선에 방향이 있는 그래프로 간선은 한 정점에서 다른 정점으로 방향을 가지며 단방향으로 이동
사용 예시
- 웹 페이지 링크 그래프: 웹 페이지를 정점으로 나타내고 하나의 웹 페이지에서 다른 웹 페이지로의 하이퍼링크를 방향 간선으로 표현. 이러한 방식으로 웹 검색 엔진은 웹 페이지의 중요성을 계산하고 검색 결과를 반환
- 전자 메일 통신 그래프: 사용자 간의 이메일 통신을 나타내는 그래프에서 이메일 메시지는 보낸 사람에서 받는 사람으로의 방향 간선으로 표현. 각 이메일은 단방향 통신을 나타냄
가중 그래프 (Weighted Graph)
간선에 가중치가 할당된 그래프로 간선마다 추가 정보(가중치)가 포함
사용 예시
- 도시 간 비행 노선 그래프: 여러 도시를 정점으로 나타내고 도시 간의 항공 노선을 가중치가 있는 간선으로 표현. 가중치는 비행 거리나 비용을 나타내어 최소 비용 경로를 찾는 데 사용
- 소셜 네트워크 친밀도 그래프: 사용자 간의 친밀도를 나타내는 그래프에서 간선의 가중치는 두 사용자 사이의 친밀도 또는 상호 작용의 정도를 나타냄. 이를 통해 친밀한 관계를 분석하거나 추천 시스템을 개발할 수 있음
[ 트리 ]
트리는 계층적 자료 구조로서 정점(노드)과 간선(edge)으로 이루어져 있음
노드(Node)들이 연결된 방식을 나타내는 자료 구조로 트리는 하나의 루트 노드(root node)에서 시작하여 여러 개의 자식 노드(child node)들로 확장되는 구조를 갖음
각 노드는 부모 노드와 자식 노드 사이의 관계를 가지며 이러한 관계는 계층적인 구조를 형성
루트 노드, 내부 노드, 리프 노드 등으로 구성됨
▶ 트리의 구성
- 루트 노드(Root Node): 트리에서 최상위에 있는 노드
- 내부 노드(Internal Node): Leaf Node가 아닌 노드
- 리프 노드(Leaf Node): 자식이 없는 노드. 잎 노드, 단말 노드, 말단 노드라고도 부름
- 부모 노드(Parent Node): 어떤 노드보다 위에 있는 노드
- 자식 노드(Child Node): 어떤 노드보다 아래에 있는 노드
- 형제 노드(Sibling Node): 같은 부모를 가지는 노드.
- 간선(Edge): 노드를 연결하는 선 (Link 혹은 Branch라고도 함)
▶ 트리 관련 용어
- 크기(size): 자신을 포함한 모든 자손 노드의 개수
- 깊이(depth): 루트 노드에서 특정 노드까지 최단 거리로 도달하기 위해 거쳐야 하는 간선의 수
- 레벨(level): 트리의 레벨은 주어지는 문제마다 조금씩 다르지만 보통 깊이와 같은 의미. 트리의 특정 깊이(레벨)를 가지는 노드의 집합
- 서브트리(subtree): 트리 내의 하위 집합(부분 집합)으로 트리 내의 어떤 노드와 그 노드의 모든 자손 노드로 이루어진 부분 트리를 말함
- 차수(degree): 하위 트리의 개수 / 간선 수 = 각 노드가 지닌 가지의 수
- 트리의 차수(degree of tree): 트리의 최대 차수
- 트리의 높이(height of tree): 루트 노드에서 가장 멀리 있는 리프 노드까지의 거리
- 간선 수 = 노드 수 - 1
▶ 트리의 종류
이진 트리 (Binary Tree): 자식의 노드 수가 2개 이하인 트리
- 정이진 트리(full binary tree): 자식 노드가 0 또는 2개인 이진 트리
- 완전 이진 트리(complete binary tree): 왼쪽에서부터 채워져 있는 이진 트리. 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 경우 왼쪽부터 채워져 있음
- 변질 이진 트리(degenerate binary tree): 자식 노드가 하나밖에 없는 이진 트리
- 포화 이진 트리(perfect binary tree): 모든 노드가 꽉 차 있는 이진 트리
- 균형 이진 트리(balanced binary tree): 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리. map, set을 구성하는 레드 블랙 트리는 균형 이진 트리 중 하나
이진 탐색 트리 (BST, Binary Search Tree)
노드의 오른쪽 하위 트리에는 노드 값보다 큰 값이 있는 노드만 포함되고 왼쪽 하위 트리에는 노드 값보다 작은 값이 들어 있는 트리를 말함. 검색을 하기에 용이
평균적으로 시간복잡도가 O(log n)이 걸리며 최악의 경우 O(n)이 걸림(삽입 순서에 따라 선형적일 수 있기 때문)
AVL 트리 (Adelson-Velsky and Landis Tree)
- AVL 트리는 위에서 설명한 최악의 경우 선형적인 트리가 되는 것을 방지하고 항상 균형을 잡는 이진 탐색 트리
- 즉 자가 균형 이진 탐색 트리(self-balancing binary search tree)
- 두 자식 서브트리의 높이는 항상 최대 1만큼 차이 난다는 특징이 있음
- 탐색, 삽입, 삭제 모두 시간복잡도는 O(log n)이며 n은 노드의 개수
- 삽입, 삭제를 할 때마다 균형이 안 맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전(rotation)시키며 균형을 잡음
- AVL 트리에서 균형이 무너졌는지 판단을 위해 Balance Factor(BF)를 활용
- BF(K) = K의 왼쪽 서브트리의 높이 - K의 오른쪽 서브트리의 높이
- AVL 트리는 모든 Node의 BF가 -1, 0, 1 중 하나여야 하며 이를 벗어나면 균형이 깨졌다는 것을 의미하고 회전(rotation)을 하게 됨
레드 블랙 트리 (Red-Black Tree)
- 레드 블랙 트리는 자가 균형 이진 탐색 트리(self-balancing binary search tree)
- 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며 삽입 및 삭제 중 트리가 균형을 유지하도록 하는 데 사용
- "모든 리프 노드와 루트 노드는 블랙이고, 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다." 등의 규칙을 기반으로 균형을 잡는 트리
- 탐색, 삽입, 삭제 모두 시간복잡도 O(log n)
[ 힙(Heap) ]
힙은 완전 이진 트리 기반의 자료 구조
최소힙과 최대힙 두 가지가 있고, 해당 힙에 따라 특정한 특징을 지킨 트리를 말함
최소 힙의 삽입과 삭제 연산은 주로 우선순위 큐(Priority Queue)와 같이 최소값 또는 최대값을 효율적으로 관리해야 하는 경우에 사용됨
▶ 힙 종류
최소 힙(Min Heap)
루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 함
또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 함
최대 힙(Max Heap)
루트 노드에 있는 키는 모든 자식에 있는 키 중에 최댓값이어야 함
또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 함
▶ 동작 방식
삽입
- 새로운 노드를 트리의 마지막 노드에 추가. 이 새로운 노드를 부모 노드와의 크기를 비교
- 최대 힙인 경우: 추가한 노드가 부모 노드보다 크면 자리를 바꿈
- 최소 힙인 경우: 추가한 노드가 부모 노드보다 작으면 자리를 바꿈
- 크기를 비교하여 스왑(swap)하는 작업을 힙의 성질을 만족시킬 때 까지 반복
삭제
- 루트 노드에서 값을 제거
- 마지막 노드를 루트 노드로 옮김
- 자식 노드와 대소관계를 비교
- 최대 힙인 경우: 자식 노드 중 더 큰 노드와 부모 노드의 자리를 바꿈
- 최소 힙인 경우: 자식 노드 중 더 작은 노드와 부모 노드의 자리를 바꿈
- 크기를 비교하여 스왑(swap)하는 작업을 힙의 성질을 만족시킬 때 까지 반복
▶ 힙의 구현
- 왼쪽 자식의 index = 부모 index * 2
- 오른쪽 자식의 index = (부모 index * 2) + 1
- 부모의 index = Math.floor(자식의 인덱스 / 2)
[ 맵(Map) ]
맵은 특정 순서에 따라 키(key)와 매핑된 값(value)의 조합으로 형성된 자료 구조
즉 Key와 Value를 쌍으로 데이터를 저장하는 자료 구조
Map은 Key를 사용하여 데이터를 검색, 추가, 삭제, 수정할 수 있으며 각 Key는 고유해야 함
일반적으로 Map은 동적 크기를 갖음. 데이터가 추가되거나 삭제될 때 자동으로 크기를 조절 및 정렬
Map은 데이터를 효율적으로 저장하고 검색하기 위해 해시 함수(hash function)를 사용
JavaScript의 Map은 ECMAScript 6 (ES6) 스펙부터 공식적으로 추가됨
▶ 해시 맵
가장 일반적으로 Map이라고 불리는 자료 구조는 해시 맵 또는 해시 테이블
이 자료 구조는 키-값(key-value)쌍을 저장하고 검색하는 데 사용됨
키를 해시 함수를 통해 해싱하고 그 결과를 배열의 인덱스로 사용하여 값을 저장하거나 검색함
JavaScript에서는 Map 객체가 이러한 해시 맵을 구현하는 데 사용됨
삽입, 삭제, 검색 연산의 평균 시간 복잡도가 O(1)에 가까움
Map에서 key로 사용 가능한 데이터 타입: 문자열, 숫자, 객체, 함수 등 다양한 데이터 타입을 키로 사용 가능함
▶ 맵의 활용
Map은 데이터를 저장하고 검색하는 데 빠르고 효율적
예를 들어, 프로그래밍에서는 변수의 이름과 값을 연결하는 데 Map을 사용하거나 데이터베이스 캐싱, 웹 애플리케이션에서 사용자 세션 관리, 빅데이터 처리, 그래프 알고리즘 등 다양한 분야에서 활용됨
[ 셋(Set) ]
중복 요소가 없이 유일한 값을 저장하는 자료 구조
Map과 마찬가지로 JavaScript의 Set은 ECMAScript 6 (ES6) 스펙부터 공식적으로 추가됨
순서를 보장하지 않으므로 요소가 추가된 순서대로 나열되지 않음
중복 요소를 허용하지 않으므로 동일한 값을 여러 번 추가하더라도 하나의 값만 유지됨
따라서 중복 요소를 효과적으로 관리할 때 사용됨. 추가된 데이터는 내부적으로 항상 객체로 저장됨
원시 데이터 유형과 객체를 모두 저장할 수 있는 자료 구조. 각 요소를 구분하기 위해 데이터를 내부적으로 객체로 변환함
그러므로 원시 데이터 값이 Set에 저장되면 내부적으로 객체 형태로 변환됨
▶ 셋(Set)과 배열(Array)의 차이
중복 요소의 처리
- Set: 중복 요소를 허용하지 않음(유일성을 보장)
- 배열: 중복 요소를 허용. 동일한 값을 배열에 여러 번 추가할 수 있음
요소 순서
- Set: 요소를 저장할 때 순서를 보장하지 않음. 추가한 순서대로 요소가 저장되지 않으며 순서가 정해져 있지 않음
- 배열: 요소를 저장한 순서를 유지함. 즉, 배열에 요소를 추가한 순서대로 요소가 저장되며 순서가 중요
인덱싱
- Set: 인덱싱(indexing)을 지원하지 않음. 즉, Set에서 특정 위치의 요소에 직접 접근할 수 없음
- 배열: 요소에 대한 인덱스를 사용하여 특정 위치의 요소에 직접 접근할 수 있음
반복
- Set: forEach 메서드 또는 for...of 반복문을 사용하여 요소를 순회할 수 있음
- 배열: forEach 메서드, for...of 반복문, 또는 일반 for 반복문을 사용하여 요소를 순회할 수 있음
메서드 및 기능
- Set: 값의 유일성과 집합 연산을 지원하는 메서드(Ex. add, delete, has, clear)를 제공
- 배열: 요소의 추가, 삭제, 검색, 정렬 등 다양한 메서드와 기능(Ex. push, pop, shift, unshift, sort, filter, map) 지원
▶ 셋(Set)과 배열(Array)의 평균 시간 복잡도 비교
셋(Set)
- add(value): O(1) (해시 함수를 사용하므로 해시 충돌이 적으면 O(1))
- delete(value): O(1)
- has(value): O(1)
- size 또는 length: O(1)
배열(Array)
- push(value): O(1) (배열의 크기가 동적으로 조정되면 O(N)의 복잡도가 발생)
- pop(): O(1)
- shift(): O(N) (모든 요소를 앞으로 이동해야 하므로)
- unshift(value): O(N) (모든 요소를 뒤로 밀어야 하므로)
- splice(): O(N) (삭제 또는 삽입하는 요소의 수에 따라 다름)
Set은 요소 추가, 삭제 및 확인 연산에서 일반적으로 상수 시간 복잡도 O(1)을 가지므로 중복 요소를 허용하지 않고 요소 존재 여부를 빠르게 확인하는 데 적합
배열은 요소의 순서가 중요하거나 동적 크기 조정이 필요한 경우에 유용함
예를 들어, 인덱스를 사용하여 특정 요소에 직접 접근하거나 요소를 정렬하거나 필터링하는 경우 배열이 유용함
[ 해시 테이블(Hash Table) ]
해시 테이블은 (Key, Value)로 데이터를 저장하는 자료 구조로 빠르게 데이터를 검색할 수 있는 자료구조
매우 큰 숫자 데이터나 문자열과 같은 임의의 길이를 가진 Key값을 고정된 유한한 크기의 값으로 매핑한 테이블로 O(1)의 빠른 속도로 데이터를 찾을 수 있음
해시 테이블은 해시 함수를 사용해서 변환한 값을 배열(버킷)의 index로 정하고 값을 저장
해시 함수는 Key값을 받아 해시 함수를 사용하여 고정 크기의 해시 코드(해시 값)를 반환
해시 코드는 배열의 index로 사용되어 값을 저장하거나 검색하는 데 사용. 여기서 실제 값이 저장되는 장소를 Bucket 또는 Slot이라고 한다.
해시 함수는 여러 종류가 있고 Key를 해시 코드로 변환하고 충돌을 최소화하기 위한 목적으로 설계 됨
▶ 해시 함수의 종류
Division Method (나눗셈 방법)
키를 테이블 크기로 나눈 나머지를 해시 코드로 사용. 즉, hash(key) = key % table_size와 같은 형태로 표현
간단하고 빠르지만 특정 키 패턴에 대해서는 충돌이 발생할 수 있음
Multiplication Method (곱셈 방법)
키를 0과 1 사이의 실수로 변환한 다음 테이블 크기를 곱한 후 정수 부분을 취함
hash(key) = floor(table_size * (key * A - floor(key * A)))와 같은 형태로 표현
상수 A는 일반적으로 0보다 크고 1보다 작은 값을 사용
좋은 분포를 제공하는데 충돌을 최소화하는 데 도움이 됨
Folding Method (접기 방법)
키를 일정한 크기의 부분 키로 나누고 이를 합하여 해시 코드를 생성
예를 들어, 123456789을 12, 34, 56, 78, 9로 나누고 합쳐서 해시 코드를 생성할 수 있음
Mid-Square Method (중앙제곱 방법)
키를 제곱한 다음 중간 일부 자리를 선택하여 해시 코드로 사용
예를 들어, 1234를 제곱하면 1522756이고 여기서 중간의 3자리인 227을 해시 코드로 사용할 수 있음
SHA-1, SHA-256 등 암호학적 해시 함수
보안이 중요한 경우 암호학적 해시 함수를 사용
이러한 함수는 충돌을 최소화하고 무작위성과 안전성을 제공함
하지만 일반적인 해시 테이블에 비해 계산 비용이 높을 수 있음
▶ 시간 복잡도
- 평균: O(1), 최악: O(N)
- 각각의 Key값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 평균 O(1)의 시간복잡도로 데이터를 조회할 수 있음
- 하지만 데이터의 충돌이 발생한 경우 연결 리스트 또는 다른 자료 구조를 순회하여 검색해야 하므로 최악의 경우에는 O(N)까지 시간복잡도가 증가