👍7가지 자바스크립트 알고리즘

알고리즘은 컴퓨터 과학 분야에서 가장 기본적이고 중요한 개념 중 하나입니다. 모든 프로그래머들은 알고리즘에 대한 이해와 숙련된 구현 능력을 가지고 있어야 합니다.

왜냐하면 알고리즘이 컴퓨터 과학에서 어떠한 문제를 해결하는 데 필요한 일련의 단계와 규칙들을 제시하기 때문입니다. 그렇기 때문에 알고리즘을 이해하면 복잡한 문제를 더 효율적으로 해결할 수 있으며, 자신이 작성한 코드의 성능을 향상시키는 데도 큰 도움이 됩니다.

또한, 알고리즘은 프로그래밍 언어나 개발 분야에 상관없이 모든 프로그래머들이 공통적으로 이해할 수 있는 개념입니다. 따라서 알고리즘에 대한 이해는 프로그래밍 언어나 도구가 변하더라도 계속해서 유용하게 활용될 수 있습니다.

JavaScript에서도 다양한 알고리즘이 사용됩니다. 예를 들어, 정렬 알고리즘, 검색 알고리즘, 그래프 알고리즘 등이 있습니다. 이러한 알고리즘을 이해하고 JavaScript에서 구현할 수 있다면, 웹 애플리케이션, 데스크톱 애플리케이션, 모바일 애플리케이션 등 다양한 프로그램을 개발할 때 큰 도움이 됩니다.

이번 포스팅에서는 가장 일반적으로 사용되는 알고리즘들을 소개하고 Javascript에서 구현해보겠습니다.

---

Sorting Algorithms

정렬은 컴퓨터 과학의 기본 작업이며, 이를 위한 몇 가지 효율적인 알고리즘이 있습니다. 자바스크립트에서 가장 많이 사용되는 몇 가지 기능과 구현에 대해 살펴보겠습니다

QuickSort

QuickSort는 배열에서 "pivot" 요소를 선택하고 피벗보다 작거나 큰지에 따라 다른 요소를 두 개의 하위 배열로 분할하는 분할 및 정복 알고리즘입니다. 그런 다음 하위 배열이 재귀적으로 정렬됩니다.

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  
  const pivot = arr[Math.floor(arr.length / 2)];
  const left = [];
  const right = [];
  const equal = [];

  for (let el of arr) {
    if (el < pivot) {
      left.push(el);
    } else if (el > pivot) {
      right.push(el);
    } else {
      equal.push(el);
    }
  }

  return [...quickSort(left), ...equal, ...quickSort(right)];
}

console.log(quickSort([3, 6, 8, 10, 1, 2, 1]));

 

MergeSort

MergeSort는 배열을 두 개로 나누고 두 개의 절반을 정렬한 다음 다시 병합하는 분할 및 정복 알고리즘입니다.

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const result = [];

  while (left.length && right.length) {
    if (left[0] < right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }

  return [...result, ...left, ...right];
}

console.log(mergeSort([3, 6, 8, 10, 1, 2, 1]));

 

HeapSort

HeapSort는 입력 요소에서 힙을 빌드한 다음 힙에서 최대 요소를 반복적으로 추출하여 정렬된 출력 배열의 끝에 배치하는 비교 기반 정렬 알고리즘입니다.

function heapSort(arr) {
  function heapify(arr, n, i) {
    let largest = i;
    let l = 2 * i + 1;
    let r = 2 * i + 2;

    if (l < n && arr[l] > arr[largest]) {
      largest = l;
    }

    if (r < n && arr[r] > arr[largest]) {
      largest = r;
    }

    if (largest !== i) {
      [arr[i], arr[largest]] = [arr[largest], arr[i]];
      heapify(arr, n, largest);
    }
  }

  let n = arr.length;

  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }

  return arr;
}

console.log(heapSort([3, 6, 8, 10, 1, 2, 1]));

 

Search algorithms

Binary Search

Binary Search는 정렬된 항목 목록에서 항목을 찾기 위한 효율적인 알고리즘입니다. 대상 값을 찾을 때까지 검색 중인 배열의 절반으로 분할하는 작업을 반복합니다.

