🖋️ 알고리즘 정리

• 정렬

  • 특징

    • 데이터를 특정 기준에 따라 순서대로 나열
    • 대표적인 정렬 알고리즘
      • 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬 등
    • JavaScript에서는 Array.prototype.sort() 메서드를 사용하여 쉽게 정렬

  • 적용 사례

    • 데이터를 순서대로 나열해야 할 때 사용
    • 예시
      • 데이터베이스의 결과 정렬, 날짜나 시간 정렬, 숫자나 문자열 정렬 등

  • 버블 정렬 CODE

function bubbleSort(arr) {
  let n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // swap
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

console.log(bubbleSort([5, 3, 8, 4, 2]));

• 완전 탐색

  • 특징

    • 가능한 모든 경우의 수를 탐색하여 문제를 해결
    • 가장 단순하고 확실한 해결 방법이지만, 경우의 수가 많을 때 비효율

  • 적용 사례

    • 예시
      • 소수 찾기, 순열과 조합 계산, 브루트 포스 암호 해독 등

  • 소수 찾기 CODE

function isPrime(num) {
  if (num <= 1) return false;
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) return false;
  }
  return true;
}

console.log(isPrime(5));  // true
console.log(isPrime(4));  // false

• 그리디

  • 특징

    • 매 순간 최적이라고 생각되는 선택을 하여 해결
    • 항상 최적의 결과를 보장하지는 않지만, 효율적이고 빠른 해결이 가능

  • 적용 사례

    • 예시
      • 거스름돈 문제, 최소 회의실 배정, 크루스칼 알고리즘 등

  • 거스름 돈 문제 CODE

function getChange(total) {
  const coins = [500, 100, 50, 10];
  let count = 0;
  for (let coin of coins) {
    count += Math.floor(total / coin);
    total %= coin;
  }
  return count;
}

console.log(getChange(1260));

• 동적계획법 (DP)

  • 특징

    • 복잡한 문제를 재귀적으로 분할하여, 하위 문제의 해결 결과를 저장하고 재활용
    • 중복 계산을 방지하여 효율성을 높임

  • 적용 사례

    • 예시
      • 피보나치 수열, 최장 증가 부분 수열, 배낭 문제 등

  • 거스름 돈 문제 CODE

function fibonacci(n) {
  let dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

console.log(fibonacci(10));

• 깊이 우선 탐색 (DFS)

  • 특징

    • 그래프의 노드를 깊이를 우선하여 탐색하는 알고리즘
    • 스택(Stack) 또는 재귀(Recursion)를 사용하여 구현
    • 모든 노드를 방문하고자 할 때 사용되며, 경로의 존재 여부, 사이클 감지 등에 유용
    • 탐색을 시작하는 노드에서 가능한 한 깊게 그래프를 탐색하며, 더 이상 탐색할 수 없을 때 이전 분기점으로 돌아가 다른 경로를 탐색

  • 적용 사례

    • 예시
      • 퍼즐 게임에서 모든 가능한 경우의 수 탐색
      • 특정 경로의 존재 여부 확인
      • 사이클 감지

  • CODE

    function dfs(graph, start) {
       let visited = new Set();
       let stack = [start];
    
       while (stack.length) {
        let node = stack.pop();
        if (!visited.has(node)) {
          visited.add(node);
          stack.push(...graph[node].filter(n => !visited.has(n)));
        }
       }
    
      return Array.from(visited);
    }
    
    let graph = {
     A: ['B', 'C'],
     B: ['A', 'D', 'E'],
     C: ['A', 'F'],
     D: ['B'],
     E: ['B'],
     F: ['C']
    };
    
    console.log(dfs(graph, 'A')); // ['A', 'C', 'F', 'B', 'E', 'D']

• 너비 우선 탐색 (BFS)

  • 특징

    • 그래프의 노드를 너비를 우선하여 탐색하는 알고리즘
    • 큐(Queue)를 사용하여 구현
    • 최단 경로 문제나 그래프의 레벨(Level)을 탐색할 때 주로 사용
    • 시작 노드에서 가까운 노드를 우선적으로 탐색하며, 차례대로 모든 이웃 노드들을 방문

  • 적용 사례

    • 예시
      • 최단 경로 찾기
      • 소셜 네트워크에서의 최단 연결 경로(케빈 베이컨 수)
      • 레벨 별 노드 탐색

  • CODE

    function bfs(graph, start) {
       let visited = new Set();
       let queue = [start];
    
       while (queue.length) {
         let node = queue.shift();
         if (!visited.has(node)) {
           visited.add(node);
           queue.push(...graph[node].filter(n => !visited.has(n)));
         }
       }
    
       return Array.from(visited);
    }
    
    let graph = {
     A: ['B', 'C'],
     B: ['A', 'D', 'E'],
     C: ['A', 'F'],
     D: ['B'],
     E: ['B'],
     F: ['C']
    };
    
    console.log(bfs(graph, 'A')); // ['A', 'B', 'C', 'D', 'E', 'F']