[DAY-5] JS 주요 문법(5)

😉 헷갈렸던 & 몰랐던 부분들만 정리하는 나만의 TIL
😯 모든 강의 내용은 적지 않아요!

오늘의 소감은?
코딩 테스트 연습을 조금 늦게 시작한 편이라 아직 백준 100문제도 다 못풀었다.
그래서 이진트리는 쳐다보지도 못할 구역이었다.. ^^...

삭제 메소드 짜고 기능 테스트하는데에만 오늘 시간 다썼다.
아직 이진트리에 대한 이해가 부족해서 더 공부해봐야겠다.

[+] 실습 - 가장 먼 노드

😂 왜 시간초과 나냐고 ..

가장 먼 노드를 딱 보면 생각나는 로직이 BFS였습니다.
인접 리스트로 풀었어야 시간 초과가 안났을까,,? 아직 JS로 코테는 무리라고 생각해요..

• 초기 답안

function popVal(arr) {
  const val = arr[0];

  for (let i = 0; i < arr.length - 1; i += 1) {
    arr[i] = arr[i + 1];
  }
  arr.splice(-1, 1);

  return val;
}

function bfs(s, arr, e) {
  const visit = new Array(e + 1).fill(false);
  const val = new Array(e + 1).fill(0);
  const queue = [s];
  visit[s] = true;

  while (queue.length) {
    const num = popVal(queue);
    const v = val[num] + 1;

    for (let node of arr) {
      if (node[0] === num && !visit[node[1]]) {
        queue.push(node[1]);
        visit[node[1]] = true;
        val[node[1]] = v;
      } else if ((node[1] === num) & !visit[node[0]]) {
        queue.push(node[0]);
        visit[node[0]] = true;
        val[node[0]] = v;
      }
    }
  }

  const maxVal = Math.max.apply(null, val);
  return val.filter((i) => i === maxVal).length;
}

function solution(n, edge) {
  return bfs(1, edge, n);
}

😣 파이썬으로 짜던 것 처럼 인접 리스트를 이용한 코드로 수정해봤습니다.

• 수정 답안

function popVal(arr) {
  const val = arr[0];

  for (let i = 0; i < arr.length - 1; i += 1) {
    arr[i] = arr[i + 1];
  }
  arr.splice(-1, 1);

  return val;
}

function bfs(s, graph, e) {
  const visit = new Array(e + 1).fill(false);
  const val = new Array(e + 1).fill(0);
  const queue = [s];
  visit[s] = true;

  while (queue.length) {
    const num = popVal(queue);
    const v = val[num] + 1;

    for (let n of graph[num]) {
      if (!visit[n]) {
        queue.push(n);
        visit[n] = true;
        val[n] = v;
      }
    }
  }

  const maxVal = Math.max.apply(null, val);

  return val.filter((i) => i === maxVal).length;
}

function solution(n, edge) {
  const graph = Array.from(Array(n + 1), () => []);

  for (const [a, b] of edge) {
    graph[a].push(b);
    graph[b].push(a);
  }

  return bfs(1, graph, n);
}

😮 성능이 이렇게나 차이가 난다니..
이제 확실히 JS로 코드 짜는게 감이 오기 시작하는 것 같습니다.

[1] 트리(Tree)

트리는 방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조를 가지고 있습니다.

[1-1] 트리 특징

• 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가집니다.
• 정점이 N개인 트리는 반드시 N-1개의 간선을 가집니다.
• 루트에서 특정 정점으로 가는 경로는 유일합니다.

[1-2] 이진 트리

이진 트리는 각 정점이 최대 2개의 자식을 가지는 트리를 의미합니다.

이진 트리, 완전 이진트리, 포화 이진트리 이 외에는 편향 트리가 있습니다.

특징

• 정점이 N개인 이진 트리는 최악의 경우 높이가 N이 될 수 있습니다.
• 정점이 N개인 포화 또는 완전 이진 트리 높이는 log N 입니다.
• 높이가 h인 포화 이진 트리는 2^h-1개의 정점을 가집니다.
• 일반적인 이진 트리를 사용하는 경우는 많지 않고, 다음 자료구조에 응용되는 경우가 많습니다.
  → 이진 탐색 트리, 힙, AVL 트리, 레드 블랙 트리

[1-3] 구현 방법

트리는 인접 행렬, 인접 리스트 두 가지 방식으로 구현할 수 있습니다.

• 배열로 구현

인덱스 * 2 는 왼쪽 정점, 인덱스 * 2 + 1은 오른쪽 정점이 됩니다.