function binarySearch(arr, x) {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    let mid = Math.floor((high + low) / 2);

    if (arr[mid] < x) {
      low = mid + 1;
    } else if (arr[mid] > x) {
      high = mid - 1;
    } else {
      return mid;
    }
  }

  return -1;
}

console.log(binarySearch([1, 2, 3, 4, 5, 6, 7], 4));

Binary Search 구현에서 함수는 배열 배열 및 대상 값 x를 입력으로 사용하고 x의 인덱스가 있으면 x의 인덱스를 반환하고 -1을 반환합니다.

 

Hash Tables

Hash Table은 해시 함수를 사용하여 원하는 값을 찾을 수 있는 버킷 또는 슬롯 배열로 인덱스를 계산하는 키를 값에 매핑하는 데이터 구조입니다.

class HashTable {
  constructor() {
    this.size = 10;
    this.keys = new Array(this.size);
    this.values = new Array(this.size);
  }

  put(key, data) {
    let index = this.hashFunction(key);
    while (this.keys[index] !== undefined) {
      if (this.keys[index] === key) {
        this.values[index] = data;
        return;
      }
      index++;
      index %= this.size;
    }
    this.keys[index] = key;
    this.values[index] = data;
  }

  get(key) {
    let index = this.hashFunction(key);
    while (this.keys[index] !== undefined) {
      if (this.keys[index] === key) {
        return this.values[index];
      }
      index++;
      index %= this.size;
    }
    return undefined;
  }

  hashFunction(key) {
    let sum = 0;
    for (let i = 0; i < key.length; i++) {
      sum += key.charCodeAt(i);
    }
    return sum % this.size;
  }
}

const t = new HashTable();
t.put("apple", 10);
t.put("orange", 20);
t.put("banana", 30);
console.log(t.get("orange"));

해시 테이블 구현은 키-값 쌍을 각각 삽입하고 검색하기 위해 put 및 get 메서드가 포함된 클래스 HashTable을 사용합니다. 클래스는 또한 키-값 쌍이 저장된 내부 배열에서 인덱스를 계산하는 hashFunction 메서드를 정의합니다.

 

Graph Algorithms

그래프 알고리즘은 두 노드 사이의 최단 경로를 찾거나 그래프가 연결되어 있는지 확인하는 등 그래프와 관련된 문제를 해결하는 데 사용됩니다. 일반적인 두 가지 그래프 알고리즘을 살펴보겠습니다.

Dijkstra’s Shortest Path Algorithm

Dijkstra의 최단 경로 알고리즘은 그래프에서 노드 사이의 최단 경로를 찾는 알고리즘입니다.

1. 모든 노드에 임시 거리 값을 할당합니다. 초기 노드를 현재 노드로 설정하고 임시 거리를 0으로 표시합니다.
2. 현재 노드의 경우 모든 인접 노드를 고려하여 임시 거리를 계산합니다. 새로 계산된 임시 거리를 현재 할당된 값과 비교하고 더 작은 값을 할당합니다.
3. 현재 노드의 모든 인접 노드를 고려한 후 현재 노드를 방문한 것으로 표시합니다. 방문한 노드는 다시 확인되지 않습니다.
4. 가장 작은 임시 거리로 표시된 방문하지 않은 노드를 선택하고 새 "현재 노드"로 설정한 다음 2단계로 돌아갑니다.

function dijkstra(graph, start) {
  const visited = new Set();
  const distances = new Map();
  const prev = new Map();

  for (const node in graph) {
    distances.set(node, Infinity);
    prev.set(node, null);
  }

  distances.set(start, 0);

  while (visited.size !== Object.keys(graph).length) {
    let currNode = null;
    let currDist = Infinity;

    for (const [node, dist] of distances) {
      if (!visited.has(node) && dist < currDist) {
        currNode = node;
        currDist = dist;
      }
    }

    for (const [neighbor, weight] of graph[currNode]) {
      const dist = currDist + weight;
      if (dist < distances.get(neighbor)) {
        distances.set(neighbor, dist);
        prev.set(neighbor, currNode);
      }
    }

    visited.add(currNode);
  }

  return { distances, prev };
}

