자료구조 알아보기

Taemin Jang·2024년 2월 13일

알고리즘 스터디

목록 보기

1/1

패스트캠퍼스에 있는 JavaScript로 코딩 테스트 준비하기를 참고하여 알고리즘 스터디를 진행하기로 했다.

자료구조란?

자료구조(Data Structure)는 다수의 자료를 담기 위한 구조로써 자료의 수가 많아질수록 효율적인 자료구조가 필요하다.

다양한 자료구조와 알고리즘이 있으며, 각각의 이해와 성능 비교를 통해 상황에 맞게 사용해야 한다.

제대로 이해하지 못하고 사용한다면 불필요하게 메모리와 계산을 낭비할 수 있다.

자료구조의 종류

선형 자료구조 (Linear data structure)
하나의 데이터 뒤에 다른 데이터가 하나 존재하는 자료구조로써, 데이터가 순차적으로 연결되어 있다.
ex) 배열, 연결 리스트, 스택, 큐, 덱
비선형 자료구조 (Non-Linear data structure)
하나의 데이터 뒤에 다른 데이터가 여러 개 올 수 있는 자료구조로써, 데이터가 일직선상으로 연결되어 있지 않다.
ex) 트리, 그래프

성능 측정 방법

시간 복잡도
알고리즘에 사용되는 연산 횟수를 측정한다.
공간 복잡도
알고리즘에 사용되는 메모리의 양을 측정한다.

주로 공간을 많이 사용하는 대신 시간을 단축하는, 즉 시간 복잡도를 줄이는 방법이 흔히 사용된다.

Big-O 표기법

복잡도를 표현할 때는 Big-O 표기법을 사용한다.
1. 특정한 알고리즘의 성능을 수치적으로 표현할 수 있다.
2. 가장 큰 항만 고려하는 표기법이다.
일반적으로 연산 횟수가 10억을 넘어가면 1초 이상의 시간이 소요된다.

만약 n이 1,000이라면,

O(n): 약 1,000번의 연산
O(nlogn): 약 10,000번의 연산
O(n^2): 약 1,000,000번의 연산
O(n^3): 약 1,000,000,000번의 연산

O(3n^2 + n) = O(n^2)
=> 가장 큰 항만 표시

배열(Array)

여러 개의 변수를 담는 공간으로 가장 기본적인 자료구조다.
인덱스(index)가 존재하며, 인덱스는 0부터 시작해 특정한 인덱스에 직접적으로 접근이 가능하다.
인덱스로 접근하는 수행시간은 O(1)이다.

특징

컴퓨터의 메안 메모리에서 배열의 공간은 연속적으로 할당된다.
장점은 캐시 히트 가능성이 높으며, 조회가 빠르다.
단점은 배열의 크기를 미리 지정해야하므로 데이터의 추가 및 삭제에 한계가 있다.

연결 리스트(Linked List)

배열과 다르게 크기가 정해져 있지 않고, 리스트의 크기는 동적으로 변경 가능하다.
각 노드가 한 줄로 연결되어 있고, 각 노드는 [데이터, 포인터] 형태를 가진다.

특징

컴퓨터의 메인 메모리에서 주소가 연속적이지 않다.
장점은 포인터를 통해 다음 데이터의 위치를 가리킨다는 점에서 삽입과 삭제가 간편하다. O(1)
단점은 특정 번째의 원소를 검색할 때는 앞에서부터 원소를 찾아야해서, 데이터의 검색 속도가 느리다.

배열과 연결리스트의 차이로, 배열은 특정 인덱스 조회는 O(1)로 빠르지만 특정 위치에 삽입 및 삭제 같은 경우 최악의 경우 O(N)까지 걸릴 수 있다.
그 이유는 배열의 특징으로 연속적이기 때문에 특정 위치에 삽입 및 삭제할 경우 한 칸씩 옮겨야 하므로 시간이 오래걸린다.

하지만 연결리스트는 삽입 및 삭제할 위치를 정확히 알고 있다면 위치를 한 칸씩 옮기지 않아도 가능하다.
그 이유는 포인터가 가리키는 노드만 변경시켜주면 되기 때문이다.

스택(Stack)

