Data Structure 실전 프로젝트 가이드

실무에서 자주 사용되는 자료구조를 활용한 프로젝트 예제를 소개합니다. Stack, Queue, Tree, Graph 등 핵심 자료구조를 TypeScript로 구현하고 실전 활용법을 배웁니다.

---

---

들어가며

이 글에서는 Data Structure 실전 프로젝트 가이드에 대해 상세히 알아보겠습니다. 총 10가지 주요 개념을 다루며, 각각의 개념에 대한 설명과 실제 코드 예제를 함께 제공합니다.

목차

1. Stack으로_되돌리기_기능_구현
2. Queue로_작업_스케줄러_만들기
3. LRU_Cache로_성능_최적화
4. Tree로_파일_시스템_구현
5. Graph로_친구_추천_시스템
6. Trie로_자동완성_검색
7. Heap으로_우선순위_큐_구현
8. Hash_Table로_중복_제거_시스템
9. Linked_List로_실시간_플레이리스트
10. Binary_Search_Tree로_정렬된_데이터_관리

---

1. Stack으로 되돌리기 기능 구현

개요

브라우저의 뒤로가기나 에디터의 Undo 기능처럼 Stack을 활용한 히스토리 관리 시스템입니다.

코드 예제

class HistoryStack<T> {
  private stack: T[] = [];

  push(item: T): void {
    this.stack.push(item);
  }

  undo(): T | undefined {
    return this.stack.pop();
  }

  peek(): T | undefined {
    return this.stack[this.stack.length - 1];
  }
}

설명

Stack의 LIFO(Last In First Out) 특성을 활용하여 사용자 액션을 저장하고 되돌릴 수 있습니다.

---

2. Queue로 작업 스케줄러 만들기

개요

비동기 작업을 순차적으로 처리하는 태스크 큐 시스템입니다. API 호출 제한이나 순차 처리가 필요할 때 유용합니다.

코드 예제

class TaskQueue {
  private queue: (() => Promise<any>)[] = [];
  private processing = false;

  async add(task: () => Promise<any>): Promise<void> {
    this.queue.push(task);
    if (!this.processing) await this.process();
  }

  private async process(): Promise<void> {
    this.processing = true;
    while (this.queue.length > 0) {
      const task = this.queue.shift()!;
      await task();
    }
    this.processing = false;
  }
}

설명

Queue의 FIFO(First In First Out) 원칙으로 작업을 순서대로 처리하며, 동시 실행을 방지합니다.

---

3. LRU Cache로 성능 최적화

개요

최근 사용한 데이터를 우선 보관하는 캐시 시스템으로 API 응답이나 계산 결과를 저장합니다.

코드 예제

class LRUCache<K, V> {
  private cache = new Map<K, V>();

  constructor(private capacity: number) {}

  get(key: K): V | undefined {
    if (!this.cache.has(key)) return undefined;
    const value = this.cache.get(key)!;
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key: K, value: V): void {
    if (this.cache.has(key)) this.cache.delete(key);
    else if (this.cache.size >= this.capacity) {
      this.cache.delete(this.cache.keys().next().value);
    }
    this.cache.set(key, value);
  }
}

설명

Map의 삽입 순서 보장 특성을 활용해 가장 오래된 항목을 자동으로 삭제하는 효율적인 캐시를 구현합니다.

---

4. Tree로 파일 시스템 구현

개요

폴더와 파일의 계층 구조를 표현하는 트리 자료구조입니다. 재귀적 탐색과 경로 검색이 가능합니다.

코드 예제

interface TreeNode {
  name: string;
  type: 'file' | 'folder';
  children?: TreeNode[];
}

function findPath(node: TreeNode, target: string, path = ''): string | null {
  const currentPath = path + '/' + node.name;
  if (node.name === target) return currentPath;

  if (node.children) {
    for (const child of node.children) {
      const result = findPath(child, target, currentPath);
      if (result) return result;
    }
  }
  return null;
}

설명

트리의 재귀적 특성으로 파일 시스템을 탐색하고 특정 파일의 전체 경로를 찾을 수 있습니다.

---

5. Graph로 친구 추천 시스템

개요

소셜 네트워크에서 친구의 친구를 찾는 추천 알고리즘입니다. BFS를 활용한 최단 거리 탐색입니다.

코드 예제

class SocialGraph {
  private graph = new Map<string, Set<string>>();

  addFriend(user: string, friend: string): void {
    if (!this.graph.has(user)) this.graph.set(user, new Set());
    if (!this.graph.has(friend)) this.graph.set(friend, new Set());
    this.graph.get(user)!.add(friend);
    this.graph.get(friend)!.add(user);
  }