const graph = {
  A: { B: 2, C: 3 },
  B: { D: 4, E: 5 },
  C: { F: 6 },
  D: { G: 7 },
  E: { G: 8, H: 9 },
  F: { H: 10 },
  G: {},
  H: {},
};

console.log(dijkstra(graph, 'A'));

 

Breadth-First Search (BFS)

BFS 알고리즘은 다음 레벨로 진행하기 전에 그래프의 각 레벨을 탐색하여 그래프의 모든 노드를 방문합니다. 큐를 사용하여 방문할 노드를 추적합니다. 처음에는 시작 노드가 대기열에 추가됩니다. 그런 다음 대기열이 비어 있지 않은 동안 대기열의 첫 번째 노드가 제거되고 해당 노드의 인접 노드가 대기열에 추가됩니다. 각 노드가 큐에서 제거되면 동일한 노드를 다시 방문하지 않도록 방문한 것으로 표시됩니다.

class Graph {
  constructor() {
    this.nodes = [];
    this.adjacencyList = {};
  }

  addNode(node) {
    this.nodes.push(node);
    this.adjacencyList[node] = [];
  }

  addEdge(node1, node2) {
    this.adjacencyList[node1].push(node2);
    this.adjacencyList[node2].push(node1);
  }

  bfs(start) {
    const visited = {};
    const result = [];
    const queue = [start];
    visited[start] = true;

    while (queue.length > 0) {
      const current = queue.shift();
      result.push(current);

      this.adjacencyList[current].forEach((neighbor) => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.push(neighbor);
        }
      });
    }

    return result;
  }
}

const graph = new Graph();

graph.addNode("A");
graph.addNode("B");
graph.addNode("C");
graph.addNode("D");
graph.addNode("E");
graph.addNode("F");

graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "E");
graph.addEdge("D", "E");
graph.addEdge("D", "F");
graph.addEdge("E", "F");

console.log(graph.bfs("A")); // Output: ['A', 'B', 'C', 'D', 'E', 'F']

bfs 방법에서는 큐를 사용하여 방문할 노드를 추적합니다. 시작 노드를 방문하여 대기열에 추가하는 것으로 시작합니다. 그런 다음 대기열이 비어 있지 않은 동안 대기열에서 첫 번째 노드를 제거하고 결과에 추가한 다음 인접 노드를 방문합니다. 이전에 방문한 적이 없는 이웃은 방문한 것으로 표시하고 대기열 끝에 추가합니다. 대기열이 비워질 때까지 이 과정을 반복합니다. 마지막으로 결과 배열을 반환합니다.

BFS 알고리즘은 O(V+E)의 시간 복잡도를 가지며, 여기서 V는 꼭짓점의 수이고 E는 그래프의 모서리의 수이다. 큐와 방문한 노드를 저장하기 위해 추가 메모리를 사용하므로 공간 복잡성도 O(V)입니다.

Depth-First Search (DFS)

DFS는 역추적하기 전에 각 분기를 따라 가능한 한 멀리 탐색하는 순회 알고리즘입니다. 그래프 또는 트리에서 시작 노드에서 목표 노드까지의 경로를 검색하는 데 자주 사용됩니다.

class Graph {
  constructor() {
    this.nodes = [];
    this.adjacencyList = {};
  }

  addNode(node) {
    this.nodes.push(node);
    this.adjacencyList[node] = [];
  }

  addEdge(node1, node2) {
    this.adjacencyList[node1].push(node2);
    this.adjacencyList[node2].push(node1);
  }

  dfs(start) {
    const visited = {};
    const result = [];
    const adjacencyList = this.adjacencyList;

    (function dfsVisit(vertex) {
      if (!vertex) return null;
      visited[vertex] = true;
      result.push(vertex);

      adjacencyList[vertex].forEach((neighbor) => {
        if (!visited[neighbor]) {
          return dfsVisit(neighbor);
        }
      });
    })(start);

    return result;
  }
}