부모 정점을 알고싶다면, 인덱스 // 2 (소숫점을 버린 상태)로 알 수 있습니다.

const tree = [
  undefined,
  9,
  3,
  8,
  2,
  5,
  undefined,
  7,
  undefined,
  undefined,
  undefined,
  4,
];

• 연결 리스트로 구현

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

class Tree {
	constructor() {
		this.root = node;
	}

	//... methods : queue를 선언해서 enqueue로 left, right 자식 노드들을 더해준다.
}

const tree = new Tree(new Node(10));
tree.root.left = new Node(5);
tree.root.right = new Node(9);
tree.root.left.left = new Node(3);
...

[2] 힙(Heap)

이진 트리 형태를 가지며,
우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제될 때 바로 정렬되는 특징이 있습니다.

힙은 ‘우선순위 큐’를 구현하기에 가장 적합한 요소입니다.

우선순위 큐
FIFO인 큐와 달리 우선 순위가 높은 요소가 먼저 나가는 큐

[2-1] 힙의 특징

• 우선순위가 높은 요소가 먼저 나가는 특징이 있습니다.
• 루트가 가장 큰 값이 되는 최대 힙(Max Heap)과 루트가 가장 작은 값이 되는 최소 힙(Min Heap)이 있습니다.
• JS에서는 직접 구현해서 사용해야 합니다. (라이브러리가 없습니다.)

[2-2] 힙 알고리즘

(1) 요소 추가

• 요소가 추가될 때는 트리의 가장 마지막 정점에 위치합니다.
• 추가 후 부모 정점보다 우선순위가 높으면 순서를 바꿉니다.
• 이 과정을 반복하면 결국 가장 우선순위가 높은 정점이 루트가 됩니다.

(2) 요소 제거

• 요소 제거는 루트 정점만 가능합니다.
• 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치합니다.
• 루트 정점의 두 자식 정점 중 더 우선순위가 높은 정점과 바꿉니다.
• 두 자식 정점이 우선순위가 더 낮을 때 까지 반복합니다,

완전 이진트리의 높이는 log N 이기 때문에, 힙의 요소 추가/제거 알고리즘은 O(log N)의 시간복잡도를 가집니다.

[2-3] 구현 방법

• MaxHeap

class MaxHeap {
  constructor() {
    this.heap = [null];
  }

  push(val) {
    this.heap.push(val);
    let curIdx = this.heap.length - 1;
    let parIdx = Math.floor(curIdx / 2);

    while (parIdx !== 0 && this.heap[parIdx] < val) {
      const tmp = this.heap[parIdx];
      this.heap[parIdx] = val;
      this.heap[curIdx] = tmp;

      curIdx = parIdx;
      parIdx = Math.floor(curIdx / 2);
    }
  }

  pop() {
    const returnVal = this.heap[1];
    this.heap[1] = this.heap.pop();

    let curIdx = 1;
    let leftIdx = 2;
    let rightIdx = 3;

    while (
      this.heap[curIdx] < this.heap[leftIdx] ||
      this.heap[curIdx] < this.heap[rightIdx]
    ) {
      if (this.heap[leftIdx] < this.heap[rightIdx]) {
        const tmp = this.heap[curIdx];
        this.heap[curIdx] = this.heap[rightIdx];
        this.heap[rightIdx] = tmp;
        curIdx = rightIdx;
      } else {
        const tmp = this.heap[curIdx];
        this.heap[curIdx] = this.heap[leftIdx];
        this.heap[leftIdx] = tmp;
        curIdx = leftIdx;
      }
      leftIdx = curIdx * 2;
      rightIdx = curIdx * 2 + 1;
    }

    return returnVal;
  }
}

const heap = new MaxHeap();
heap.push(45);
heap.push(30);
console.log(heap.heap);
heap.push(70);
console.log(heap.heap);
heap.push(43);
console.log(heap.heap);

const popArr = [];
popArr.push(heap.pop());
console.log(popArr);
console.log(heap.heap);

[+] 과제 - MinHeap

간단하게 MaxHeap의 > 조건을 <로 바꿔주면 되는 과제였습니다.
MaxHeap, MinHeap의 차이를 알고 원리를 이해하기 위해 내주신 과제같아요.

• MinHeap

class MinHeap {
  constructor() {
    this.heap = [null];
  }

  push(val) {
    this.heap.push(val);
    let curIdx = this.heap.length - 1;
    let parIdx = Math.floor(curIdx / 2);

    while (parIdx !== 0 && this.heap[parIdx] > val) {
      const tmp = this.heap[parIdx];
      this.heap[parIdx] = val;
      this.heap[curIdx] = tmp;

      curIdx = parIdx;
      parIdx = Math.floor(curIdx / 2);
    }
  }

