JavaScript 자료구조

1. 자료 구조(Data Structure)란?

• 다수의 자료(data)를 담기 위한 구조
• 데이터의 수가 많아질수록 효율적인 자료 구조가 필요하다.
  ==> ex) 학생 수가 1,000,000명 이상인 학생 관리 프로그램
• 따라서 자료 구조의 필요성에 대해서 이해할 필요가 있다.
• 성능 비교: 자료구조/알고리즘의 성능 측정 방법에 대해 이해할 필요가 있다.
• 데이터를 효과적으로 저장하고, 처리하는 방법에 대해 바르게 이해할 필요가 있다.
• 자료구조를 제대로 이해하지 못하면 불필요하게 메모리와 계산을 낭비할 여지가 있다.

2. 자료 구조의 종류

• 선형 구조 (linear data structure)
  • 하나의 데이터 뒤에 다른 데이터가 하나 존재하는 자료구조
  • 데이터가 연속적(순차적)으로 연결되어 있다.
  • 배열 (Array)
  • 연결 리스트 (linked list)
  • 스택 (stack)
  • 큐 (queue)
• 비선형 구조(non-linear dtat structure)
  • 하나의 데이터 뒤에 다른 데이터가 여러 개 올 수 있는 자료구조
  • 데이터가 일직선상으로 연결되어 있지 않아도 된다.
  • 트리 (tree)
  • 그래프 (graph)

3. 자료 구조와 알고리즘

• 자료 구조와 알고리즘
  • 효율적인 자료구조 설계를 위해 알고리즘 지식이 필요
  • 효율적인 알고리즘을 작성하기 위해서 문제 상황에 맞는 적절한 자료구조가 사용되어야 한다.
  • 프로그램을 작성할 때 자료구조와 알고리즘 모두 고려해야 한다.
• 프로그램의 성능 측정 방법
  • 시간 복잡도(time complexity): 알고리즘에 사용되는 연산 횟수를 측정
  • 공간 복잡도(space complexity): 알고리즘에 사용되는 메모리의 양을 측정
  • 공간을 많이 사용하는 대신 시간을 단축하는 방법이 흔히 사용된다.
• Big-O 표기법
  • 특정한 알고리즘이 얼마나 효율적인지 수치적으로 표현할 수 있다.
  • 가장 빠르게 증가하는 항만을 고려하는 표기법(가장 큰 항만을 고려하면 된다.)

4. 배열(Array)과 리스트(List)

• 배열 (Array)
  • 가장 기본적인 자료구조
  • 여러 개의 변수를 담는 공간으로 이해 가능
  • 배열은 인덱스(index)가 존재, index는 0부터 시작
  • 특정한 인덱스에 직접적으로 접근 가능 => 수행 시간: O(1)
  • 컴퓨터의 메인 메모리에서 배열의 공간은 연속적으로 할당된다.
    ==> 장점: 캐시(cache) 히트 가능성이 높으며, 조회가 빠르다.
    ==> 단점: 배열의 크기를 미리 지정해야 하는 것이 일반적이므로, 데이터의 추가 및 삭제에 한계가 있다.
• 연결 리스트(Linked List)
  • 컴퓨터의 메인 메모리상에서 주소가 연속적이지 않다.
  • 배열과 다르게 크기가 정해져 있지 않고, 리스트의 크기는 동적으로 변경 가능
    ==> 장점: 포인터(pointer)를 통해 다음 데이터의 위치를 가리킨다는 점에서 삽입과 삭제가 간편
    ==> 단점: 특정 번째의 원소를 검색할 때는 앞에서부터 원소를 찾아야 하므로, 데이터 검색 속도가 느리다.
• JavaScript의 배열
  • 배열 기능을 제공
  • 일반 배열처럼 임의의 인덱스를 이용해 직접적인 접근이 가능
  • 동적 배열의 기능을 제공하여, 맨 뒤의 위치에 원소 추가가 가능
  • 배열의 용량이 가득 차면, 자동으로 크기를 증가
  • 내부적으로 포인터(pointer)를 사용, 연결 리스트의 장점도 가지고 있다.