const graph = new Graph();

graph.addNode("A");
graph.addNode("B");
graph.addNode("C");
graph.addNode("D");
graph.addNode("E");
graph.addNode("F");

graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "E");
graph.addEdge("D", "E");
graph.addEdge("D", "F");
graph.addEdge("E", "F");

console.log(graph.dfs("A")); // Output: ['A', 'B', 'D', 'E', 'C', 'F']

위의 구현에서는 먼저 노드와 인접 목록이라는 두 가지 속성을 가진 그래프라는 클래스를 정의합니다. nodes 속성은 그래프의 모든 노드를 저장하고 adjacencyList 속성은 노드 사이의 에지를 저장합니다.

그런 다음 addNode(), addEdge() 및 dfs()의 세 가지 방법을 정의합니다. addNode() 메서드는 그래프에 새 노드를 추가하고, addEdge() 메서드는 두 노드 사이에 에지를 추가하며, dfs() 메서드는 지정된 노드에서 시작하여 깊이 우선 검색을 수행합니다.

dfs() 방법에서는 먼저 빈 방문 개체를 초기화하여 방문한 노드를 추적하고 결과 배열을 통해 노드를 방문한 순서대로 저장합니다. 그런 다음 정점을 취하고 재귀적 깊이 우선 검색을 수행하는 dfsVisit()이라는 중첩 함수를 정의합니다.

dfsVisit() 함수 내에서 먼저 현재 정점을 방문으로 표시하고 결과 배열에 추가합니다. 그런 다음 현재 정점의 인접 목록을 반복하고 방문하지 않은 각 이웃에 대해 dfsVisit() 함수를 재귀적으로 호출합니다.

마지막으로, 시작 정점으로 dfsVisit() 함수를 호출하고 결과 배열을 반환합니다.

DFS의 시간 복잡도는 O(V+E)이며, 여기서 V는 정점 수이고 E는 그래프의 가장자리 수입니다.

 

Dynamic Programming

Dynamic Programming은 문제를 더 작은 하위 문제로 나누고 중복 계산을 피하기 위해 이러한 하위 문제에 대한 솔루션을 저장하여 문제를 해결하는 기술입니다. 피보나치 시퀀스는 동적 프로그래밍을 사용하여 해결할 수 있는 문제의 전형적인 예입니다.

function fibonacci(n) {
  if (n <= 0) {
    return 0;
  } else if (n == 1) {
    return 1;
  } else {
    return fibonacci(n-1) + fibonacci(n-2);
  }
}

console.log(fibonacci(10)); // Output: 55

 

Greedy Algorithms

Greedy Algorithm은 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 함으로써 최적화 문제를 해결하는 데 사용됩니다. Huffman 코딩은 그리디 알고리즘을 사용하여 주어진 기호 집합에 대한 접두사 코드를 구성하는 무손실 데이터 압축 알고리즘입니다.

function huffmanEncoding(data) {
  const freqCounter = {};
  for (let char of data) {
    freqCounter[char] = (freqCounter[char] || 0) + 1;
  }

  const priorityQueue = new PriorityQueue();
  for (let char in freqCounter) {
    priorityQueue.enqueue(new HuffmanNode(char, freqCounter[char]));
  }

  while (priorityQueue.size() > 1) {
    const leftNode = priorityQueue.dequeue();
    const rightNode = priorityQueue.dequeue();
    const combinedFreq = leftNode.freq + rightNode.freq;
    priorityQueue.enqueue(new HuffmanNode(null, combinedFreq, leftNode, rightNode));
  }

  const huffmanCode = {};
  generateCode(priorityQueue.peek(), "", huffmanCode);

  let encodedData = "";
  for (let char of data) {
    encodedData += huffmanCode[char];
  }
  return encodedData;
}

class PriorityQueue {
  constructor() {
  this.queue = [];
}

enqueue(node) {
  let added = false;
  for (let i = 0; i < this.queue.length; i++) {
    if (node.freq < this.queue[i].freq) {
      this.queue.splice(i, 0, node);
      added = true;
      break;
    }
  }
  if (!added) {
      this.queue.push(node);
    }
  }

