불변량 (Invariant)

정의

불변량 (Invariant) 은 어떤 변환(operation)이 적용되어도 변하지 않는 양이나 성질. 불가능성 증명, 알고리즘의 정당성(correctness) 증명, 종료 조건 분석에 사용. 대표적으로 parity, coloring, sum/mod, algebraic invariant 가 있다.

문제 상황과 동기

“이 상태에서 저 상태로 도달할 수 있는가?” 를 판별할 때, 가능한 모든 연산을 시뮬레이션할 수는 없다.

• naive: BFS/DFS로 모든 상태 탐색. 상태 공간이 지수적으로 커짐.
• invariant: 항상 보존되는 양 Q를 찾아, Q(initial) != Q(target) 임을 보이면 불가능 증명. O(1) 판별.

핵심 통찰: 변환은 특정 양을 보존한다. 보존되는 양이 다르면 절대 도달할 수 없다.

시각화

핵심 아이디어

초기 상태 S0 = (변수, 구조, ...)
불변량 I(S) 가 모든 가능한 변환 T 에 대해 I(S) = I(T(S)) 를 만족
I(S0) != I(목표) => 목표 도달 불가능

대표적인 불변량:

알고리즘

invariant_check(sequence, operation):
    I = compute_invariant(sequence)
    # operation 이 I 를 보존하는지 확인
    for each possible operation:
        assert I == compute_invariant(apply(sequence, operation))
    # 목표 상태의 I 와 비교
    return I == compute_invariant(target)

구현

// 순열의 inversion parity 계산
// 불변량: 인접 swap 은 inversion parity 를 바꾸지 않는다
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n; cin >> n;
  vector<int> a(n);
  for (auto& v : a) cin >> v;
  int inv = 0;
  for (int i = 0; i < n; i++)
      for (int j = i + 1; j < n; j++)
          if (a[i] > a[j]) inv++;
  cout << (inv % 2 == 0 ? "even" : "odd") << "\n";
  // 15-puzzle: inversions % 2 == 0 이면 solvable (empty row 보정)
  return 0;
}

# 도미노 체스판: checkerboard coloring invariant
# 두 칸을 제거했을 때 도미노로 전부 덮을 수 있는가?
def can_cover(r1, c1, r2, c2):
  # 각 도미노는 검+흰 1개씩 덮음
  # 제거된 두 칸이 다른 색이어야 가능
  color = lambda r, c: (r + c) % 2
  return color(r1, c1) != color(r2, c2)
​
a, b, c, d = map(int, input().split())
print(1 if can_cover(a, b, c, d) else 0)
# BOJ 7538: 서로 다른 색 두 칸만 제거 가능

// Parity invariant for permutation
import java.util.*;
public class Main {
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int[] a = new int[n];
      for (int i = 0; i < n; i++) a[i] = sc.nextInt();
      int inv = 0;
      for (int i = 0; i < n; i++)
          for (int j = i + 1; j < n; j++)
              if (a[i] > a[j]) inv++;
      System.out.println(inv % 2 == 0 ? "even" : "odd");
  }
}

4
3 1 4 2

even

복잡도

변형 / 활용

함정

1. 불변량이 충분 조건이 아닐 때

같은 불변량 값을 가져도 실제로 도달 가능하지 않을 수 있음. parity 만으로 15-puzzle 이 완전히 결정되지는 않음 (empty tile row 도 고려).

2. invariant vs monovariant 혼동

불변량은 변하지 않는 양. Monovariant는 단조 변하는 양 (항상 증가/감소). 후자는 알고리즘 종료 증명에 사용.

3. 불변량을 잘못 선택

너무 강한 불변량은 깨지기 쉽고, 너무 약한 불변량은 useless. 경험적으로 mod 2, sum, XOR 이 자주 통함.

BOJ 연습 문제

참고

• 순열 사이클 분해
• 홀짝성
• 그래프 탐색
• 게임 이론 (Sprague-Grundy 의 mex invariant)