  pop() {
    const returnVal = this.heap[1];
    this.heap[1] = this.heap.pop();

    let curIdx = 1;
    let leftIdx = 2;
    let rightIdx = 3;

    while (
      this.heap[curIdx] > this.heap[leftIdx] ||
      this.heap[curIdx] > this.heap[rightIdx]
    ) {
      if (this.heap[leftIdx] > this.heap[rightIdx]) {
        const tmp = this.heap[curIdx];
        this.heap[curIdx] = this.heap[rightIdx];
        this.heap[rightIdx] = tmp;
        curIdx = rightIdx;
      } else {
        const tmp = this.heap[curIdx];
        this.heap[curIdx] = this.heap[leftIdx];
        this.heap[leftIdx] = tmp;
        curIdx = leftIdx;
      }
      leftIdx = curIdx * 2;
      rightIdx = curIdx * 2 + 1;
    }

    return returnVal;
  }
}

const heap = new MinHeap();
heap.push(45);
heap.push(30);
console.log(heap.heap);
heap.push(70);
console.log(heap.heap);
heap.push(43);
console.log(heap.heap);

const popArr = [];
popArr.push(heap.pop());
console.log(popArr);
console.log(heap.heap);

제일 작은 값이 root에 배치되는 MinHeap가 잘 작동함을 알 수 있습니다.

[3] 트라이(Trie)

트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다.

[3-1] 트라이의 특징

• 검색어 자동완성, 사전 찾기 등에 응용될 수 있습니다.
• 문자열을 탐색할 때 단순하게 비교하는 것 보다 효율적입니다.
• L이 문자열의 길이일때 탐색, 삽입은 O(L)만큼 걸립니다.
• 각 정점이 자식에 대한 링크를 전부 가지고 있어야 하기 때문에 저장 공간을 더 많이 사용합니다.

[3-2] 트라이 구조

• 루트는 비어있습니다.
• 각 간선(링크)는 추가될 문자를 키로 가집니다
• 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가집니다.
• 해시 테이블과 연결 리스트를 이용하여 구현할 수 있습니다.

[3-3] 구현 방법

class Node {
  constructor(val = "") {
    this.val = val;
    this.children = new Map();
  }
}

class Trie {
  constructor() {
    this.root = new Node();
  }

  insert(str) {
    let curNode = this.root;

    for (const char of str) {
      if (!curNode.children.has(char)) {
        curNode.children.set(char, new Node(curNode.val + char));
      }

      curNode = curNode.children.get(char);
    }
  }

  has(str) {
    let curNode = this.root;

    for (const char of str) {
      if (!curNode.children.has(char)) {
        return false;
      }
      curNode = curNode.children.get(char);
    }

    return true;
  }
}

const trie = new Trie();
trie.insert("sky");
trie.insert("ski");
console.log(trie.has("sky")); // true
console.log(trie.has("ski")); // true
console.log(trie.has("skk")); // false

[4] 정렬(Sort)

(1) 비교식 정렬

다른 요소와 비교를 통해 정렬하는 방법

• 버블 정렬 : 서로 인접한 두 요소 검사하여 정렬 (O(n^2))
• 선택 정렬 : 선택한 요소와 가장 우선순위가 높은 요소를 교환하여 정렬 - O(n^2)
• 삽입 정렬 : 선택한 요소를 삽입할 수 있는 위치를 찾아 삽입하는 방식의 정렬 - O(n^2)

(2) 분산식 정렬

요소를 분산하여 정렬하는 방법

• 합병 정렬 : 분할 정복 알고리즘을 이용한 최선과 최악이 같은 안정적인 정렬 방법 - O(nlog n)
• 퀵 정렬 : 분할 정복 알고리즘을 이용한 매울 빠르지만 최악의 경우가 존재하는 불안정 정렬 -O(nlog n)

분할 정복
문제를 작은 2개의 문제로 분리하고, 더 이상 분리가 불가능할때 처리한 후 합치는 전략

[+] 실습 - 가장 큰 수

• 초기 답안

function solution(numbers) {
  let answer = numbers
    .map((n) => n + "")
    .sort((a, b) => b + a - (a + b))
    .join("");

  return answer;
}

😊 …?

곰곰히 생각하고 코드를 고쳐 보았습니다 😊…
다 0으로 이루어져 있는 엣지 케이스를 고려하지 않았더라고요..?

• 수정 답안