3. 스택(Stack)

• 먼저 들어온 데이터가 나중에 나가는 자료 구조
• 박스를 쌓는 형태와 같다.
• 스택 자료구조의 시간 복잡도

• JavaScript의 기본적인 배열 자료형은 push() 메서드와 pop() 메서드를 제공한다.
• 스택을 연결 리스트로 구현하면, 삽입과 삭제 있어서 0(1)을 보장할 수 있다.
• 연결 리스트로 구현할 때는 머리(head)를 가리키는 하나의 포인터만 가진다.
• 머리(head): 남아있는 원소 중 가장 마지막에 들엉온 데이터를 가리키는 포인터

4. 큐(Queue)

• 먼저 삽입된 데이터가 먼저 추출되는 자료 구조
  ==> ex) 게임 대기 큐는 먼저 대기한 사람이 먼저 게임에 매칭된다.
• 큐를 연결 리스트로 구현하면, 삽입과 삭제에 있어서 O(1)을 보장할 수 있다.
• 연결 리스트로 구현할 때는 머리(head)와 꼬리(tail) 두 개의 포인터를 가진다.
• 머리(head): 남아있는 원소 중 가장 먼저 들어 온 데이터를 가리키는 포인터 (삭제 시 머리에서 꺼낸다.)
• 꼬리(tail): 남아있는 원소 중 가장 마지막에 들어 온 데이터를 가리키는 포인터 (삽입 시 꼬리에 넣는다.)
• 큐 동작 속도: 배열 vs .연결 리스트
  • 다수의 데이터를 삽입 및 삭제할 때에 대하여, 수행 시간을 측정할 수 있다.
  • 단순히 배열 자료형을 이용할 때보다 연결 리스트를 사용할 때 수행 시간 관점에서 효율적이다.
  • JavaScript에서는 Dictionary 자료형을 이용하여 큐(queue)를 구현하면 간단

5. 트리(Tree)와 우선순위 큐(Priority Queue)

• 가계도와 같이 계층적인 구조를 표현할 때 사용할 수 있는 자료 구조
• 트리 용어 정리
  • 루트 노드(root node): 부모가 없는 최상위 노드
  • 단말 노드(leaf node): 자식이 없는 노드
    ==> 부모와 자식 관계가 성립한다.
  • 형제 관계: 같은 부모 노드를 가지고 있는 노드 사이를 형제 관계라 한다.
  • 깊이(depth): 루트 노드에서의 길이(length)
  • 길이란 출발 노드에서 목적지 노드까지 거쳐야 하는 간선의 수를 의미
  • 높이(height)는 루트 노드에서 가장 깊은 노드까지의 길이를 의미
• 이진 트리(Binary Tree)
  • 최대 2개의 자식을 가질 수 있는 트리
• 우선순위 큐(Priority Queue)
  • 우선 순위에 따라서 데이터를 추출하는 자료 구조
  • 컴퓨터 운영체제, 온라인 게임 매칭 등에서 활용
  • 우선순위 큐는 일반적으로 힙(heap)을 이용해 구현한다.
• 포화 이진 트리(Full Minary Tree)
  • 리프 노드를 제외한 모든 노드가 두 자식을 가지고 있는 트리
• 완전 이진 트리(Complete Binary Tree)
  • 모든 노드가 왼쪽 자식부터 차근차근 채워진 트리다.
• 높이 균형 트리(Height Balanced Tree)
  • 왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1 이상 차이 나지 않는 트리
