[알고리즘] 알고리즘 개념 정리

그리디

현재 상황에서 지금 당장 좋은 것만 고르는 방법,

순간 가장 좋아보이는 것을 선택하며, 현재 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

 

구현

머릿속에 있는 알고리즘을 소스코드로 구현하는 과정.

모든 경우의 수를 주저 없이 다 계산 하거나, 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 등의 유형있다.

 

DFS

깊이 우선 탐색으로 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘. 스택을 사용한다.

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "E"],
  D: ["B", "F"],
  E: ["C","G"],
  F: ["D","H","I"],
  G: ["E","J","K"],
  H: ["F","L"],
  I: ["F", "M"],
  J: ["G","N"],
  K: ["G","O"],
  L: ["H"],
  M: ["I","P"],
  N: ["J"],
  O: ["K"],
  P: ["M"]
};
const dfs = (graph, start) => {
    const checked = [];    // 탐색 완료 데이터
    const willCheck = [];  // 탐색 예정 데이터
    
    willCheck.push(start);
    
    while(willCheck.length!==0){
      const node = willCheck.pop();  // 스택(Last In First Out)
      if(!checked.includes(node)){
            checked.push(node);
         //reverse() 제거 시 그림의 4,3,2,1 순서로 탐색     
           willCheck.push(...graph[node].reverse());  
        
      }
   }
    return checked;
}
console.log(dfs(graph, "A"));
// ['A', 'B', 'D', 'F', 'H', 'L', 'I', 'M', 'P', 'C', 'E', 'G', 'J', 'N', 'K', 'O']

BFS

너비 우선 탐색. 가까운 노드부터 탐색하는 알고리즘. 큐를 사용한다는 것이 특징

일반적인 경우 DFS보다는 BFS 구현이 조금 더 빠르게 동작함.

 

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "G", "H", "I"],
  D: ["B", "E", "F"],
  E: ["D"],
  F: ["D"],
  G: ["C"],
  H: ["C"],
  I: ["C", "J"],
  J: ["I"]
};

const BFS = (graph, startNode) => {
  const visited = []; // 탐색을 마친 노드들
  let needVisit = []; // 탐색해야할 노드들

  needVisit.push(startNode); // 노드 탐색 시작

  while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
    const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
    if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
      visited.push(node); 
      needVisit = [...needVisit, ...graph[node]];
    }
  }
  return visited;
};

console.log(BFS(graph, "A"));
// ["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]

정렬

데이터를 특정한 기준에 따라 순서대로 나열한 것

 

선택 정렬

가장 작은 것을 선택하는 정렬

가장 작은 데이터를 선택해 맨 앞에있는 데이터와 바꾸고, 그 다음으로 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복함.

 

삽입 정렬

특정한 데이터를 적절한 위치에 삽입하는 정렬

특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞 까지의 데이터는 이미 정렬되어있다고 가정함.

정렬되어있는 데이터 리스트에서 적절한 위치를 찾은 후 그 위치에 삽입

 

퀵정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 정렬.

기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작

큰 수와 작은 수를 교환할 때 필요한 기준으로 pivot을 사용. 퀵정렬 수행 전에는 pivot을 어떻게 설정할 것인지 명시

 

계수 정렬

일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담음.

먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있게 하나의 리스트를 생성함. 그 다음 데이터를 하나씩 확인하며 데이터 값과 동일한 인덱스의 데이터를 1씩 증가시킴

 

탐색

데이터를 찾아내는 것.

 

순차 탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

데이터 개수가 N일때 최대 N번의 비교 연산이 필요하므로 최악의 경우 시간 복잡도는 O(N)임

 

이진탐색

정렬된 데이터의 탐색 범위를 절반씩 좁혀가며 데이터를 탐색함.

 

시작과 끝 그리고 중간 지점의 변수를 생성하고 사용. 찾으려는 데이터와 중간 위치의 데이터를 반복적으로 비교하여 원하는 데이터를 찾음.

 

한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간복잡도는 O(logN)임

 

DP

동적 계획법. 메모리 공간을 약간 더 사용해 연산 속도를 비약적으로 증가시킴.

 

Top-Down 방식

하향식. 재귀함수를 이용함. 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식

메모이제이션을 사용해 성능 개선이 가능함.

 

Bottom-Up 방식

상향식. 작은 문제부터 하나씩 답을 도출함