[Javascript] 알고리즘

KoEunseo·2022년 9월 2일
0

algorithm

목록 보기
1/8

01.BIG O

성능을 평가하는 방법. 문제에 대한 접근방식이 여러가지 있을 수 있다. 이 접근방식들의 성능을 평가할 수 있는 방법이다.

좋은 코드란?
[√] 속도가 빠른 코드
[ ] 메모리를 더 적게 사용하는 코드
[ ] 읽기 좋은 코드

단순히 함수가 실행되는 시간을 측정하는 것은 의미가 없다. 기기의 사양에 따라 연산속도에 차이가 있을수도 있고...
컴퓨터가 함수를 실행하고 리턴값을 내기까지 수행되는 '연산 개수'를 세는 방법이 있다.

함수에 인자로 n이 들어갈 때, 0부터 n까지의 합을 구하고 싶다. 이때

example 1: O(1)

//연산의 개수가 상수인 경우
function add(n){ return n * (n + 1) / 2 }

와

example 2: O(n)

function addLoop(n){
  result = 0;
  for(let i = 0; i <= n; i++) {
    result = result + i
  }
  return result;
}

하는 것은 같은 결과를 리턴한다. 그러나 결과를 도출하기까지 필요한 연산의 갯수는 엄청난 차이가 있다. 반복문이 연산에 들어가는 순간 일단 n의 크기에 비례해서 연산개수가 우상향한다.

빅오는 입력값의 크기와 실행시간의 관계에 대한 것이다.

상수나 연산은 중요하지 않음.

  • 산수는 상수이다.
  • 변수를 할당하는 것도 상수
  • 키나 인덱스에 접근하는것도 상수

O(2n + 10)은 => O(n),
O(500)은 => O(1)
O(12n^2 + 5n) => O(n^2)

Math.max(n, 10) 가장 큰 숫자 반환.

시간복잡도 : 시간
공간복잡도 : 공간차지

  • 원시값들은 상수공간 차지
  • String은 char크기만큼 O(n) 공간 차지
  • reference타입(배열, 객체) O(n)

07. 재귀

종료 조건이 없는것, 값을 반환하는 걸 잊는것(리턴하는것), 잘못된 값을 반환하는것(처음 들어온 인자를 다음에도 가공하지 않고 그대로 넘겨준다던가) 은 스택오버플로를 발생시킨다.

helper method recursion

재귀함수 내에 변수가 있다면 그 함수가 실행될 때마다 변수는 초기화된다. 그렇기때문에 1. 재귀함수 바깥에 변수를 두거나 2. 재귀함수 내에 변수를 뒀다면 그 안에 헬퍼함수를 만들어 재귀하게 한다.

function collectOddVal(arr){
  let result = []
  function helper(helperInput){
    if(helperInput.length === 0) {
      return;
    }
    if(helperInput[0] % 2 !== 0){
      reult.push(helperInput[0])
    }
    helper(helperInput.slice(1)) //현재 첫번째에 있는 값을 잘라냄
  }
  helper(arr)
  return result;
}

pure recursion

function collectOddVal(arr){
  let newArr = [];
  if(arr.length === 0) { return newArr; }
  if(arr[0] % 2 !== 0) {newArr.push(arr[0])}
  
  newArr = newArr.concat(collectOddVal(arr.slice(1)))
  //1. [1].concat(collectOddVal([2,3,4,5])) <- [1] + [3, 5]
    //2. [].concat(collectOddValues([3,4,5]))
      //3.[3].concat(collectOddVal([4,5])) <- [3] + [5]
        //4. [].concat(collectOddVal([5]))
          //5. [5].concat(collectOddVal([])) <- [5] + []
  return newArr;
}

TIP

배열을 복사하는 slice, spread, concat같은 메서드를 사용하라. 배열을 변경할 필요가 없어진다.
문자열은 변경할수가 없다. slice, substr, substring 사용해 사본을 만들어라.
객체는 Object.assign이나 spread 연산자를 사용하라.

22.이진검색트리

Tree
Binary Tree : 최대 2개의 자식노드를 가진 트리
Binary Search Tree(BST)
부모노드의 왼쪽에는 작은수, 오른쪽에는 큰수가 온다. 이진트리 + 기준에따라
정렬된다.

class BinarySearchTree {
  constructor(){
    this.root = null;
  }
}