  dequeue() {
    return this.queue.shift();
  }

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

  peek() {
    return this.queue[0];
  }
}

class HuffmanNode {
  constructor(char, freq, left = null, right = null) {
    this.char = char;
    this.freq = freq;
    this.left = left;
    this.right = right;
  }
}

function generateCode(node, code, huffmanCode) {
  if (node.char) {
    huffmanCode[node.char] = code;
    return;
  }
  generateCode(node.left, code + "0", huffmanCode);
  generateCode(node.right, code + "1", huffmanCode);
}

console.log(huffmanEncoding("aaaaabbbcccc")); // Output: "000001111101111100010010".

 

Divide and Conquer

Divide and Conquer은 다중 분기 재귀를 기반으로 하는 알고리즘 설계 패러다임입니다. 분할 및 정복 알고리듬은 문제를 동일하거나 관련된 유형의 하위 문제로 분해하여 직접 해결할 수 있을 정도로 간단해집니다.

분할 및 정복 알고리즘을 사용하여 해결할 수 있는 문제의 전형적인 예는 병합 정렬 알고리즘입니다. 병합 정렬은 배열을 두 부분으로 나누고 각 부분을 정렬한 다음 정렬된 부분을 다시 병합하여 작동하는 비교 기반 정렬 알고리즘입니다.

앞서 작성한 MergeSort와 Binary Search 알고리즘을 사용하면 됩니다.

 

Backtracking

Backtracking은 가능한 모든 조합을 체계적인 방식으로 검색하는 것을 고려하고 특정 경로가 솔루션의 일부가 될 수 없다고 판단되는 즉시 포기하는 일반적인 알고리즘 기법입니다. N-Queens 문제는 Backtracking을 사용하여 해결할 수 있는 고전적인 문제입니다. 어떤 여왕도 다른 여왕을 공격할 수 없도록 NxN 체스판에 N개의 여왕을 배치하는 것이 목표입니다.

function solveNQueens(n) {
  const board = new Array(n).fill(null).map(() => new Array(n).fill('.'));
  const result = [];

  function couldPlace(row, col) {
    // check if a queen can be placed on board[row][col]
    // check if this row is not under attack from any previous queen in that column
    for (let i = 0; i < row; i++) {
      if (board[i][col] === 'Q') {
        return false;
      }
    }

    // check if this row is not under attack from any previous queen in the diagonal
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] === 'Q') {
        return false;
      }
    }

    // check if this row is not under attack from any previous queen in the diagonal
    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (board[i][j] === 'Q') {
        return false;
      }
    }

    return true;
  }

  function backtrack(row = 0) {
    if (row === n) {
      const temp = board.map((x) => x.join(''));
      result.push(temp);
      return;
    }

    for (let col = 0; col < n; col++) {
      if (couldPlace(row, col)) {
        board[row][col] = 'Q';
        backtrack(row + 1);
        board[row][col] = '.';
      }
    }
  }

  backtrack();

  return result;
}

console.log(solveNQueens(4));

이 알고리즘은 첫 번째 행에 여왕을 배치하기 시작하고 배치된 모든 여왕에 대해 이전 여왕의 공격을 받고 있는지 확인합니다. 그렇지 않으면 다음 행으로 이동하고 프로세스를 반복합니다. 퀸이 공격을 받는 위치에 배치되면 알고리즘이 역추적하여 다른 위치를 시도합니다. 이것은 모든 여왕들이 서로 공격하지 않고 보드에 배치될 때까지 계속됩니다.

 

결론

알고리즘의 효율적인 사용은 당면한 문제에 대한 깊은 이해와 각 알고리즘의 강점과 약점에 달려 있습니다.

문제에 적합한 알고리즘을 선택하고, 구현을 최적화하며, 시간 및 공간 복잡성을 분석하는 것은 모두 알고리즘을 최대한 활용하는 데 중요한 단계라고 생각합니다.

또한 최적의 성능을 얻으려면 데이터 구조와 입력 크기에 따라 다른 알고리즘이 필요할 수도 있습니다.