본문 바로가기
  • 커뮤니티
  • 블로그
  • 북마크
Front-end/Javascript

[Javascript]자바스크립트 알고리즘 종류와 예시 몇개

by 빽짱구 2023. 6. 7.

요새 개발자를 채용할 때 알고리즘 테스트를 하는 기업이 늘고 있습니다.

알고리즘 테스트를 하는 이유는 '문제해결' 능력을 보려고 하는 것입니다.

 

그렇다면 알고리즘이란? 무엇인가?

 

알고리즘이란?

컴퓨터가 따라 할 수 있도록 문제를 해결하는 절차나 방법을 자세히 설명하는 과정이다

 

사전적으로는 컴퓨터가 문제를 해결할 수 있도록 하는 절차나 방법이라고 설명하고 있습니다.

 

 

산에 정상을 찍는 게 목표라고 생각했을 때

정상을 가기 위해서는 빨리 가는 길, 돌아가는 길, 그 밖에 여러 갈래의 길이 있을 수 있습니다.

 

여기에서 산을 쉽게 빨리 가는 방법을 찾는다면 그게 빠른 길로 가는 알고리즘이라고 이해하시면 될 거 같습니다.

여러 알고리즘이 있지만, 만약에 본인이 더 좋은 알고리즘을 찾는다면 그 찾은 사람의 알고리즘이 될 수 도 있겠네요. 

 

 

반응형

 

알고리즘 종류와 예시

이진 탐색(Binary Search):

  • 정렬된 배열에서 특정 요소를 찾는 알고리즘입니다.
  • 배열의 중간 요소와 찾고자 하는 값 비교 후 탐색 범위를 절반으로 줄여가며 반복합니다.
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    let 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; // 찾고자 하는 값이 배열에 없을 경우
}

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(binarySearch(array, 6)); // 출력: 5 (요소 6의 인덱스)

 

퀵 정렬(Quick Sort):

  • 분할 정복(Divide and Conquer) 기법을 사용하여 배열을 정렬하는 알고리즘입니다.
  • 배열을 피벗(pivot)을 기준으로 두 개의 부분 배열로 분할하고, 재귀적으로 각 부분 배열을 정렬합니다.
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  
  const pivot = arr[0];
  const left = [];
  const right = [];
  
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  
  return [...quickSort(left), pivot, ...quickSort(right)];
}

const array = [5, 2, 9, 1, 8, 6];
console.log(quickSort(array)); // 출력: [1, 2, 5, 6, 8, 9]

 

깊이 우선 탐색(DFS, Depth-First Search):

  • 그래프 탐색 알고리즘 중 하나로, 한 정점에서 시작하여 해당 정점과 인접한 정점을 재귀적으로 탐색합니다.
  • 스택(Stack) 또는 재귀 함수를 사용하여 구현할 수 있습니다.
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);
  }
  
  dfsRecursive(startVertex) {
    const visited = {};
    const result = [];
    const adjacencyList = this.adjacencyList;
    
    function dfs(vertex) {
      if (!vertex) {
        return null;
      }
      
      visited[vertex] = true;
      result.push(vertex);
      
      adjacencyList[vertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          return dfs(neighbor);
        }
      });
    }
    
    dfs(startVertex);
    return result;
  }
}

const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addEdge('A', 'B');
graph.addEdge('B', 'C');
graph.addEdge('C', 'D');

console.log(graph.dfsRecursive('A')); // 출력: ['A', 'B', 'C', 'D']

 

너비 우선 탐색(BFS, Breadth-First Search):

  • 그래프 탐색 알고리즘으로, 한 정점에서 시작하여 해당 정점과 인접한 모든 정점을 탐색한 후, 다음 단계의 인접한 정점들을 탐색합니다.
  • 큐(Queue)를 사용하여 구현할 수 있습니다.
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);
  }
  
  bfs(startVertex) {
    const visited = {};
    const result = [];
    const queue = [startVertex];
    
    visited[startVertex] = true;
    
    while (queue.length > 0) {
      const currentVertex = queue.shift();
      result.push(currentVertex);
      
      this.adjacencyList[currentVertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.push(neighbor);
        }
      });
    }
    
    return result;
  }
}

const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addEdge('A', 'B');
graph.addEdge('B', 'C');
graph.addEdge('C', 'D');

console.log(graph.bfs('A')); // 출력: ['A', 'B', 'C', 'D']

 

선택 정렬(Selection Sort):

  • 배열에서 최솟값을 선택하여 정렬되지 않은 부분 배열의 첫 번째 요소와 교환하는 정렬 알고리즘입니다.
  • 정렬되지 않은 부분 배열을 반복하면서 가장 작은 요소를 선택하고, 해당 요소를 정렬된 부분 배열의 마지막 요소와 교환합니다.
