비트 해석, MST, 배열 회전 공식을 정리한 문제 풀이 메모

물병

이 문제는 비트바이트를 사용해서 문제를 해결해야 하는 문제였습니다. 이 문제에서 얻을 수 있는 인사이트는 2와 관련되어 증감되는 수의 경우 비트를 사용해서 해결할 것을 의심해보는 것입니다.

이 문제의 해결방법은 다음과 같습니다. N의 값은 물의 병의 수를 뜻합니다. 문제의 조건은 물 1병당 기본 1리터의 물이 담겨 있다는 조건이 있습니다. 그렇기 때문에 N이 13일 경우 초기 물의 총 양은 13리터가 있는 것과 같습니다.

그렇다면 이 문제를 해결하기 위해 초기 물의 양을 병으로 치환한다면 몇 병이 필요할까요? 이 문제의 조건은 2의 단위로 합칠 수 있고 2의 배수가 아닌 경우는 오직 1뿐입니다. 이러한 조건으로 생각해보면 13의 물의 양은 1 + 4 + 8 으로 3병으로 나누는 것이 최소한의 병을 사용하여 물을 담는 최선의 방법입니다.

그리고 이 13이라는 숫자를 이진수로 표현한다면 1101이 됩니다. 우연찮게도 이 숫자의 1의 개수가 필요한 병의 수와 일치합니다. 그럼 이 가설을 검증하기 위해 1 증가한 값인 N이 14인 경우로 다시 생각해보겠습니다.

14를 병으로 표현한다면 2 + 4 + 8 로 여전히 3병이 필요합니다. 이 수를 이진수로 변환하면 1110으로 여전히 1의 수는 3으로 3병과 일치합니다. 그럼 15 또한 계산해보겠습니다. 15를 수로 표현한다면 1 + 2 + 4 + 8 으로 4병이 필요합니다. 이를 이진수로 표현하면 1111로 필요한 병의 수와 일치합니다.

이 문제는 이런 식으로 규칙을 찾아서 해결해야 하는 문제였습니다. 이 문제에서 추가적으로 얻을 수 있는 인사이트는 모든 수는 2의 제곱 수로 표현이 가능하다는 것입니다. 또한 문제를 해결하기 위해서는 문제의 숨겨진 규칙을 찾아내는 것 또한 필요하다는 것입니다.

도시 분할 계획

이 문제는 최소신장트리 MST 문제였습니다. 이 부분을 잘 몰라서 해결하지 못했습니다. 이때 최소 신장 트리가 갖는 특징은 다음과 같습니다.

• 신장 트리(Spanning Tree): 그래프 내의 모든 정점을 포함해야 합니다.
• 연결성: 모든 정점이 서로 연결되어 있어야 하며, 고립된 정점이 없어야 합니다.
• 무사이클(Acyclic): 트리 구조이므로 사이클이 존재하지 않아야 합니다.
• 최소 가중치: 구성된 간선들의 가중치 합이 최소가 되어야 합니다.

최소 신장 트리를 생성하기 위한 알고리즘인 크루스칼 알고리즘의 사고 과정은 다음과 같습니다.

1. 연결되어 있는 간선의 비용을 최소 비용 기준으로 정렬한다.
2. 정렬된 간선을 탐색하여 가장 적은 비용을 갖는 간선부터 연결한다.
3. 2의 과정에서 순환이 발생할 경우 해당 간선은 연결하지 않고 다음 간선으로 넘어간다.

class UnionFind {
  constructor(size) {
    this.parent = Array.from({ length: size }, (_, i) => i);
    this.ranks = Array(size).fill(0);
  }

  find(node) {
    if (this.parent[node] !== node) {
      this.parent[node] = this.find(this.parent[node]);
    }
    return this.parent[node];
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);

    if (rootX === rootY) {
      return false;
    }

    if (this.ranks[rootX] < this.ranks[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.ranks[rootX] > this.ranks[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.ranks[rootX] += 1;
      this.parent[rootY] = rootX;
    }

    return true;
  }
}

순환을 찾는 것은 Union-Find를 활용하면 되고 나머지 부분은 어렵지 않기 때문에 추가적으로 언급하지 않고 넘어가겠습니다.

마법사 상어와 파이어스톰

이 문제에서 너무 많은 시간이 걸렸습니다. 배열을 회전시키는 로직은 수학 공식처럼 외우는 게 좋다고 판단하였습니다. 이외의 문제의 경우 조건을 제대로 읽지 않고 조건을 구현하지 못해서 시간이 오래 걸렸습니다. 이런 경우를 봐서 저는 독해력이 그다지 좋지 않은 것 같습니다. "이후 얼음이 있는 칸 3개 또는 그 이상과 인접해 있지 않은 칸은 얼음의 양이 1 줄어든다." 이 구문을 빠르게 이해하지 못했습니다.

각설하고 외웠어야 하는 메인 로직에 대해서 작성하겠습니다.

function rotate90DegClockwise(arr) {
  const [R, C] = [arr.length, arr[0].length];
  const newArr = Array.from({ length: R }, () => Array(C).fill(0));

  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      newArr[c][N - 1 - r] = arr[r][c];
    }
  }
  return newArr;
}

function rotate90DegCounterClockwise(arr) {
  const [R, C] = [arr.length, arr[0].length];
  const newArr = Array.from({ length: R }, () => Array(C).fill(0));

  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      newArr[C - 1 - c][r] = arr[r][c];
    }
  }
  return newArr;
}