function solution(numbers) {
  let answer = numbers
    .map((n) => n + "")
    .sort((a, b) => b + a - (a + b))
    .join("");

  if (parseInt(answer) === 0) {
    return "0";
  }

  return answer;
}

[5] 이진 탐색(Binary Search)

정렬 되어있는 요소들을 반씩 제외하며 찾는 알고리즘입니다.

O(lon n)만큼의 시간복잡도가 걸립니다.

[5-1] 이진 탐색 특징

• 반드시 정렬이 되어있어야 사용할 수 있습니다.
• 배열 혹은 이진 트리를 이용하여 구현할 수 있습니다.
• O(log n) 시간복잡도인만큼 상당히 빠릅니다.
• 최악의 경우 한쪽으로 편향된 트리가 될 수 있습니다. 이럴 경우, 순차 탐색과 동일한 시간복잡도(O(n))를 가집니다.
  → 이를 해결하기 위해 AVL 트리, 레드-블랙 트리의 자료구조를 이용할 수 있습니다.

[+] 과제 - 이진 탐색 트리 요소 제거

진짜 이렇게 긴 메소드는 나도 처음 짜보는걸..? 😥
재귀를 이용해서 짰다가 탈출하지 못하는 이슈때문에
parentNode와,, minParent를 따로 선언해서 사용했습니다.

> 이로서 백종원 선생님도 감탄하실 스파게티 코드 완성!!
(리팩토링 하고 다시 올려야겠다. 너무나도 부끄럽다.)

delete(val) {
	let curNode = this.root;
	let parentNode = null;

	while (curNode !== null) {
		// 탐색 진행
		if (curNode.val < val) {
			parentNode = curNode;
			curNode = curNode.right;
		}
		else if (curNode.val > val) {
			parentNode = curNode;
			curNode = curNode.left;
		}
		else {
			// 리프노드일 경우
			if (curNode.left === null && curNode.right === null) {
				console.log('leaf')
				if (parentNode.val < curNode.val) {
					parentNode.right = null;
					return;
				}
				parentNode.left = null;

				return;
			}
			// 자식이 하나일때
			else if (curNode.left && !curNode.right) {
				if (parentNode.val < curNode.val) {
					parentNode.right = curNode.left;
					return curNode;
				}
				parentNode.left = curNode.left

				return curNode;
			}
			else if (!curNode.left && curNode.right) {
				if (parentNode.val < curNode.val) {
					parentNode.right = curNode.right;
					return curNode;
				}
				parentNode.left = curNode.right

				return curNode;
			}

			if (curNode.val < parentNode.val) {
				let min = curNode.right;
				let minParent = curNode.right;

				while (min.left) {
					minParent = min;
					min = min.left;
				}

				if (minParent === min) {
					parentNode.left = min;
					min.left = curNode.lfet;
					curNode.right = null;
				} else {
					if (min.right) {
						minParent.left = min.right;
					}
					else {
						minParent.left = null;
					}
				}

				parentNode.left = min;
				min.right = curNode.right;
				min.left = curNode.left;

			} else {
				let min = curNode.right;
				let minParent = curNode.right;

				while (min.left) {
					minParent = min;
					min = min.left;
				}

				if (minParent === min) {
					parentNode.right = min;
					min.left = curNode.lfet;
					curNode.right = null;
				} else {
					if (min.right) {
						minParent.left = min.right;
					}
					else {
						minParent.left = null;
					}
				}

				parentNode.right = min;
				min.right = curNode.right;
				min.left = curNode.left
			}

			return curNode;
		}
	}

	return null;
	}

[+] 실습 - 입국심사

입력의 최대 범위가 1,000,000,000이므로 이진 탐색이겠구나 추측했습니다.
이진탐색…한번도 풀어본 적 없는데 😥

• 답안

function binarySearch(n, times) {
  let left = 0;
  let right = n * times[times.length - 1]; // n * 가장 긴 심사대
  let answer = right;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    let max = 0;

    for (let t of times) {
      max += Math.floor(mid / t);
    }

    if (max < n) {
      // 심사한 인원이 적어요
      left = mid + 1;
    } else {
      // 심사한 인원이 초과되었으니 right(최대) - 1
      answer = Math.min(mid, answer);
      right = mid - 1;
    }

    mid = Math.floor((left + right) / 2);
  }

  return answer;
}

function solution(n, times) {
  times.sort((a, b) => a - b); // 이분탐색은 정렬 후에 사용 가능
  return binarySearch(n, times);
}

이진탐색 코드를 거의 복붙하다시피 이용했습니다.
JS 이진탐색 코드 외운 후, 사용할 수 있을 만큼 이해해놓자.

---

출처

프로그래머스