배열 회전, 나머지 합, 역방향 스케줄링 정리

배열 돌리기 3

이 문제에서 잘못했던 것은 이전의 배열 돌리기 공식을 잘못 이해했다는 것입니다.

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

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

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

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

위와 같이 배열 또한 회전하면 변경되어야 한다는 점을 잊어서는 안 됩니다. 기존에는 정사각형을 기준으로 회전을 시키는 공식을 암기하였기 때문에 당연하게 가로와 세로의 길이를 전혀 고려하지 않고 문제를 해결하였는데 이 부분이 이 문제를 해결하는 데 어려움을 만들었습니다.

나머지 합

이 문제를 읽자마자 우선 prefix sum 와 완전 탐색을 사용해서는 O(N^2) 의 작업 시간으로는 제한조건인 $10^6$을 절대 통과할 수 없다는 것을 알 수 있었습니다. JavaScript의 1초에 작업할 수 있는 작업량은 1억 이하이기 때문입니다.

그래서 이 문제는 수학적으로 접근하여 해결했어야 합니다. 이 문제의 요구사항은 "연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하시오" 입니다. 이 부분을 다르게 해석할 수 있었어야 합니다.

기존의 수식을 표현하면 $(S[i] - S[j]) \% M = 0$ 로 표현됩니다. 그렇다면 이는 $(S[i] \% M) - (S[j] \% M) = 0$ 와 같이 표현할 수 있습니다. 식을 이렇게 표현하면 이제 조건이 좀 더 명확해졌습니다. 부분합을 계산하고 이 부분합을 M으로 나눈 나머지가 같은 값의 조합을 구해야 하는 문제로 개선이 가능합니다.

function getCombination2(n) {
  if (n < 2) return 0;
  return (n * (n - 1)) / 2;
}

위의 로직이 $_nC_2$ 를 구하는 공식이므로 이를 활용하여 prefix sum을 M으로 나눈 나머지 값들의 개수 중 조합을 구하여 반환하면 됩니다.

시간 관리하기

이 문제는 흔히 볼 수 있는 스케줄링 문제였습니다. 저는 이 문제를 이분 탐색을 활용하여 해결하고자 하였습니다. 이 방법 자체는 문제가 되지 않았습니다. 하지만 문제의 의도는 그리디를 활용하여 해결하는 것이었기 때문에 이 방법을 사용하여 해결하는 것도 확인해볼 필요가 있습니다.

이런 스케줄링 문제를 해결할 때 흔히 사용하는 방법은 역방향 스케줄링(Backward Scheduling) 을 사용하는 방법입니다. 이 방법은 "언제 일을 시작해야 하는가?"가 아닌, "언제까지 일을 마쳐야 하는가?" 를 기준으로 거꾸로 계획을 세우는 방식입니다.

이 방법은 유휴시간을 최소화하는 것입니다. 유휴시간이 짧은 작업을 너무 일찍 시작해서 완료해두면, 그 결과물을 보관해야 하는 비용이 들거나 다른 급한 일을 처리할 기회비용을 날리게 됩니다. 따라서 데드라인에 딱 맞춰서 끝내기 위해 가장 늦게 시작할 수 있는 시간을 계산하기 위해 역으로 계산을 수행하는 것입니다.