• 힙(Heap)
  • 원소들 중에서 최댓값 혹은 최솟값을 빠르게 찾아내는 자료구조
  • 최대 힙(max heap): 값이  큰 원소부터 추출한다.
    ==> 부모 노드가 자식 노드보다 값이 큰 완전 이진 트리를 의미
    ==> 루트 노드는 전체 트리에서 가장 큰 값을 가진다, 값이 큰 데이터가 우선 
  • 최소 힙(min heap): 값이 작은 원소부터 추출한다.
    ==> 부모 노드가 자식 노드보다 값이 작은 완전 이진 트리를 의미
    ==> 루트 노드가 전체 트리에서 가장 작으며, 값이 작 데이터가 우선 
  • 힙은 원소의 삽입과 삭제를 위해 O(logN)의 수행 시간을 요구한다.
  • 단순한 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작어은 정렬과 동일하다.
  • 이럴 경우 시간 복잡도는 O(NlogN)이다.
• 힙(Heap)의 특징
  • 완전 이진 트리 자료구조
  • 우선순외가 높은 노드가 루트(root)에 위치한다.
• 최소 힙 구성 함수: Heapify
  • 부모로 거슬러 올라가며, 부무보다 자신이 더 작은 경우에 위치를 교체한다. (상향식)
  • 새로운 원소가 삽입되었을 때 O(logN)의 시간 복잡도르 힙 성질을 유지하도록 할 수 있다.
• 힙에 새로운 원소가 삭제될 떄
  • 원소가 제거되었을 때 O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다.
  • 원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 한다.
  • 원소가 제거되었을 때 O(logN)의 시간 복작도로 힙 성질을 유지하도록 할 수 있다.
  • 이후에 루트 노드에서부터 하향식으로(더 작은 자식 노드로) heapify()를 진행한다.

6. 그래프(Graph)

• 사물을 정점(vertex)과 간선(edge)으로 나타내기 위한 도구
• 그래프를 구현하는 두 가지 방식
  1. 인접 행렬(adjacency matrix): 2차원 배열을 사용하는 방식
     • 무방향 무가중치 그래프 
       • 모든 간선이 방향성을 가지지 않는 그래프를 무방향 그래프라고 한다.
       • 모든 간선에 가중치가 없는 그래프를 무가중치 그래프라고 한다.
       • 무방향 비가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 행렬로 출력할 수 있다.
     • 방향 가중치 그래프
       • 모든 간선이 방향을 가지는 그래프를 방향 그래프라고 한다.
       • 모든 간선에 가중치가 있는 그래프를 가중치 그래프라고 한다.
       • 방향 가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 행렬로 출력할 수 있다.
  2. 인접 리스트(adjacency list): 연결 리스트를 이용하는 방식
     • 무방향 무가중치 그래프
       • 모든 간선이 방향성을 가지지 않는 그래프를 무방향 그래프라고 한다.
       • 모든 간선에 가중치가 없는 그래프를 무가중치 그래프라고 한다.
       • 무방향 비가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 리스트로 출력할 수 있다.
     • 방향 가중치 그래프
       • 모든 간선이 방향을 가지는 그래프를 방향 그래프라고 한다.
       • 모든 간선에 가중치가 있는 그래프를 가중치 그래프라고 한다.
       • 방향 가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 리스트로 출력할 수 있다.
• 그래프의 시간 복잡도
  • 인접 행렬: 모든 정점들의 연결 여부를 저장해 O(V^2)의 공간을 요구한다.
    ==> 공간 효율성이 떨어지지만, 두 노드의 연결 여부를 O(1)에 확인할 수 있다.
  • 인접 리스트: 연결된 간선의 정보만을 저장하여 O(V+E)의 공간을 요구한다.
    ==> 공간 효율성이 우수하지만, 두 노드의 연결 여부를 확인하기 위해 O(V)의 시간이 필요하다.
• 인접 행렬 vs. 인접 리스트
  • 최단 경로 알고리즘을 구현할 때, 각각 근처의 노드와 연결되어 있는 경우가 많으므로, 간선 개수가 적어 인접 리스트가 유리하다.