function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;
    
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  
  return arr;
}

const array = [5, 2, 9, 1, 8, 6];
console.log(selectionSort(array)); // 출력: [1, 2, 5, 6, 8, 9]

 

최단 경로 탐색(Dijkstra's Algorithm):

  • 가중치 그래프에서 두 정점 사이의 최단 경로를 찾는 알고리즘입니다.
  • 시작 정점에서부터 다른 모든 정점까지의 최단 거리를 계산합니다.
  • 우선순위 큐(Priority Queue)를 사용하여 구현할 수 있습니다.
class Graph {
  constructor() {
    this.vertices = [];
    this.edges = {};
  }
  
  addVertex(vertex) {
    this.vertices.push(vertex);
    this.edges[vertex] = {};
  }
  
  addEdge(vertex1, vertex2, weight) {
    this.edges[vertex1][vertex2] = weight;
    this.edges[vertex2][vertex1] = weight;
  }
  
  dijkstra(startVertex) {
    const distances = {};
    const visited = {};
    const previous = {};
    const queue = new PriorityQueue();
    
    this.vertices.forEach(vertex => {
      distances[vertex] = Infinity;
      previous[vertex] = null;
    });
    
    distances[startVertex] = 0;
    queue.enqueue(startVertex, 0);
    
    while (!queue.isEmpty()) {
      const currentVertex = queue.dequeue().element;
      visited[currentVertex] = true;
      
      for (let neighbor in this.edges[currentVertex]) {
        const weight = this.edges[currentVertex][neighbor];
        const totalDistance = distances[currentVertex] + weight;
        
        if (totalDistance < distances[neighbor]) {
          distances[neighbor] = totalDistance;
          previous[neighbor] = currentVertex;
          
          if (!visited[neighbor]) {
            queue.enqueue(neighbor, totalDistance);
          }
        }
      }
    }
    
    return {
      distances,
      previous
    };
  }
}

class PriorityQueue {
  constructor() {
    this.items = [];
  }
  
  enqueue(element, priority) {
    const queueElement = {
      element,
      priority
    };
    
    let added = false;
    
    for (let i = 0; i < this.items.length; i++) {
      if (queueElement.priority < this.items[i].priority) {
        this.items.splice(i, 0, queueElement);
        added = true;
        break;
      }
    }
    
    if (!added) {
      this.items.push(queueElement);
    }
  }
  
  dequeue() {
    return this.items.shift();
  }
  
  isEmpty() {
    return this.items.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', 'E', 3);
graph.addEdge('C', 'D', 2);
graph.addEdge('C', 'E', 1);
graph.addEdge('D', 'E', 3);

console.log(graph.dijkstra('A')); // 출력: { distances: { A: 0, B: 4, C: 2, D: 4, E: 3 }, previous: { A: null, B: 'A', C: 'A', D: 'C', E: 'C' } }

 

요즘에는 큰 기업에서 채용할 때 알고리즘 테스트를 하기 때문에 이해를 하기보단 수능 예상 문제집처럼 외우고 가는 경우도 많다고 합니다. 그래서 신입이 경력자 보다 알고리즘을 더 잘 알 수도 있지만, 그렇다고 알고리즘을 모르는 경력자들이 업무 대처 능력과 개발 능력이 떨어진다고 생각하진 않습니다.

이미 경력자들은 본인만의 알고리즘을 가지고 있을 수 있으니깐요. 그리고 알고리즘과 연봉이 정비례하진 않습니다.

 

물론 다양한 알고리즘을 아는 것이 이점이 많고, 기본기와 장기적으로 봤을 때는 유리하다고는 생각합니다.

외운다기보다 이해를 하는게 포인트라고 봅니다.

 

 

아래는 코딩 테스트를 할 수 있는 사이트입니다.

난이도 별로 문제가 주어지는데 참 어렵네요 ㅎㅎ

 

 

https://school.programmers.co.kr/learn/challenges?order=recent&page=1&languages=javascript 

 

코딩테스트 연습 | 프로그래머스 스쿨

개발자 취업의 필수 관문 코딩테스트를 철저하게 연습하고 대비할 수 있는 문제를 총망라! 프로그래머스에서 선발한 문제로 유형을 파악하고 실력을 업그레이드해 보세요!

school.programmers.co.kr

 

알고리즘은 여러 개발 언어에서 사용되고 비슷하다고 하니, 참고하시면 될듯합니다.

이 글이 도움 되셨다면 하트를 눌러주세요.

관련글

티스토리툴바