class Node {
  constructor(value){
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

var tree = new BinarySearchTree();
tree.root = new Node(10);
tree.root.right = new Node(15);
tree.root.left = new Node(7);
tree.root.left.right = new Node(9);

Insert Node

  1. 새로운 노드 만들기
  2. 루트에서 시작한다.
    1. 루트가 있는지 확인. 없다면 root가 새 node가 되면 된다.(트리가 비어있어서 처음으로 새로운 무언가를 삽입)
    2. 새 노드의 값이 ㄹ루트의 값보다 큰지 작은지 확인
    3. 더 크다면 노드에 오른쪽 값이 있는지 확인
      • 있다면 그 노드에 가서 이 과정 반복.
      • 없다면 그 노드에 오른쪽 값으로 추가
    4. 더 작다면 노드에 왼쪽값이 있는지 확인
      • 있다면 그 노드에 가서 이 과정 반복.
      • 없다면 그 노드에 왼쪽 값으로 추가
  3. 노드 전체를 출력한다.
class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }
}

//      10
//   5     13
// 2  7  11  16
var tree = new BinarySearchTree();
tree.insert(10)
tree.insert(5)
tree.insert(13)
tree.insert(11)
tree.insert(2)
tree.insert(16)
tree.insert(7)

Finding a node in a BST

  1. 루트에서 시작한다.
  2. 루트가 있는지 확인한다. 없다면 탐색을 끝낸다.
    1. 루트가 있다면 값이 노드와 같은지 살펴본다.
    2. 같다면 끝. 아니라면 값이 노드보다 큰지 작은지 비교한다.
    3. 값이 노드보다 크다면
      • 오른쪽에 노드가 있는지 확인한다.
        * 있다면 그 노드에서 위 과정을 반복한다.
        • 없다면 탐색 끝
    4. 값이 노드보다 작다면
      • 왼쪽에 노드가 있는지 확인한다.
        * 있다면 그 노드에서 위 과정을 반복한다.
        • 없다면 끝
find(value) {
  if(this.root === null) return false;
  var current = this.root,
      found = false;
  while(current && !found){ //current값이 null이 되면 루프가 멈춘다.
    if(value < current.value) {
      current = current.left;
    } else if(value > current.value) {
      current = current.right;
    } else {
      found = true; //루프를 멈춤
    }
  }
  if(!found) return undefined;
  return current;
}

23. 트리순회

BFS 너비우선탐색

  1. 두개의 변수를 만드는데, 하나는 큐를 만들어서 요소들을 추적하고 다른 하나는 데이터의 리스트를 만들어서 마지막에 출력한다.
  2. 큐에 루트를 넣는다.
  3. 큐에 아무것도 남지 않을때까지 루프를 돌린다.
    • 큐에서 디큐를 한다(shift). 배열의 맨 앞에서 제거하는 역할.
    • 그 노드를 리스트에 추가한다.
    • 그 노드에 왼쪽값이 있는지 확인해서 있다면 큐에 넣어주고
    • 그 노드에 오른쪽값이 있다면 큐에 넣어준다.
  4. 리스트를 출력한다.
BFS() {
  var data = [],
      queue = [];
  var node = this.root;
  queue.push(node)
  while(queue.length){ //0이 나오면 flase
    node = queue.shift() //큐의 맨앞에서 제거.FIFO
    data.push(node.value);
    if(node.left) queue.push(node.left);
    if(node.right) queue.push(node.right);
  }
  return data;
}

DFS 깊이우선탐색

preOrder

  1. 방문한 노드의 값을 저장할 변수를 만든다
  2. current라는 변수에 root를 저장한다.
  3. 헬퍼함수를 만든다.
    • 이 함수는 노드의 값을 변수에 넣어서 저장하는 역할을 한다.
    • 노드를 방문해 배열이나 리스트에 값을 추가한다
    • 노드가 left값을 가졌다면 재귀방식으로 헬퍼함수를 다시 호출한다.
    • 노드가 right값을 가졌다면 재귀방식으로 헬퍼함수를 다시 호출한다.
  4. 헬퍼함수를 current변수에 대해 호출한다.
  5. 배열이나 리스트를 리턴한다.
DFS() {
  var data = [];
  var current = this.root;
  function traverse(node) {
    data.push(node.value);
    if(node.left) traverse(node.left);
    if(node.right) traverse(node.right);
  }
  traverse(current);
  return data;
}

깊이보다 너비가 넓은 트리의 경우 깊이우선탐색이 더 적은 공간을 점유한다. 너비우선탐색을 하려면 옆으로 가면서 큐에 노드들을 저장해야하는데 많은 공간이 소요된다. 시간복잡도는 상관이 없다.

profile
KoEunseo
주니어 플러터 개발자의 고군분투기
다음 포스트

배열과 객체의 성능평가(with. bigO)

0개의 댓글