주벨로퍼의 개발 공부

1. 이분 검색이란?

  이진 검색은 정렬된 리스트에서 원하는 항목을 찾기에 효율적인 알고리즘이다.  
  이 검색법은 후보 범위가 한 항목으로 좁아질 때까지 찾고자 하는 항목을 포함하고 있는 리스트를 반으로 나누는 과정을 계속 반복한다.

2. 대표문제 1

function binarySearch(arr, target) {
  let answer = 0,
    lt = 0,
    rt = arr.length - 1;
  arr.sort((a, b) => a - b);
  while (lt <= rt) {
    let mid = Math.floor((lt + rt) / 2);
    if (arr[mid] === target) {
      answer = mid;
      break;
    } else if (arr[mid] < target) {
      lt = mid + 1;
    } else {
      rt = mid - 1;
    }
  }
  return answer + 1;
}

3.  대표문제 2

function getDvdNums(songs, dvdSize) {
  let cnt = 1,
    sum = 0;
  for (let i = 0; i < songs.length; i++) {
    if (sum + songs[i] > dvdSize) {
      cnt++;
      sum = songs[i];
    } else {
      sum += songs[i];
    }
  }
  return cnt;
}

function solution(songs, dvdNums) {
  let answer;
  let min = Math.max(...songs);
  let max = songs.reduce((acc, cur) => acc + cur);

  while (min <= max) {
    let mid = Math.floor((min + max) / 2);
    if (getDvdNums(songs, mid) <= dvdNums) {
      answer = mid;
      max = mid - 1;
    } else {
      min = mid + 1;
    }
  }
  return answer;
}

4. 대표문제 3

function helper(arr, dist) {
  let cnt = 1;
  let ep = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] - ep >= dist) {
      ep = arr[i];
      cnt++;
    }
  }
  return cnt;
}

function solution(arr, num) {
  arr.sort((a, b) => a - b);
  let lt = 1;
  let rt = arr[arr.length - 1];
  let mid;
  let answer;
  while (lt <= rt) {
    mid = Math.floor((lt + rt) / 2);
    if (helper(arr, mid) >= num) {
      answer = mid;
      lt = mid + 1;
    } else {
      rt = mid - 1;
    }
  }
  return answer;
}

1.  그리디 알고리즘이란?

  그리디 알고리즘은 욕심쟁이 알고리즘이라고도 불리는데 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법입니다. 
  이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘이다.
  그리디 알고리즘이 항상 최적해를 보장해주진 못하지만 몇몇 경우에 있어선 아주 효율적으로 최적해를 구할 수 있다.

1 - 1) 대표문제 1

function solution(meeting){
  let answer = 0;
  meeting.sort((a, b) => { 
    if (a[1] === b[1]) return a[0] - b[0];
    else return a[1] - b[1];
  })
  let et = 0;
  for (let x of meeting) {
    if (x[0] >= et){
      answer++;
      et=x[1];
    }
  }
  return answer;
}

1 - 2) 대표문제 2

function solution(arr) {
  let answer = Number.MIN_SAFE_INTEGER;
  let timeLine = [];
  for (let i = 0; i < arr.length; i++) {
    timeLine.push([arr[i][0], "s"]);
    timeLine.push([arr[i][1], "e"]);
  }
  timeLine.sort((a, b) => {
    if (a[0] === b[0]) return a[1].charCodeAt() - b[1].charCodeAt();
    return a[0] - b[0];
  });
  let cnt = 0;
  for (let x of timeLine) {
    if (x[1] === "s") cnt++;
    else cnt--;
    answer = Math.max(answer, cnt);
  }
  return answer;
}

1. Selection Sort

  선택 정렬은 첫 번째 인덱스에는 두 번째 자료부터 마지막 자료까지 중에 가장 최솟값을 놓고
  두 번째 자료에는 세 번째 자료부터 마지막 자료까지 중에 최솟값을 놓는 과정을 반복하여 정렬하는 알고리즘

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let min = Math.min(...arr.slice(i + 1));
    let minIdx = arr.indexOf(min);
    if (minIdx === i) continue;
    else [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
  }
  return arr;
}

2. Bubble Sort

  버블 정렬은 자기 자신 바로 옆에 자료와 크기 비교를 통해 한 쪽으로 최댓값 또는 최솟값을 결정하고 이것을 매번 반복하여
  정렬하는 알고리즘이다.

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

3. Insert Sort

  각 자료를 선형 탐색하면서 해당 자료와 해당 자료 이전까지 자료들의 크기를 비교하여 정렬하는 알고리즘이다.
  즉 두 번째 자료는 첫 번째 자료와 크기를 비교하여 정렬하고 세 번째 자료는 두 번째 자료와 크기를 비교하고 만약 세 번째 자료의 크기가 작다면 두 번째 자료와 자리를 바꾸고 또 두 번째 자료와 첫 번째 자료의 크기를 비교한다. 이러한 방법으로 마지막 자료까지 반복하는 것이 삽입 정렬이다.

