자료구조

hojoon·2024년 1월 30일

코딩테스트

목록 보기

4/5

자료구조

자료구조는 다수의 데이터를 담기 위한 구조이다.
성능 비교 : 자료구조/알고리즘의 성능 측정 방법에 대해 이해할 필요가 있음

O(log N), O(N)의 차이를 알자

1. 선형 구조

선형 자료구조는 하나의 데이터 뒤에 다른 데이터가 하나 존재하는 자료구조다.
데이터가 일렬로 연속적으로 연결되어 있다.

2. 비선형 구조

하나의 데이터 뒤에 다른 데이터가 여러 개 올 수 있는 자료구조다.
데이터가 일직선상으로 연결되어 있지 않아도 된다. (트리, 그래프)

시간복잡도

알고리즘에 사용되는 연산 횟수를 측정

공간 복잡도

알고리즘에 사용되는 메모리의 양을 측정한다.

복잡도를 표현할 대는 Big-O 표기법을 사용한다.

특정한 알고리즘이 얼마나 효율적인지 수치적으로 표현할 수 있다.
가장 빠르게 증가하는 항만을 고려하는 표기법이다.

이중 for문 같은 경우는 O(n^2)

일반적으로 연산 횟수가 10억을 넘어가면 1초 이상의 시간이 소요된다.

배열

가장 기본적인 자료구조
여러 개의 변수를 담는 공간으로 이해할 수 있다.
배열은 인덱스가 존재하며, 인덱스는 0부터 시작한다.
특정한 인덱스에 직접적으로 접근 가능 -> 수행 시간 : O(1)
컴퓨터의 메인 메모리에서 배열의 공간은 연속적으로 할당된다.
- 장점 : 캐시 히트 가능성이 높으며, 조회가 빠르다.
- 단점 : 배열의 크기를 미리 지정해야 하는 것이 일반적이므로, 데이터의 추가 및 삭제에 한계가 있다.

연결 리스트

연결 리스트는 컴퓨터의 메인 메모리상에서 주소가 연속적이지 않다.
배열과 다르게 크기가 정해져 있지 않고, 리스트의 크기는 동적으로 변경 가능하다.

2차원 배열 만들기

let arr = Array.from(Array(4), ()=> new Array(5))

자바스크립트의 배열은 연결리스트 구조의 배열이다

자료의 위치를 가지고 있는 포인터를 가지고 있다.

스택

먼저 들어온 데이터가 나중에 나가는 자료구조
흔히 박스가 쌓인 형태를 스택이라고 한다.
우리가 박스를 쌓은 뒤에 꺼낼 때는, 가장 마지막에 올렸던 박스부터 꺼내야 한다.

스택이 가지고 있는 연산

삽입 push : 스택에 원소를 삽입하는 연산
추출 pop : 스택에서 원소를 추출하는 연산
최상위 원소 top : 스택의 최상위 원소를 확인하는 연산
Empty : 스택이 비어 있는지 확인하는 연산

자바스크립트는 기본적으로 push, pop 제공
일반적으로 스택을 구현할때 자바스크립트의 배열을 자료형을 사용한다.

let stack = []
stack.push(5)
stack.push(2)
stack.push(7)
stack.pop()
stack.push(5)
stack.pop()

reverse를 사용하면 최상단 원소부터 확일 할 수 있음.

큐

먼저 삽입된 데이터가 먼저 추출되는 자료구조다.
게임 큐와 같이 먼저 대기한 사람이 먼저 게임에 매칭된다.
큐를 연결리스트로 구현하면, 삽입과 삭제에 있어서 O(1)을 보장할 수 있다.
연결 리스트로 구현할 때 머리와 꼬리 두 개의 포인터를 가진다.
머리 : 남아있는 원소 중 가장 먼저 들어 온 데이터를 가리키는 포인터
꼬리 : 남아있는 원소 중 가장 마지막에 들어 온 데이터를 가리키는 포인터

자바스크립트에서는 Dictionary 자료형을 이용하여 큐를 구현하면 간단하다.
일반 배열로 구현하면 비효율적.

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;
  }
  peek() {
    return this.items[this.headIndex];
  }
  getLength() {
    return (this.tailIndex = this.headIndex);
  }
}

이해가 안가면 따라 쳐보면 된다.

const 큐 = {
  0: 5,
  1: 2,
  2: 3,
  3: 7,
  //0
  //4
};

const deq = {
  // 0:5
  0: 2,
  1: 3,
  2: 7,
  //1
  //4
};

const enq = {
  0: 2,
  1: 3,
  2: 7,
  5: 1,
  //1
  //5
};

const enq2 = {
  0: 2,
  1: 3,
  2: 7,
  5: 1,
  6: 4,
  // 1
  // 6
};

const deq2 = {
  //0: 2,
  1: 3,
  2: 7,
  5: 1,
  6: 4,
  // 2
  // 6
  // getLength = 4 (tail - head)
};