2021_04_21

TIL - DataStructure, Algorithm 복습하기

1. DataStructure, Algorithm 복습하기

[Queue 용어]

• enQueue: 큐에 요소를 삽입하는 동작이다.
• deQueue: 큐에서 요소를 삭제하는 동작이다.
• front: 큐의 가장 첫 요소를 가리킨다.
• rear: 큐의 가장 마지막 요소를 가리킨다.

큐는 삽입과 삭제가 한쪽에서만 이루어지는 자료구조이다.

[배열 용어]

• Array.prototype.shift(): 배열에서 첫 번째 요소를 제거하고 제거된 요소를 반환한다.
• Array.prototype.unshift(): 새로운 요소를 배열의 맨 앞쪽에 추가하고, 새로운 길이를 반환한다.

[인접 행렬 생성하기 - matrix 생성하기]

let matrix = [];
  let max = 0;
  //배열에 저장되어있는 정점을 순회하면서 정점의 최댓값을 구한다.
  for(let i = 0; i < edges.length; i++) { 
    if(edges[i][0] > max) {
      max = edges[i][0];
    }
    if(edges[i][1] > max) {
      max = edges[i][1];
    }
  }
  for(let i = 0; i <= max; i++) { //matrix의 길이는 max + 1이다. (세로)
    matrix.push(new Array(max + 1).fill(0)); //matrix 한 줄을 만든다.(가로)
  }

[Binary Search]

while(min <= max) {
    //수행범위를 1/2씩 줄여가면서 수행시간을 줄인다. (Binary Search)
    mid = Math.floor((max + min) / 2); 
    if(menuBS(mid)) { //원하는 조건에 따라서
      max = mid - 1; //최댓값을 점점 줄인다.
    }
    else {
      min = mid +1; //최솟값을 점점 늘린다.
    }
  }