  getSuggestions(user: string): string[] {
    const friends = this.graph.get(user) || new Set();
    const suggestions = new Set<string>();

    friends.forEach(friend => {
      this.graph.get(friend)?.forEach(fof => {
        if (fof !== user && !friends.has(fof)) {
          suggestions.add(fof);
        }
      });
    });
    return Array.from(suggestions);
  }
}

설명

그래프의 인접 노드를 탐색하여 2촌 관계의 사용자를 추천 목록으로 제공합니다.

---

6. Trie로 자동완성 검색

개요

검색어 자동완성 기능을 구현하는 Trie 자료구조입니다. 효율적인 문자열 검색이 가능합니다.

코드 예제

class TrieNode {
  children = new Map<string, TrieNode>();
  isEnd = false;
}

class AutoComplete {
  private root = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.isEnd = true;
  }

  search(prefix: string): boolean {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) return false;
      node = node.children.get(char)!;
    }
    return true;
  }
}

설명

Trie는 문자열 검색에 최적화된 트리로, O(m) 시간에 검색어 존재 여부를 확인할 수 있습니다.

---

7. Heap으로 우선순위 큐 구현

개요

중요도가 높은 작업을 먼저 처리하는 우선순위 큐입니다. 알림 시스템이나 작업 스케줄링에 활용됩니다.

코드 예제

class PriorityQueue<T> {
  private heap: { priority: number; item: T }[] = [];

  enqueue(item: T, priority: number): void {
    this.heap.push({ priority, item });
    this.heap.sort((a, b) => b.priority - a.priority);
  }

  dequeue(): T | undefined {
    return this.heap.shift()?.item;
  }

  peek(): T | undefined {
    return this.heap[0]?.item;
  }

  isEmpty(): boolean {
    return this.heap.length === 0;
  }
}

설명

우선순위에 따라 자동으로 정렬되어 가장 중요한 항목을 항상 먼저 처리할 수 있습니다.

---

8. Hash Table로 중복 제거 시스템

개요

대량의 데이터에서 중복을 빠르게 찾아내는 해시 기반 중복 검사 시스템입니다.

코드 예제

class DuplicateDetector<T> {
  private seen = new Set<string>();

  add(item: T): boolean {
    const key = JSON.stringify(item);
    if (this.seen.has(key)) {
      return false;
    }
    this.seen.add(key);
    return true;
  }

  hasDuplicate(item: T): boolean {
    return this.seen.has(JSON.stringify(item));
  }

  clear(): void {
    this.seen.clear();
  }
}

설명

Set의 해시 기반 검색으로 O(1) 시간에 중복을 감지하여 대용량 데이터 처리에 효율적입니다.

---

9. Linked List로 실시간 플레이리스트

개요

노래를 추가/삭제하기 쉬운 음악 플레이리스트입니다. 중간 삽입과 삭제가 빈번한 경우 유용합니다.

코드 예제

class Song {
  constructor(public title: string, public next: Song | null = null) {}
}

class Playlist {
  private head: Song | null = null;

  add(title: string): void {
    const newSong = new Song(title);
    if (!this.head) {
      this.head = newSong;
    } else {
      let current = this.head;
      while (current.next) current = current.next;
      current.next = newSong;
    }
  }

  remove(title: string): boolean {
    if (!this.head) return false;
    if (this.head.title === title) {
      this.head = this.head.next;
      return true;
    }
    let current = this.head;
    while (current.next && current.next.title !== title) {
      current = current.next;
    }
    if (current.next) {
      current.next = current.next.next;
      return true;
    }
    return false;
  }
}

설명

Linked List는 배열과 달리 중간 노드 삭제 시 전체 재배열이 필요 없어 동적 목록 관리에 적합합니다.

---

10. Binary Search Tree로 정렬된 데이터 관리

개요

자동으로 정렬된 상태를 유지하는 이진 탐색 트리입니다. 빠른 검색과 정렬이 필요한 경우 사용합니다.

코드 예제

class BSTNode {
  constructor(
    public value: number,
    public left: BSTNode | null = null,
    public right: BSTNode | null = null
  ) {}
}

class BST {
  private root: BSTNode | null = null;

  insert(value: number): void {
    this.root = this.insertNode(this.root, value);
  }

  private insertNode(node: BSTNode | null, value: number): BSTNode {
    if (!node) return new BSTNode(value);
    if (value < node.value) node.left = this.insertNode(node.left, value);
    else node.right = this.insertNode(node.right, value);
    return node;
  }
}

설명

BST는 삽입과 동시에 정렬을 유지하며, 평균 O(log n) 시간에 검색/삽입/삭제가 가능합니다.

---

마치며

이번 글에서는 Data Structure 실전 프로젝트 가이드에 대해 알아보았습니다. 총 10가지 개념을 다루었으며, 각각의 사용법과 예제를 살펴보았습니다.

관련 태그

#TypeScript #DataStructure #Stack #Queue #Tree