function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j >= 0; j--) {
      if (arr[j] < arr[j - 1]) [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
      else break;
    }
  }
  return arr;
}

4. Quick Sort

  현존하는 가장 빠른 정렬 알고리즘 중에 하나이다. 퀵 정렬에서는 요소 하나를 기준 원소인 pivot으로 설정한다.
  그리고 기준 원소의 왼쪽에는 기준 원소보다 작은 값의 배열을 놓고 오른쪽에는 기준 원소보다 큰 값을 놓는다.
  그리고 왼쪽 배열과 오른쪽 배열 각각에 대해서 또 위의 과정을 반복하여 정렬하는 것이 퀵 정렬이다.

const quickSort = function (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]);
  }

  const lSorted = quickSort(left);
  const rSorted = quickSort(right);
  return [...lSorted, pivot, ...rSorted];
};

1.  스택이란?

  LIFO 구조로 마지막에 들어온 데이터가 가장 빨리 나가는 자료구조이다.
  탑 쌓기, 브라우저의 뒤로가기 기능 등을 생각하면 된다.

1 - 1) 스택 대표문제 1
  입력된 문자열에서 소괄호 ( ) 사이에 존재하는 모든 문자를 제거하고 남은 문자만 출력하는 프로그램을 작성하세요.
  입력 예제 : (A(BC)D)EF(G(H)(IJ)K)LM(N)
  출력 예제 : EFLM

function removeBraket(str) {
  let answer = [];
  for (let i = 0; i < str.length; i++) {
    if (str[i] === ")") {
      while (answer.pop() !== "(");
    } else {
      answer.push(str[i]);
    }
  }
  return answer.join("");
}

1 - 2) 스택 대표문제 2

입력 예제1 : ()(((()())(())()))(())
출력 예제2 : 17

입력 예제2 : (((()(()()))(())()))(()())
출력 예제2 : 24

function solution(s){
  let answer=0;
  let stack=[];
  for(let i=0; i<s.length; i++){
    if(s[i]==='(') stack.push('(');
    else{
      stack.pop(); 
      if(s[i-1]==='(') answer+=stack.length;
      else answer++;
      //stack.pop(); 이 위치에 하면 레이저까지 카운팅한다.
    }
  }                          
  return answer;
}

2. 큐란? 

  FIFO 구조로 먼저 들어온 데이터가 먼저 나가는 자료구조이다.
  가게에서 웨이팅을 할 때 줄을 선 순서대로 주문받는 경우를 생각하자.

2 - 1) 큐 대표문제 1

function solution(essentials, plans) {
  let queue = essentials.split("");
  for (let x of plans) {
    if (queue.includes(x)) {
    // 일단 x가 essentials에 있어야 함
      if (x !== queue.shift()) return "NO"; // 필수과목은 순서대로 있어야함!
    }
  }
  if (queue.length > 0) return "NO"; // 정상적인 플랜이었다면 queue의 최종 길이는 0, 반례 CB
  return "YES";
}

1. Hash Map 자료구조

  Key - Value 로 데이터를 저장하는 자료구조이다.
 

2. 대표문제 - 아나그램

  두 문자열에서 알파벳의 나열 순서는 다르지만 그 구성이 일치할 때 두 문자열은 아나그램이라고 한다.
  예를 들면 AbaAeCe 와 baeeACA 는 알파벳의 나열 순서는 다르지만 각각의 문자의 개수는 같으므로 아나그램이다.

  두 단어가 입력으로 주어지고 아나그램인지 아닌지를 판단하는 함수를 작성하시오.
 

function isAnagram(str1, str2) {
    let sH = new Map();
    for(let x of str1){
        if(sH.has(x)) sH.set(x, sH.get(x) + 1);
        else sH.set(x, 1);
    }
    for(let x of str2){
        if(!sH.has(x) || sH.get(x) === 0) return false;
        sH.set(x, sH.get(x) - 1);
    }
    return true;
}

1. 슬라이딩 윈도우 알고리즘이란?

  일정한 범위를 가지고 이동하면서 원하는 결과를 얻는 알고리즘!

2. 최대 매출 구하기 문제

  N일 동안의 매출기록에서 연속된 K일 동안의 최대 매출액이 얼마인지 구하는 문제

function solution(arr, k) {
	let answer, sum = 0;
    for(let i = 0; i < k; i++) sum += arr[i];
    answer = sum;
    for (let i = k; i < arr.length; i++) {
    	sum += (arr[i] - arr[i - k]);
        answer = Math.max(answer, sum);
    }                    
    return answer;
}