홀짝성 (Parity)

2026년 6월 23일 · 수정 2026년 6월 23일 · 📖 약 3분 · 935자/단어 #algorithm #foundation #parity

정의

홀짝성 (Parity) 은 어떤 양이 짝수 / 홀수 라는 두 상태로 분류되는 불변량.

수학적으로는 mod 2 의 값. PS 에서는 증명 (impossibility), 2색 분할, 대칭성, 그래프의 connected component 의 사이클 홀짝 같은 패턴에서 핵심 도구.

문제 상황과 동기

“NxN 보드의 모든 칸을 색칠. 한 번에 한 행 / 한 열 전체를 토글. 모든 칸을 검정으로 만들 수 있나?”

무차별 시뮬레이션은 2^N 시도. N=20 정도까지만.
홀짝성 관찰: 한 칸이 토글된 횟수 = (자기 행 토글) + (자기 열 토글). 두 횟수의 parity 합 만 중요.
이걸로 행/열 시도 횟수의 parity 조합 만 다루면 충분 → O(N²) 또는 더 단순.

핵심 통찰: 어떤 연산도 parity 를 invariant 로 보존 하면, 그 parity 가 불변량 (invariant) 으로 가능 / 불가능 판정.

시각화

핵심 아이디어

Parity = invariant

"각 연산이 X 의 parity 를 변하지 않게 한다" 
⇒ "초기 parity ≠ 목표 parity" 이면 도달 불가능

예시 1: 8-puzzle

3x3 의 빈칸 + 8개 타일. 한 번에 인접 타일을 빈칸과 swap. 도달 가능한 상태 ↔ inversion 수의 parity 가 보존.

예시 2: 이분 그래프

그래프가 이분 (bipartite) ↔ 모든 사이클이 짝수 길이 ↔ BFS 트리에서 각 정점의 깊이 parity 가 색상.

예시 3: XOR 게임

게임의 상태 = stone heap. 마지막 stone 가져가는 자가 이김 (Nim). 답: XOR (a_1 ^ a_2 ^ ... ^ a_n) 의 parity / 0 인지.

활용 패턴

패턴	적용
그래프 2-color	BFS 깊이 % 2
체스보드 색칠	(x + y) % 2
Inversion 수	merge sort + 카운트, parity check
Sprague-Grundy	Nim, XOR sum 의 0 여부
불가능 증명	”invariant 가 보존 안 됨” 으로
Toggle ops	짝수 번 토글 = 원상복귀
거리 parity	그래프에서 두 정점 거리의 짝홀

알고리즘

이분 그래프 판정

bipartite(G):
    color[v] = -1 for all v
    for each unvisited v:
        BFS / DFS:
            color[start] = 0
            for each edge (u, w):
                if color[w] == -1:
                    color[w] = color[u] ^ 1
                elif color[w] == color[u]:
                    return false  # 홀수 사이클 발견
    return true

Inversion 수의 parity

inversion(a):
    cnt = 0
    merge_sort_with_count(a, cnt)
    return cnt % 2

구현

// 그래프가 이분 그래프인지 판정 (parity 기반 BFS)
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m; cin >> n >> m;
  vector<vector<int>> adj(n + 1);
  while (m--) {
      int u, v; cin >> u >> v;
      adj[u].push_back(v);
      adj[v].push_back(u);
  }
  vector<int> color(n + 1, -1);
  bool ok = true;
  for (int s = 1; s <= n && ok; s++) {
      if (color[s] != -1) continue;
      queue<int> q;
      q.push(s); color[s] = 0;
      while (!q.empty() && ok) {
          int u = q.front(); q.pop();
          for (int v : adj[u]) {
              if (color[v] == -1) {
                  color[v] = color[u] ^ 1;
                  q.push(v);
              } else if (color[v] == color[u]) {
                  ok = false; break;
              }
          }
      }
  }
  cout << (ok ? "YES" : "NO") << "\n";
}

