TIL #054

오늘 한 것

도전

• 부스트캠프 지원

알고리즘

⚠️ 외부 IDE를 사용하지 않고 알고리즘 풀기

• 코딩테스트 고득점 키트 : 해시
  • Lv.1 폰켓몬
  • const solution = (nums) => { const kindNum = new Set(nums).size; return kindNum < nums.length / 2 ? kindNum : nums.length / 2; }
  • Lv.1 완주하지 못한 선수
  • const solution = (participant, completion) => { const sortP = participant.sort(); const sortC = completion.sort(); for(let i = 0; i < sortP.length; i++) { if(sortP[i] !== sortC[i]) return sortP[i]; } }
  • Lv.2 의상
  • const closet = {}; const addCloth = (cloth, type) => { if(!closet[type]) closet[type] = []; closet[type].push(cloth); } const solution = (clothes) => { let answer = 1; clothes.forEach(([cloth, type]) => addCloth(cloth, type)); Object.keys(closet).forEach(type => answer *= closet[type].length + 1 ); return answer - 1; }
  • Lv.3 베스트 앨범
  • const genreInfo = {}; const addGenre = (genre) => { const newGenre = { playSum : 0, songs: [] }; genreInfo[genre] = newGenre; } const addSong = (i, genre, play) => { genreInfo[genre].playSum += play; genreInfo[genre].songs.push([i, play]); } const getBestGenres = () => { const genres = Object.keys(genreInfo); const getSum = (genre) => genreInfo[genre].playSum; return genres .sort((a, b) => getSum(b) - getSum(a)); } const getBestSongs = (genre) => { const {songs} = genreInfo[genre]; const sort = songs.sort((a, b) => b[1] - a[1]); return sort.slice(0, 2).map(([i, play]) => i);; } const solution = (genres, plays) => { genres.forEach((genre, i) => { if(!genreInfo[genre]) addGenre(genre); addSong(i, genre, plays[i]); }); const bestGenres = getBestGenres(); const bestSongs = bestGenres.map(genre => getBestSongs(genre)); return bestSongs.flat(); }
