주벨로퍼의 개발 공부

1.  프로세스란?

  프로그램이란 어떤 작업을 위해 실행할 수 있는 파일을 말한다.
  이러한 프로그램이 메모리에 적재되고 CPU 에 의해 실행중인 상태를 프로세스라고 한다.

  기본적으로 프로세스는 최소 1개의 스레드를 가진다.
  프로세스는 독립된 메모리 영역(Code, Data, Stack, Heap)을 할당 받는다.
  각 프로세스는 별도의 주소 공간에서 실행되므로, 다른 프로세스의 주소 공간(변수, 자료구조)에 접근할 수 없다.
  프로세스간의 데이터 통신을 위해서는 IPC(Inter Process Communication)이 필요하다.

2.  스레드란?

  프로세스 내에서 실행되는 흐름의 단위이다.
  일반적으로 한 프로그램은 하나의 스레드를 가지고, 둘 이상의 스레드를 동시에 실행한다면 이를 멀티스레드라 한다.
  스레드는 프로세스 내에서 Stack만 따로 할당 받고, Code, Data, Heap 영역은 공유한다.

3. Memory Map

  프로세스는 운영체제로부터 CPU 시간, 주소공간, 독립된 메모리 영역(Code, Data, Stack, Heap)을 할당 받는다.

  3 - 1) Code 영역
    실행할 프로그램의 코드가 저장되는 영역이다.
    CPU는 이 영역에 저장된 명령어를 하나씩 수행한다.
    프로그램이 끝날때까지 메모리 영역에 유지된다.

  3 - 2) Data 영역
    전역변수와 정적변수가 저장되는 영역이다.
    프로그램 시작때 할당되고 종료될때 해제된다.

  3 - 3) Stack 영역
    프로그램에 의해 사용되는 임시 데이터 영역이다.
    함수 호출시 지역변수, 매개변수를 저장한다.

  3 - 4) Heap 영역
    프로그래머에 의해 동적으로 할당되는 영역이다.
    메모리를 동적으로 할당할 때 사용되는 영역이다.

4. Multi Process

  여러 개의 프로세스를 통해 하나의 작업을 병렬적으로 처리하는 방식이다.
  즉 같은 프로그램을 동시에 처리하기위한 방식이다.
  각 프로세스 간 메모리 영역의 구분이 필요하거나 독립된 주소 공간을 가져야 할 때 사용한다.

  4 - 1) 장점
    각 메모리 영역이 독립적이기 때문에 안정성이 높다.
    여러 프로세스가 실행중이기 때문에 하나의 프로세스에 문제가 생겨도 문제가 확산되지 않는다.

  4 - 2) 단점
    멀티 스레드 방식보다 많은 메모리 공간과 CPU 시간을 차지한다.
    Context Switching 오버헤드가 발생할 수 있다.

    **CPU는 여러 프로세스를 아주 짧은 시간 간격으로 돌아가면서 작업을 처리하는데 이 과정을 Context-Switching이라 한다.

5. Multi Thread

  하나의 프로세스 내에서 여러 개의 스레드를 생성해 여러 CPU 코어를 사용하기위한 방식이다.

  5 - 1) 장점
    멀티프로세스 방식보다 적은 메모리 공간을 차지한다.
    Context Switching 이 빠르다.
    시스템 자원 소모가 감소하여 자원의 효율성이 증가한다.
    스레드간의 통신이 프로세스간의 통신보다 비용이 적기 때문에 자원 소모가 감소한다.

  5 - 2) 단점
    하나의 스레드에 문제가 생기면 전체 프로세스에 영향을 끼친다.
    자원을 공유하기때문에 동기화를 각별히 신경써야한다.
    개별로 스레드가 유기적으로 실행되기때문에 디버깅이 어렵다.

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;
}