코딩테스트에 자주 나오는 알고리즘 정리

• DFS/BFS
• 정렬
• 이진 탐색
• 최단 경로
• 최소비용

 

최소비용

 - 크루스칼 알고리즘(최소 비용 신장 트리) : O(E log E + E)

class DisjointSet {
  constructor() {
    this.parent = {};
    this.rank = {};
  }

  makeSet(vertex) {
    this.parent[vertex] = vertex;
    this.rank[vertex] = 0;
  }

  find(vertex) {
    if (this.parent[vertex] !== vertex) {
      this.parent[vertex] = this.find(this.parent[vertex]);
    }
    return this.parent[vertex];
  }

  union(vertex1, vertex2) {
    const root1 = this.find(vertex1);
    const root2 = this.find(vertex2);

    if (root1 !== root2) {
      if (this.rank[root1] < this.rank[root2]) {
        this.parent[root1] = root2;
      } else if (this.rank[root1] > this.rank[root2]) {
        this.parent[root2] = root1;
      } else {
        this.parent[root2] = root1;
        this.rank[root1]++;
      }
    }
  }
}

function kruskal(graph) {
  const edges = [];
  const minimumSpanningTree = [];

  // 모든 간선 추출
  for (let vertex in graph) {
    for (let neighbor in graph[vertex]) {
      edges.push([vertex, neighbor, graph[vertex][neighbor]]);
    }
  }

  // 간선 가중치를 기준으로 정렬
  edges.sort((a, b) => a[2] - b[2]);

  const disjointSet = new DisjointSet();

  // 각 정점에 대해 독립적인 집합 생성
  for (let vertex in graph) {
    disjointSet.makeSet(vertex);
  }

  // 가장 작은 가중치 간선부터 선택
  for (let edge of edges) {
    const [vertex1, vertex2, weight] = edge;

    // 사이클이 생성되지 않는 경우에만 간선 선택
    if (disjointSet.find(vertex1) !== disjointSet.find(vertex2)) {
      disjointSet.union(vertex1, vertex2);
      minimumSpanningTree.push(edge);
    }
  }

  return minimumSpanningTree;
}

// 그래프 정의
const graph = {
  A: { B: 7, D: 5 },
  B: { A: 7, D: 9, C: 8, E: 7 },
  C: { B: 8, E: 5 },
  D: { A: 5, B: 9, E: 15, F: 6 },
  E: { B: 7, C: 5, D: 15, F: 8, G: 9 },
  F: { D: 6, E: 8, G: 11 },
  G: { E: 9, F: 11 },
};

// 테스트
const minimumSpanningTree = kruskal(graph);
console.log(minimumSpanningTree);

 

 

 

  - 개선된 프림 알고리즘(최소 비용 신장 트리) : O(E log E + V) 

          * 기존 우선순위 큐를 힙 자료구조를 사용하여 가장 작은 가중치의 간선을 선택하여 속도를 개선

class Graph {
  constructor() {
    this.adjacencyList = new Map();
  }

  addVertex(vertex) {
    this.adjacencyList.set(vertex, new Map());
  }

  addEdge(v1, v2, weight) {
    this.adjacencyList.get(v1).set(v2, weight);
    this.adjacencyList.get(v2).set(v1, weight);
  }

  prim(startVertex) {
    const minimumSpanningTree = new Map();
    const visited = new Set();
    const heap = new Heap();

    // 시작 정점을 방문 처리
    visited.add(startVertex);

    // 시작 정점과 연결된 간선들을 힙에 삽입
    const edges = this.adjacencyList.get(startVertex);
    for (let [vertex, weight] of edges.entries()) {
      heap.insert({ vertex, weight });
    }

    while (!heap.isEmpty()) {
      const { vertex, weight } = heap.deleteMin();

      // 이미 방문한 정점이면 건너뛰기
      if (visited.has(vertex)) {
        continue;
      }

      // 정점을 방문 처리하고, 최소 비용 간선을 minimumSpanningTree에 추가
      visited.add(vertex);
      minimumSpanningTree.set(vertex, weight);

      // 현재 정점과 연결된 간선들을 힙에 삽입
      const edges = this.adjacencyList.get(vertex);
      for (let [v, w] of edges.entries()) {
        if (!visited.has(v)) {
          heap.insert({ vertex: v, weight: w });
        }
      }
    }

    return minimumSpanningTree;
  }
}

