[JS] 자료구조 기본 코드 정리

김현수·2023년 11월 17일

자료구조

목록 보기

1/8

🖋️ 자료구조 정리

`해시`

빠른 데이터 검색 및 관리가 필요할 때 적합
특징

  * 키-값 쌍으로 데이터 저장
  * 데이터에 빠르게 접근 가능하도록 설계된 자료구조
  * Javascript 에서는 객체 또는 Map 객체를 사용하여
    해시 테이블을 구현 가능

사용 예

  * 데이터 저장, 검색, 삭제 등 O(1)의 시간복잡도 제공
  * 중복 제거, 데이터의 존재 유무를 빠르게 확인할 때 유용

문제 예

  * 문자열 내 문자의 빈도 수 계산
  * 중복 요소 찾기 또는 제거
  * 집합 연산 (교집합, 합집합 등)

기본 기능 CODE

// 해시 테이블 구현 예시 (JavaScript 객체 사용)
let hash = {
  "key1": "value1",
  "key2": "value2"
};

// 값 접근
console.log(hash["key1"]); // 출력: value1

// 새로운 키-값 추가
hash["key3"] = "value3";

// Map을 사용하는 경우
let map = new Map();
map.set("key1", "value1");
map.set("key2", "value2");
map.set("key3", "value3");

// 값 접근
console.log(map.get("key1")); // 출력: value1

// 존재 여부 확인
console.log(map.has("key2")); // 출력: true


// 특정 데이터 삭제
map.delete("key2");

console.log(map); // 출력: Map { 'key1' => 'value1', 'key3' => 'value3' }

정렬 CODE

// 정렬 
let map = new Map();

map.set("b", "value2");
map.set("a", "value1");
map.set("c", "value3");

// 키를 기준으로 정렬
let sortedByKey = new Map([...map.entries()].sort());

console.log(sortedByKey); // 출력: Map { 'a' => 'value1', 'b' => 'value2', 'c' => 'value3' }

`스택 / 큐`

데이터의 순서와 처리 방식이 중요할 때 유용

스택 특징

  * 후입선출(LIFO, Last In First Out) 구조
  * JavaScript에서는 배열을 사용하여 스택을 구현할 수 있으며
    push()와 pop() 메서드로 데이터를 관리

큐 특징

   * 선입선출(FIFO, First In First Out) 구조
   * JavaScript에서는 배열을 사용하여 큐를 구현하며
     push()로 데이터를 추가하고 shift()로 데이터를 제거

사용 예

   * 스택은 괄호 매칭, 후위 표기법 계산 등에 사용
   * 큐는 데이터가 순차적으로 처리되어야 하는 경우(예: 태스크 스케줄링)에 사용

문제 예

   * 괄호의 유효성 검사
   * 역순 문자열 생성
   * BFS(너비 우선 탐색) 구현 시 큐 사용

스택 CODE

// 스택 구현 예시
let stack = [];

// 요소 추가
stack.push("element1");
stack.push("element2");

// 요소 제거 및 반환
console.log(stack.pop()); // 출력: element2

// 스택의 맨 위 요소 확인
console.log(stack[stack.length - 1]); // 출력: element1

큐 CODE

// 큐 구현 예시
let queue = [];

// 요소 추가
queue.push("element1");
queue.push("element2");

// 요소 제거 및 반환
console.log(queue.shift()); // 출력: element1

// 큐의 첫 번째 요소 확인
console.log(queue[0]); // 출력: element2

`힙`

데이터 중 최댓값 또는 최솟값에 빠르게 접근해야 할 때 사용

특징

 * 완전 이진 트리의 형태를 가진 자료구조
 * 최대 힙(max heap)과 최소 힙(min heap)이 있으며, 
   각각 최대값, 최소값을 빠르게 찾는 데 유용
 * JavaScript에서는 배열을 사용하여 힙을 구현

사용 예

 * 우선순위가 있는 데이터의 관리에 사용
 * 데이터의 정렬, 특히 힙 정렬에 사용

문제 예

  * 최대값, 최소값 찾기
  * 우선순위 큐 구현
  * 힙 정렬

최소 힙 CODE

// 최소 힙 구현 예시
class MinHeap {
  constructor() {
    this.heap = [];
  }

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

 bubbleUp() {
   let index = this.heap.length - 1;
   while (index > 0) {
    let element = this.heap[index];
    let parentIndex = Math.floor((index - 1) / 2);
    let parent = this.heap[parentIndex];

    if (parent <= element) break;
    this.heap[index] = parent;
    this.heap[parentIndex] = element;
    index = parentIndex;
   }
 }

 // 추가 메서드 (extractMin, sinkDown, 등) 필요
}

// 사용 예시
let minHeap = new MinHeap();
minHeap.insert(2);
minHeap.insert(3);
minHeap.insert(1);

console.log(minHeap.heap); // 출력: [1, 3, 2] - 최소값이 맨 앞에 위치

`그래프`

복잡한 관계와 네트워크를 모델링하고 탐색할 때 필요

특징

 * 네트워크 경로 탐색, 사회 네트워크 서비스의 친구 관계 등 
   복잡한 관계를 모델링하는 데 사용
 * 비순환 그래프(ACYCLIC)와 순환 그래프(CYCLIC), 
   방향 그래프(DIRECTED)와 무방향 그래프(UNDIRECTED) 등 다양한 형태

사용 예

 * 그래프는 복잡한 네트워크 구조를 표현하고 탐색하는 데 사용
 * 그래프 알고리즘에는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS), 
   최단 경로 찾기(예: 다익스트라 알고리즘), 최소 신장 트리(예: 크루스칼 알고리즘) 등

문제 예

  * 네트워크 연결 구성 요소 찾기
  * 최단 경로 계산
  * 사이클 감지

객체를 사용한 인접 리스트 CODE

// 그래프 구현 예시
class Graph {
  constructor() {
    this.adjacencyList = {};
  }

 addVertex(vertex) {
   if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
 }

 addEdge(vertex1, vertex2) {
   this.adjacencyList[vertex1].push(vertex2);
   this.adjacencyList[vertex2].push(vertex1);
 }

// 추가 메서드 (removeVertex, removeEdge 등) 필요
}

// 사용 예시
let graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addEdge("A", "B");

console.log(graph.adjacencyList); // 출력: { A: [ 'B' ], B: [ 'A' ] }

김현수

일단 한다

다음 포스트

[JS] 자료구조 기본 코드 정리

자료구조

🖋️ 자료구조 정리

`해시`

`스택 / 큐`

`힙`

`그래프`

[JS] 자료구조의 특징과 설명

0개의 댓글