MST, 백트래킹, Prefix Sum에서 자주 놓치는 지점들

우주신과의 교감

이 문제는 MST를 사용하여 해결하는 문제였습니다. 문제의 조건과 해결 방법을 찾는 과정은 어려울 게 없었습니다. 하지만 사소한 부분에서 계속 실수하는 것은 정말 고쳐야 하는 습관이라는 생각이 들었습니다. 변수의 이름을 제대로 사용하지 않아 문제를 틀리는 것은 정말 바보 같은 짓이기 때문에 이러한 부분에 대한 검토는 반드시 이루어져야 할 것 같습니다.

색종이 붙이기

풀었던 문제를 다시 푼 것인데도 제대로 해결하지 못했습니다. 그 이유는 조건을 제대로 고려하지 못했고, 모두 고려하지 않았기 때문입니다. 예를 들어 이 문제에서는 조건에 따라 좌표를 점프할 필요가 있었습니다. 한 번 탐색한 값의 경우 다시 탐색할 필요가 없기 때문이죠.

그렇다면 점프한 이후에는 다시 정상적인 범주로 탐색을 해야 하기 때문에 초기화하는 과정이 반드시 필요할 것입니다. 하지만 이 부분을 고려했지만 제대로 작성하지 못했다는 것이 문제였습니다.

또한 좌표에 대한 이동을 제대로 구현하지 못한 것이 문제였습니다. 예를 들어 size 가 4일 경우 좌표를 어떤 범위까지 검사해야 하는가에 대한 의사결정을 제대로 하지 못했습니다.

// let size = 1; size <= 5; size++ 인지
// let size = 0; size < 5; size++ 인지를 제대로 결정하지 못했습니다.

function checkFill(size, x, y, board, remain) {
  const [nx, ny] = [x + size, y + size];
  if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
    return false;
  }
}

위와 같이 결정을 하지 못하다 보니 초과가 되지 않는 범위 또한 초과가 되었다고 검사를 수행하는 작업들이 반복되다 보니 문제를 해결하는 과정에서 버벅이게 되었습니다. 이를 해결하기 위해서는 값의 제한 범위가 명확한 값을 사용하는 것이 중요하다고 생각했습니다.

$\text{현재 위치} + \text{색종이 크기} \le \text{전체 맵 크기}$

위와 같이 값의 범위 내에 있는 것을 검사하거나 이외의 경우를 확실하게 범위를 제한하여 검사하는 것이 중요하다고 생각했습니다.

그리고 배열을 복사할 것인가 현재 작성되어 있는 배열을 재사용할 것인지에 대한 판단을 제대로 수행하지 못했습니다. 배열을 복사하는 행위는 당연히 비용이 발생하기 때문에 무작정 하는 것은 좋지 못합니다. 배열의 크기가 작을 경우에는 배열을 반복하며 작업을 수행하는 것이 배열을 복사하는 행위보다 메모리 효율과 작업 시간에 유리할 수 있다는 점을 반드시 생각해야 합니다.

A. 배열 복사 (Deep Copy)

매 재귀 호출마다 현재 상태를 보존하기 위해 새로운 배열을 생성합니다.

• 비용: $O(N^2)$ (전체 배열 크기만큼 순회하며 값 복사) + 메모리 할당 오버헤드
• 단점: 탐색 깊이가 깊어질수록, 호출 횟수가 많아질수록 기하급수적으로 성능이 저하됩니다. 특히 JavaScript나 Python 같은 언어에서는 가비지 컬렉션(GC) 부하가 발생할 수 있습니다.

언제 유리한가? 상태 변화가 매우 복잡하여 되돌리는 연산(Undo)이 까다로울 때. 재귀 깊이가 매우 얕을 때.

가비지 컬렉션(GC) 부하: 재귀 함수 내에서 const newBoard = ...와 같이 매번 새로운 배열을 생성하면, Heap 메모리에 수만 개의 배열 객체가 생성됩니다. 이는 V8 엔진의 GC를 빈번하게 실행시켜, 알고리즘 로직 외적인 부분에서 Stop-the-world 현상을 유발하고 시간 초과로 이어질 확률이 매우 높습니다.

피아노 체조

이 문제는 반복하여 찾을 경우 작업시간이 O(N^2) 이기 때문에 반드시 최적화를 적용한 탐색 방법으로 문제를 해결했어야 합니다. 하지만 저는 이 방법에 대해서 생각하지 못해서 문제를 해결하지 못했습니다.

이 문제에서 찾을 수 있는 특징은 구간이 존재하며 이 구간들은 선으로 연결이 된다는 점, 구간의 합을 구해야 한다는 것을 힌트로 이 문제는 Prefix Sum를 적용하여 해결해야 하는 문제였습니다. 오랜만에 prefix sum을 사용하려니 조금 헷갈려서 이를 좀 정리하고 넘어가겠습니다.

Prefix Sum 범위 설정 공식

배열의 값(nums)은 점(Point) 입니다. (개수: $N$) 하지만 우리가 구하려는 nums[i-1] > nums[i]는 두 점을 잇는 선분(Line/Edge) 입니다. (개수: $N-1$)

입력받은 a, b는 점의 범위인데, 계산해야 하는 건 선분의 합이므로 여기서 인덱스 -1 차이가 발생합니다. 구하고자 하는 prefix의 값의 정의는 prefix[i] = "$i$번째와 $i+1$번째 사이의 관계" 로 표현할 수 있습니다.

예시 데이터: 5 3 1 2 4 (N=5) 우리가 확인하고 싶은 것: 앞의 숫자가 더 큰 구간(내리막길)의 개수

인덱스(1-based):   1       2       3       4       5
값(nums):        [ 5 ]   [ 3 ]   [ 1 ]   [ 2 ]   [ 4 ]
                   ↘       ↘       ↗       ↗
비교(Gap):       (1~2)   (2~3)   (3~4)   (4~5)
내리막 여부:       True    True    False   False

핵심 규칙

1. 구간의 개수: $N$개의 숫자가 있으면, 비교 가능한 구간(Gap)은 $N-1$개입니다.
2. 인덱스 매핑: $i$번째 숫자와 $i+1$번째 숫자의 비교 결과는 편의상 $i$번째 인덱스에 저장하는 것이 일반적입니다. (혹은 코드처럼 뒤쪽인 $i+1$에 저장하기도 함)
3. 쿼리 변환: "구간 $a$부터 $b$까지"라는 말은, 숫자 $a$번부터 $b$번 사이의 관계를 묻는 것입니다.
   • 숫자: $a, a+1, ..., b$
   • 관계(틈): $(a, a+1), ..., (b-1, b)$
   • 결론: 우리는 인덱스 $a$부터 $b-1$까지의 합을 구해야 합니다.

Prefix Sum 문제를 풀 때 범위가 헷갈린다면 다음 3단계를 따르세요.

1. 데이터가 '점'인가 '선'인가?
   • 점(그냥 숫자 합): $a \sim b$ 까지 더함 $\rightarrow$ P[b] - P[a-1]
   • 선(인접 차이/비교): $a \sim b$ 사이의 구간 합 $\rightarrow$ P[b-1] - P[a-1]
2. Loop의 끝은 어디인가?
   • 인접 비교(i vs i+1)를 할 때는 반드시 Length - 1까지만 반복하세요.
3. 검증(Test)은 가장 작은 단위로:
   • "1부터 2까지"를 넣었을 때 답이 나오는지 확인해보세요.
   • prefix[2-1] - prefix[1-1] = prefix[1] - prefix[0] (1번째 관계 값 하나만 나옴) $\rightarrow$ 성공!