// 힙(Heap) 구현
class Heap {
  constructor() {
    this.heap = [];
  }

  insert(element) {
    this.heap.push(element);
    this.heapifyUp(this.heap.length - 1);
  }

  deleteMin() {
    const min = this.heap[0];
    const last = this.heap.pop();

    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.heapifyDown(0);
    }

    return min;
  }

  heapifyUp(index) {
    const parentIndex = Math.floor((index - 1) / 2);

    if (parentIndex >= 0 && this.heap[parentIndex].weight > this.heap[index].weight) {
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      this.heapifyUp(parentIndex);
    }
  }

  heapifyDown(index) {
    const leftChildIndex = 2 * index + 1;
    const rightChildIndex = 2 * index + 2;
    let smallestIndex = index;

    if (leftChildIndex < this.heap.length && this.heap[leftChildIndex].weight < this.heap[smallestIndex].weight) {
      smallestIndex = leftChildIndex;
    }

    if (rightChildIndex < this.heap.length && this.heap[rightChildIndex].weight < this.heap[smallestIndex].weight) {
      smallestIndex = rightChildIndex;
    }

    if (smallestIndex !== index) {
      [this.heap[index], this.heap[smallestIndex]] = [this.heap[smallestIndex], this.heap[index]];
      this.heapifyDown(smallestIndex);
    }
  }

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

// 그래프 생성
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");

graph.addEdge("A", "B", 4);
graph.addEdge("A", "C", 2);
graph.addEdge("B", "D", 5);
graph.addEdge("C", "D", 1);
graph.addEdge("C", "E", 3);
graph.addEdge("D", "E", 7);

// 테스트
const minimumSpanningTree = graph.prim("A");
console.log(minimumSpanningTree);

 

 

최단 경로

- 다익스트라 알고리즘(최단경로) : O((V + E) log V),

한점에서 다른 점들까지의 최소 거리

시작 노드에서 다른 노드까지의 거리를 찾고
최단 거리 노드를 방문하며 시작 노드로부터의 경로를 최소화.
모든 노드를 방문할때까지 반복.

 

function Graph() {
  this.adjacencyList = {};
}

Graph.prototype.addVertex = function (vertex) {
  this.adjacencyList[vertex] = {};
};

Graph.prototype.addEdge = function (v1, v2, weight) {
  this.adjacencyList[v1][v2] = weight;
  this.adjacencyList[v2][v1] = weight;
};

Graph.prototype.dijkstra = function (startVertex) {
  var distances = {};
  var visited = {};
  var queue = new PriorityQueue();

  // 모든 정점까지의 거리를 Infinity로 초기화
  for (var vertex in this.adjacencyList) {
    distances[vertex] = Infinity;
  }

  distances[startVertex] = 0;
  queue.enqueue(startVertex, 0);

  while (!queue.isEmpty()) {
    var currentVertex = queue.dequeue().element;

    if (visited[currentVertex]) {
      continue;
    }

    visited[currentVertex] = true;

    var neighbors = this.adjacencyList[currentVertex];
    for (var neighbor in neighbors) {
      var weight = neighbors[neighbor];
      var distance = distances[currentVertex] + weight;
      if (distance < distances[neighbor]) {
        distances[neighbor] = distance;
        queue.enqueue(neighbor, distance);
      }
    }
  }

  return distances;
};

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

PriorityQueue.prototype.enqueue = function (element, priority) {
  this.queue.push({ element: element, priority: priority });
  this.sort();
};

PriorityQueue.prototype.dequeue = function () {
  return this.queue.shift();
};

PriorityQueue.prototype.sort = function () {
  this.queue.sort(function (a, b) {
    return a.priority - b.priority;
  });
};

PriorityQueue.prototype.isEmpty = function () {
  return this.queue.length === 0;
};

// 테스트
var graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");

graph.addEdge("A", "B", 4);
graph.addEdge("A", "C", 2);
graph.addEdge("B", "D", 5);
graph.addEdge("C", "D", 1);
graph.addEdge("C", "E", 3);
graph.addEdge("D", "E", 7);