• 코딩테스트 고득점 키트 : 스택 / 큐
  • Lv.1 같은 숫자는 싫어
  • const solution = (arr) => arr.filter((v, i) => v !== arr[i - 1]);
  • Lv2 기능 개발
  • const getLeftDay = (progress, speed) => { return Math.ceil((100 - progress) / speed); }; const solution = (progresses, speeds) => { const leftDays = progresses.map((progress, idx) => getLeftDay(progress, speeds[idx])); const answer = []; let stack = 0; let curLeftDay; leftDays.forEach(leftDay => { if(leftDay > curLeftDay) { curLeftDay = leftDay; answer.push(stack); stack = 1; return; } if(!curLeftDay) curLeftDay = leftDay; stack += 1; }); if(!!stack) answer.push(stack); return answer }
  • Lv.2 올바른 괄호
  • const solution = (s) => { const arr = s.split(''); let stack = 0; for(let i = 0; i < arr.length; i++) { if(arr[i] === '(') { stack += 1; continue; } else { if(!stack) return false; stack -= 1; } }; return !stack; }
  • Lv.2 프로세스
  • const solution = (priorities, location) => { const queue = priorities.map((priority, idx) => [priority, idx === location]); const priorityQueue = priorities.sort((a, b) => b - a); let count = 0; while(true) { const [priority, isTarget] = queue.shift(); if(priority === priorityQueue[0]) { count += 1; if(isTarget) return count; priorityQueue.shift(); } else { queue.push([priority, isTarget]) } }; }
  • Lv.2 다리를 지나는 트럭
  • const solution = (bridge_length, weight, truck_weights) => { const bridge = Array.from({length : bridge_length}, () => 0); let weightSum = 0; let truckSum = 0; let leftTrucks = truck_weights.length; let answer = 0; while(true) { answer += 1; // 다리의 가장 앞에 있는 차 빼기 weightSum -= bridge[0]; const passedTruck = bridge.shift(); if(!!passedTruck) leftTrucks -= 1; if(!leftTrucks) break; if(weightSum + truck_weights[0] <= weight) { weightSum += truck_weights[0]; bridge.push(truck_weights.shift()); } else { bridge.push(0); } } return answer; }

• 코딩테스트 고득점 키드 : 힙
  • Lv.2 이중순위우선큐
  • const solution = (operations) => { const queue = []; operations.forEach(operation => { const [order, num] = operation.split(' '); if(order === 'I') { queue.push(num * 1); queue.sort((a, b) => a - b); } else { if(num === '1') { queue.pop(); } else { queue.shift(); } } }); return [queue[queue.length - 1] || 0, queue[0] || 0] }
  • Lv.3 디스크 컨트롤러
  • function solution(jobs) { var answer = 0; let q = []; jobs.sort((u, v) => { return u[0] - v[0]; }); console.log(jobs); let len = jobs.length; let i = 0; let now = 0; while (i < len || q.length > 0) { if (i < len && jobs[i][0] <= now) { q.push(jobs[i++]); continue; } q.sort((u, v) => { return u[1] - v[1]; }); if (q.length > 0) { let job = q.shift(); now += job[1]; answer += now - job[0]; } else { now = jobs[i][0]; } } return Math.floor(answer / len); }

오늘 배운 것

알고리즘

해시 테이블 (Hash Table)

해시 테이블

특정 key는 특정 idx로 바로 접근하도록 하는 자료구조.

현실에서의 사물함, 자바스크립트의 객체와 동일 구조.

자료를 접근하는데 걸리는 시간복잡도가 O(1)로 매우 빠르다는 장점이 있다.

자바스크립트에서의 사용

객체를 통해 해시 테이블 구조를 이용할 수 있다. (이때, 객체의 key값이 중복되어선 안된다)

번외 : 해시함수

특정한 규칙을 이용하여 입력받은 key 값을 바탕으로 동일한 hash code를 만들어준다.

해시코드를 만드는 함수

입력받은 key값이 공백 하나라도 달라도 전혀 다른 해시코드를 생성한다.

장점 : 해시 코드를 통해 idx에 바로 접근할 수 있기에 검색 속도가 매우 빠르다.

단점 : 해시 함수 알고리즘이 좋지 않을 때, 하나의 idx에 데이터가 너무 많이 몰리게 되는 Hash Algorithm Collison 이 발생할 수 있다. 따라서 Collison을 최소화 하는 좋은 해시 알고리즘이 필요하다.

이러한 해시함수는 주로 블록체인, 암호화 등에서 사용된다.

스택 / 큐 (Stack / Queue)

스택

한쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조

LIFO(last In First Out) 구조를 가진다.

• push : 스택에 자료를 넣는 행위
• pop : 스택에서 자료를 꺼내는 행위

Queue

연속된 데이터의 맨 뒤에 데이터를 넣고, 맨 앞의 데이터를 꺼내는 자료 구조.

FIFO(First In First Out)의 구조를 가진다.

Queue의 위치별 명칭은 다음과 같다.

• front(head) : 큐의 가장 앞 단. 자료를 꺼내는 위치.
• rear(tail) : 큐의 가장 마지막 단. 자료를 넣는 위치.

Queue에서 작동하는 동작은 다음과 같다.

• get : 큐에서 자료를 꺼내는 행위
• put : 큐에 자료를 넣는 행위

Queue와 관련된 에러는 다음과 같다.

• 오버플로우 : 큐가 곽 차서 더 이상 자료를 넣을 수 없는 경우
• 언더플로우 : 큐가 비어 있어 자료를 꺼낼 수 없는 경우

힙 (Heap)

데이터에서 최대값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리 (Complete Binary Tree)

A가 B의 부모노드이면, A의 키 값과 B의 키 값 사이에는 대소관계가 성립한다. 형제 사이의 대소관계는 성립하지 않는다. (관계 없음). 또한 노드 값의 중복도 허용한다. 느슨한 정렬 상태를 유지한다.

가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 루트노드에 오게 되며, 이를 이용하여 우선순위 큐와 같은 자료형을 구현할 수 있습니다.

힙을 사용하는 이유

선형검색을 하여 최솟값, 최대값을 찾게 되면 최대 O(n) 시간복잡도가 소요된다.

하지만 힙을 사용하면 O(logn)의 시간복잡도를 가지게 되어 일반적인 배열을 사용할 때 보다 훨씬 빠르게 최솟값과 최대값을 구할 수 있다.

힙의 종류

• MaxHeap 최대 힙
• 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙. 가장 큰 값을 빠르게 구할 수 있음.
• MinHeap 최소 힙
• 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙. 가장 작은 값을 빠르게 구할 수 있음.

배열로 힙 구현하기

배열로 힙을 구현할 때는 인덱스 1을 루트 노드로 잡고 시작하면 편하다.

• 부모 노드의 인덱스 = 자식 노드의 인덱스 // 2
• 왼쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2
• 오른쪽 자식 노드의 인덱스 = 부모 노드 인덱스 * 2 + 1

삽입 알고리즘 (add)

1. 원소를 배열의 맨 마지막에 넣는다
2. 부모의 노드와 비교하여 더 크거나 / 작으면 바꾼다.
3. 현재 노드가 부모 노드보다 작거나, 가장 위에 도달할 때 까지 2의 과정을 반복한다.

추출 알고리즘 (poll)

1. 배열의 루트 노드를 꺼내준다.
2. 맨 끝의 노드를 비어있는 루트 노드 자리로 옮겨준다.
3. 변경되어 루트로 간 노드가 자식 노드보다 작거나 / 크면은 바꿔준다.
4. 현재 노드가 부모 노드보다 크거나, 가장 아래에 도달할 때 까지 2의 과정을 반복한다.
5. 처음에 꺼낸 노드를 반환한다

힙에서 구현되는 프로퍼티 및 메서드

1. heap : 노드들을 담는 배열
2. getParentIndex(idx) : 부모 인덱스를 구하는 메서드
3. getLeftChildIndex(idx) : 왼 자식 인덱스를 구하는 메서드
4. getRightChildIndex(i) : 오른 자식 인덱스를 구하는 메서드
5. swap(idx1, idx2) : 두 노드를 교환하는 메서드
6. hepifyUp() : 위 방향으로 부모, 자식 노드를 비교하는 메서드
7. add(value) : heap에 새로운 값을 더하는 메서드
8. heapifyDown() : 아래 방향으로 부모, 자식 노드를 비교하는 메서드
9. poll() : heap에서 루트 값을 빼어 재정렬한 후, 루트 값을 리턴하는 메서드

자바스크립트에서 MinHeap 구현하기

function MinHeap() {
  // heap : 노드들을 담는 배열
  this.heap = [null];

  // getParentIdx(idx) : 부모 인덱스를 구하는 메서드
  this.getParentIdx = (idx) => {
    return Math.floor(idx / 2);
  };
  // getLeftChildIndex(idx) : 왼 자식 인덱스를 구하는 메서드
  this.getLeftChildIdx = (idx) => {
    return idx * 2;
  };

  // getRightChildIndex(i) : 오른 자식 인덱스를 구하는 메서드
  this.getRightChildIdx = (idx) => {
    return idx * 2 + 1;
  };
  // swap(idx1, idx2) : 두 노드를 교환하는 메서드
  this.swap = (idx1, idx2) => {
    const temp = this.heap[idx2];
    this.heap[idx2] = this.heap[idx1];
    this.heap[idx1] = temp;
  };

  // hepifyUp() : 위 방향으로 부모, 자식 노드를 비교하는 메서드
  this.heapifyUp = () => {
    let curIdx = this.heap.length - 1;
    while (
      curIdx !== 1 &&
      this.heap[this.getParentIdx(curIdx)] > this.heap[curIdx]
    ) {
      this.swap(curIdx, this.getParentIdx(curIdx));
      curIdx = this.getParentIdx(curIdx);
    }
  };

  // heapifyDown() : 아래 방향으로 부모, 자식 노드를 비교하는 메서드
  this.heapifyDown = () => {
    let curIdx = 1;

    while (this.heap[this.getLeftChildIdx(curIdx)] !== undefined) {
      let smallestIdx = this.getLeftChildIdx(curIdx);
      const rightIdx = this.getRightChildIdx(curIdx);

      if (
        this.heap[rightIdx] !== undefined &&
        this.heap[rightIdx] < this.heap[smallestIdx]
      ) {
        smallestIdx = rightIdx;
      }

      if (this.heap[smallestIdx] < this.heap[curIdx]) {
        this.swap(curIdx, smallestIdx);
        curIdx = smallestIdx;
        continue;
      }
      break;
    }
  };

  // add(value) : heap에 새로운 값을 더하는 메서드
  this.add = (value) => {
    this.heap.push(value);
    this.heapifyUp();
  };

  // poll() : heap에서 루트 값을 빼어 재정렬한 후, 루트 값을 리턴하는 메서드
  this.poll = () => {
    const root = this.heap[1];
    this.heap[1] = this.heap.pop();
    this.heapifyDown();
    return root;
  };
}

오늘 느낀 점

와 진짜 최선을 다해 풀었다. 이제 힙은 완전 정복한듯.