[TIL] 20210621 - 항해 15일차

Jihyun·2021년 6월 21일

TIL(Today I Learned)algorithm article 항해99

항해99

목록 보기

12/46

TIL에 매일 알고리즘을 쓰고 있으려니 민망하다💇🏻‍♀️
하지만 열흘 동안은 완전히 알고리즘에 몰입하는 시간이기 때문에 그저 계속... 계속... 알고리즘을 풀고있다.

오늘 공부한 것

BAEKJOON ONLINE JUDGE(BOJ)

오늘의 알고리즘 코드 바로가기(github)

1149 RGB 거리
1932 정수 삼각형
11047 동전 0
11399 ATM
2606 바이러스
11279 최대 힙

알고리즘을 풀며 배운 것 & 생각

1) 어떤 방식으로 알고리즘을 풀 지 신중히 고민하자
어제 나에게 고민을 안겨준 1149 RGB 거리.
어제는 백트래킹으로 시간 초과를 맛보았기 때문에 동적계획법으로 생각을 바꿔보았다.

점화식을 찾을 때는 그냥 쭉 나열해보는 것이 최고였다.
뭘 더 줄이고 머리로 계산한 값만 써놓고 하다보면 다 놓치기 마련이었다.

이렇게 간단하게 그 전까지의 min 값만 잘 저장해두면 되는 것을...🙄🙄🙄
(~~최솟값을 구해야 하는데 max라고 써둬서 조금 고생했다.~~)

위 낙서를 코드로 표현하면 다음과 같다.(최솟값)

  let [R, G, B] = ary[i].split(" ").map((num) => Number(num));
  let valueR = Math.min(R + dp[i - 1][1], R + dp[i - 1][2]);
  let valueG = Math.min(G + dp[i - 1][0], G + dp[i - 1][2]);
  let valueB = Math.min(B + dp[i - 1][0], B + dp[i - 1][1]);
  dp[i] = [valueR, valueG, valueB];

이렇게 간단하게 끝날 문제를 백트래킹에 심취하여 놓쳤다.
문제를 잘 파악해서 가장 효율적인 방법을 찾아내는 것에 집중하자.

2) heap(max heap)
heap은 기본 알고리즘 강의에서도 한 번 다뤘던 적이 있다.
하지만 다른 개념에 비해 확 와닿지 않았는지 금세 잊었고, 결국 11279 최대 힙을 공부하며 풀어야했다.

아래는 백준이 나를 통과시켜준 코드다.

class MaxHeap {
  constructor() {
    this.storage = [null]; // index = 0 자리를 null로 채워서 쓰지 않게 만들어줌 (편하게);
  }

  insert(value) {
    this.storage.push(value);
    let index = this.storage.length - 1;
    while (index > 1) {
      let parentIndex = Math.floor(index / 2);
      if (this.storage[parentIndex] < this.storage[index]) {
        let temp = this.storage[index];
        this.storage[index] = this.storage[parentIndex];
        this.storage[parentIndex] = temp;
        index = parentIndex;
      } else {
        break;
      }
    }
  }

  delete() {
    let lastIndex = this.storage.length - 1;
    let temp = this.storage[lastIndex];
    this.storage[lastIndex] = this.storage[1];
    this.storage[1] = temp;
    let targetIndex = 1;
    let maxNum = this.storage.pop();

    while (true) {
      let leftChildIndex = targetIndex * 2;
      let rightChildIndex = targetIndex * 2 + 1;
      let maxIndex = targetIndex;

      if (
        leftChildIndex <= this.storage.length - 1 &&
        this.storage[leftChildIndex] > this.storage[maxIndex]
      )
        maxIndex = leftChildIndex;

      if (
        rightChildIndex <= this.storage.length - 1 &&
        this.storage[rightChildIndex] > this.storage[maxIndex]
      )
        maxIndex = rightChildIndex;

      if (maxIndex === targetIndex) break;

      let targetValue = this.storage[maxIndex];
      this.storage[maxIndex] = this.storage[targetIndex];
      this.storage[targetIndex] = targetValue;
      targetIndex = maxIndex;
    }
    return maxNum;
  }
}

let result = "";

const maxHeap = new MaxHeap();

for (let num of ary) {
  if (num === 0) {
    result += maxHeap.storage.length === 1 ? `0\n` : `${maxHeap.delete()}\n`;
  } else {
    maxHeap.insert(num);
  }
}

console.log(result.trim());