console.log(graph.dijkstra("A"));

 

 

이진탐색 

-  O(log n) : 정렬 되어 있을 경우 빠르게 탐색할수 있음.

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid; // 타겟을 찾았을 때 인덱스 반환
    } else if (arr[mid] < target) {
      left = mid + 1; // 중간값보다 큰 범위를 탐색하기 위해 왼쪽 범위를 업데이트
    } else {
      right = mid - 1; // 중간값보다 작은 범위를 탐색하기 위해 오른쪽 범위를 업데이트
    }
  }

  return -1; // 타겟을 찾지 못한 경우 -1 반환
}

// 테스트용 배열
const arr = [11, 22, 34, 45, 56, 67, 78, 89, 90];
const target = 45;
console.log("배열:", arr);
console.log(`타겟 ${target}의 인덱스:`, binarySearch(arr, target));

 

 

BFS/DFS

 v : 정점, e : 간선
  - 너비우선탐색(BFS) : O(v+e), queue 사용, 같은 레벨 먼저 탐색, 모든 경우 체크하며 감.

class Graph {
  constructor() {
    this.adjacencyList = new Map();
  }

  addVertex(vertex) {
    this.adjacencyList.set(vertex, []);
  }

  addEdge(v1, v2) {
    this.adjacencyList.get(v1).push(v2);
    this.adjacencyList.get(v2).push(v1);
  }

  bfs(startVertex) {
    const visited = new Set();
    const queue = [];

    visited.add(startVertex);
    queue.push(startVertex);

    while (queue.length > 0) {
      const currentVertex = queue.shift();
      console.log(currentVertex);

      const neighbors = this.adjacencyList.get(currentVertex);
      for (let neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
  }
}

// 테스트
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");

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

graph.bfs("A");

 

 

- 깊이우선탐색(DFS) : O(v+e), stack 사용, 자식 노드 먼저 탐색, 끝까지 갔다옴.   

class Graph {
  constructor() {
    this.adjacencyList = new Map();
  }

  addVertex(vertex) {
    this.adjacencyList.set(vertex, []);
  }

  addEdge(v1, v2) {
    this.adjacencyList.get(v1).push(v2);
    this.adjacencyList.get(v2).push(v1);
  }

  dfsRecursive(startVertex) {
    const visited = new Set();

    this.dfsRecursiveHelper(startVertex, visited);
  }

  dfsRecursiveHelper(vertex, visited) {
    visited.add(vertex);
    console.log(vertex);

    const neighbors = this.adjacencyList.get(vertex);
    for (let neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        this.dfsRecursiveHelper(neighbor, visited);
      }
    }
  }

  dfsIterative(startVertex) {
    const visited = new Set();
    const stack = [];

    stack.push(startVertex);

    while (stack.length > 0) {
      const currentVertex = stack.pop();

      if (!visited.has(currentVertex)) {
        visited.add(currentVertex);
        console.log(currentVertex);

        const neighbors = this.adjacencyList.get(currentVertex);
        for (let neighbor of neighbors) {
          stack.push(neighbor);
        }
      }
    }
  }
}

// 테스트
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");

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

graph.dfsRecursive("A");
// 또는
// graph.dfsIterative("A");

 

 

정렬

- 삽입정렬 : O(n^2)

function insertionSort(arr) {
  const length = arr.length;
  
  for (let i = 1; i < length; i++) {
    const current = arr[i];
    let j = i - 1;
    
    // 현재 요소를 이미 정렬된 부분의 적절한 위치에 삽입합니다.
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    
    arr[j + 1] = current;
  }
  
  return arr;
}

// 테스트용 배열
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log("정렬 전:", arr);
console.log("정렬 후:", insertionSort(arr));

 

 - 병합정렬 : O(n log n)

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) {
  let result = [];
  let i = 0;
  let j = 0;
  
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }
  
  while (i < left.length) {
    result.push(left[i]);
    i++;
  }
  
  while (j < right.length) {
    result.push(right[j]);
    j++;
  }
  
  return result;
}

// 테스트용 배열
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log("정렬 전:", arr);
console.log("정렬 후:", mergeSort(arr));