# 이분 그래프 판정
from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
for _ in range(m):
  u, v = map(int, input().split())
  adj[u].append(v); adj[v].append(u)

color = [-1] * (n + 1)
ok = True
for s in range(1, n + 1):
  if color[s] != -1 or not ok: continue
  color[s] = 0
  q = deque([s])
  while q and ok:
      u = q.popleft()
      for v in adj[u]:
          if color[v] == -1:
              color[v] = color[u] ^ 1
              q.append(v)
          elif color[v] == color[u]:
              ok = False; break
print("YES" if ok else "NO")

// 이분 그래프 판정
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      List<List<Integer>> adj = new ArrayList<>();
      for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
      for (int i = 0; i < m; i++) {
          st = new StringTokenizer(br.readLine());
          int u = Integer.parseInt(st.nextToken());
          int v = Integer.parseInt(st.nextToken());
          adj.get(u).add(v); adj.get(v).add(u);
      }
      int[] color = new int[n + 1];
      Arrays.fill(color, -1);
      boolean ok = true;
      for (int s = 1; s <= n && ok; s++) {
          if (color[s] != -1) continue;
          Deque<Integer> q = new ArrayDeque<>();
          q.add(s); color[s] = 0;
          while (!q.isEmpty() && ok) {
              int u = q.poll();
              for (int v : adj.get(u)) {
                  if (color[v] == -1) {
                      color[v] = color[u] ^ 1;
                      q.add(v);
                  } else if (color[v] == color[u]) {
                      ok = false; break;
                  }
              }
          }
      }
      System.out.println(ok ? "YES" : "NO");
  }
}

stdin

결과

YES

복잡도

작업	비용
Parity 한 번 계산	O(1) (`& 1`)
이분 그래프 판정 (BFS / DFS)	O(V + E)
Inversion parity (merge sort)	O(N log N)
XOR sum parity	O(N)
공간	O(V) (이분 색칠), O(N) (inversion)

함정

1. 정수 overflow 의 parity

a + b 의 parity 는 (a ^ b) & 1 로 안전. 큰 수 환경에서는 overflow 와 무관.

2. 음수 mod

-1 % 2 는 언어 따라 -1 또는 1. parity 비교는 & 1 (비트 마스크) 가 안전.

3. 이분 그래프 판정의 disconnected case

connected component 별로 색칠. 각 component 가 이분이어야 전체 이분.

4. Inversion parity vs count

8-puzzle 같은 문제에서 parity 만 보면 됨. 정확한 개수 가 필요한 문제 (예: 정렬 비용) 는 머지 소트로 풀이.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 1707	이분 그래프	-	kokoa-lab
BOJ 1014	컨닝	-	kokoa-lab
BOJ 2243	사탕상자	-	kokoa-lab

참고

이 글의 용어 (4개)

불변량 (Invariant)algorithm: 정의 불변량 (Invariant) 은 어떤 변환(operation)이 적용되어도 변하지 않는 양이나 성질. 불가능성 증명, 알고리즘의 정당성(correctness) 증명, 종료 …
비트마스킹 (Bitmask)algorithm: 정의 비트마스킹 (Bitmask) 은 집합 / 상태 를 정수의 비트 패턴 으로 인코딩해 집합 연산을 비트 연산으로 처리하는 기법. 같은 집합을 으로 표현하면, 멤버 확인 / 추가…
스프라그-그런디 정리 (Sprague-Grundy)algorithm: 정의 스프라그-그런디 정리 (Sprague-Grundy) 는 모든 impartial combinatorial game (두 플레이어가 같은 행동 가능, 무작위성 없음, 완전 정보…
이분 그래프 (Bipartite Graph)algorithm: 정의 이분 그래프 (Bipartite Graph) 는 정점 집합 V 를 두 개의 독립 집합 L, R 로 분할할 수 있고, 모든 간선이 L 과 R 을 잇는 그래프. 같은 집합 내 …

이 개념을 다룬 위키 페이지 (1)

wiki불변량 (Invariant)