후입선출에 대표적인 자료구조로 새로운 값을 삽입 및 삭제할 때는 항상 마지막 위치에 해당한다.

JavaScript의 배열을 이용하면 스택을 구현할 수 있다.

push() : 배열의 마지막 위치에 원소를 삽입하며 시간 복잡도는 O(1)이다.
pop() : 배열의 마지막 위치에서 원소를 삭제하며 시간 복잡도는 O(1)이다.

큐(Queue)

선입선출에 대표적인 자료구조로 연결 리스트로 구현하면, 삽입과 삭제 시간 복잡도는 O(1)로 보장할 수 있다.

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }
  // 삽입
  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex++;
  }
  // 삭제
  dequeue() {
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return item;
  }
  // head값 가져오기
  peek() {
    return this.items[this.headIndex];
  }
  // 큐의 길이
  getLength() {
    return this.tailIndex- this.headIndex;
  }
}

트리(Tree)

가계도와 같이 계층적인 구조를 표현할 때 사용할 수 있는 자료구조로, 나무의 형태를 뒤집은 것과 같아서 Tree라고 부른다.

루트 노드(root node): 부모가 없는 최상위 노드
단말 노드(leaf node): 자식이 없는 노드
트리의 높이(height): 루트 노드에서 가장 깊은 노드까지의 길이

이진 트리(Binary Tree)

최대 2개의 자식을 가질 수 있는 트리를 말한다.

포화 이진 트리 (Full Binary Tree)
리프 노드를 제외한 모든 노드가 2개의 자식을 가지고 있어야 한다.
완전 이진 트리 (Complete Binary Tree)
모든 노드가 왼쪽 자식부터 차근 차근 채워진 트리다.
높이 균형 트리 (Height Balanced Tree)
왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1이상 차이 나지 않는 트리다.

힙(Heap)

원소들 중에서 최댓값 혹은 최솟값을 빠르게 찾아낼 수 있다.
힙은 원소의 삽입, 삭제를 위해 시간 복잡도 O(logN)이 요구된다.

최대 힙(Max Heap): 값이 큰 원소부터 추출하며, 부모 노드가 자식 노드보다 값이 큰 완전 이진 트리다.

아래 왼쪽 그림은 완전 이진 트리가 아니고, 오른쪽 그림은 자식 노드가 부모 노드보다 값이 크기 때문에 최대 힙이 아니다.

최소 힙(Min Heap): 값이 작은 원소부터 추출하며, 부모 노드가 자식 노드보다 값이 항상 작은 완전 이진 트리다.

class MinHeap {
  constructor() {
    this.heap = [];
  }

  size() {
    return this.heap.length;
  }

  swap(idx1, idx2) {
    [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
  }

  add(value) {
    this.heap.push(value);
    this.bubbleUp();
  }

  poll() {
    if (this.heap.length === 1) {
      return this.heap.pop();
    }

    const value = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();
    return value;
  }
  // MinHeap에서 삽입 연산 시 부모보다 자식이 값이 작으면 올라가는 함수
  bubbleUp() {
    let index = this.heap.length - 1;
    let parentIdx = Math.floor((index - 1) / 2);
    while (
      this.heap[parentIdx] &&
      this.heap[index][1] < this.heap[parentIdx][1]
    ) {
      this.swap(index, parentIdx);
      index = parentIdx;
      parentIdx = Math.floor((index - 1) / 2);
    }
  }
  // MinHeap에서 삭제 연산 시 정렬해주는 함수
  bubbleDown() {
    let index = 0;
    let leftIdx = index * 2 + 1;
    let rightIdx = index * 2 + 2;

    while (
      (this.heap[leftIdx] && this.heap[leftIdx][1] < this.heap[index][1]) ||
      (this.heap[rightIdx] && this.heap[rightIdx][1] < this.heap[index][1])
    ) {
      let smallerIdx = leftIdx;
      if (
        this.heap[rightIdx] &&
        this.heap[rightIdx][1] < this.heap[smallerIdx][1]
      ) {
        smallerIdx = rightIdx;
      }

      this.swap(index, smallerIdx);
      index = smallerIdx;
      leftIdx = index * 2 + 1;
      rightIdx = index * 2 + 2;
    }
  }
}