애드혹 문제 parity는 거창한 수학이 아니라, 문제 상태를 홀수와 짝수 두 가지로 압축해서 보는 사고법입니다. 규칙이 잘 안 보일 때 오히려 parity만 보면 바로 불가능 판정이 나오는 경우가 적지 않습니다.
이 글은 정의 암기보다 감각에 집중합니다. 연산이 parity를 유지하는지, 뒤집는지, 그리고 목표 상태가 parity만 봐도 막히는지를 단계적으로 정리해보겠습니다.
애드혹 문제 parity는 왜 자주 통할까
parity는 정수의 홀수와 짝수 성질입니다. 정보는 아주 적어 보이지만, 애드혹 문제에서는 이 작은 정보가 오히려 강력합니다. 값 전체를 보지 않고도 상태를 두 종류로 압축할 수 있기 때문입니다.
문제를 읽을 때 숫자가 너무 많아 보여도, 실제로는 mod 2만 보면 되는 경우가 있습니다. 짝수는 0, 홀수는 1처럼 생각하면 연산 한 번이 상태를 유지하는지 뒤집는지 빠르게 추적할 수 있습니다.
2칸 이동 예시
시작점이 3이고 한 번에 +2 또는 -2만 할 수 있다고 해보겠습니다. 손으로 몇 개만 써 보면 3, 5, 1, 7, -1처럼 계속 홀수만 나옵니다.
이유는 단순합니다. 홀수에 2를 더해도 홀수고, 2를 빼도 홀수이기 때문입니다. 여기서는 현재 값의 parity가 연산 후에도 바뀌지 않습니다.
그래서 시작점이 홀수인데 목표가 짝수라면 탐색을 시작하기 전부터 불가능합니다. 이런 성질을 불변성이라고 부릅니다.
연산이 parity를 항상 유지하면, 시작 상태와 목표 상태의 parity가 다를 때는 바로 불가능하다고 말할 수 있습니다.
parity 규칙 읽기
모든 parity 문제가 같은 형태는 아닙니다. 어떤 문제는 값의 parity가 그대로 유지되고, 어떤 문제는 연산 한 번마다 parity가 뒤집힙니다.
예를 들어 +1만 할 수 있다면 짝수는 다음에 홀수, 홀수는 다음에 짝수가 됩니다. 이때는 현재 값보다 연산 횟수의 parity가 핵심입니다. 홀수 번 움직였는지, 짝수 번 움직였는지가 마지막 상태를 결정하기 때문입니다.
- 연산이 parity를 유지한다 -> 값 자체의 parity가 불변성
- 연산이 parity를 매번 뒤집는다 -> move count parity가 핵심
- 둘 다 애드혹 문제에서 자주 나오는 패턴이지만 보는 포인트가 다르다
이동 횟수 parity
격자에서 상하좌우로 한 칸씩만 움직인다고 해보겠습니다. 체스판처럼 칸 색을 번갈아 칠하면 한 번 이동할 때마다 색이 바뀝니다.
이 말은 좌표 합 r + c의 parity가 이동할 때마다 뒤집힌다는 뜻입니다. 그래서 시작 칸과 도착 칸의 색이 같으면 이동 횟수는 짝수여야 하고, 색이 다르면 이동 횟수는 홀수여야 합니다.
문제에서 정확히 K번이라는 문장이 보이면 이 체크를 먼저 해보는 편이 좋습니다. BFS나 DP를 쓰기 전에 이미 불가능한 입력을 지울 수 있기 때문입니다.
합의 parity
배열 원소 하나를 골라 1 증가시키는 연산을 생각해보겠습니다. 이 연산은 합을 정확히 1 늘립니다. 즉 합의 parity는 매번 뒤집힙니다.
현재 합이 짝수인데 3번 연산한 뒤 목표 합도 짝수여야 한다고 하면 바로 의심해야 합니다. 짝수에서 3번 뒤집히면 마지막은 홀수여야 하기 때문입니다.
- 현재 합의 parity를 본다
- 한 번의 연산이 합의 parity를 유지하는지 뒤집는지 본다
- K번 후 예상 parity를 계산한다
- 목표 합의 parity와 비교한다
이 네 단계만으로도 완전탐색에 들어가기 전에 불가능한 케이스를 많이 걸러낼 수 있습니다.
개수 parity
parity는 값뿐 아니라 개수에도 붙습니다. 같은 값끼리 둘씩 짝지어 없애야 한다면, 등장 횟수가 홀수인 값은 반드시 하나가 남습니다.
회문 재배열 가능 여부가 대표적입니다. 문자열 길이가 짝수라면 모든 문자 개수가 짝수여야 하고, 길이가 홀수라면 홀수 개수는 정확히 하나만 허용됩니다.
문제에서 둘씩 묶기, 양쪽 대칭 배치, 가운데 하나 남기기 같은 표현이 보이면 개수 parity를 먼저 의심해보면 좋습니다.
배치 문제에서 parity는 종종 정답 전체가 아니라, 가능한지 불가능한지를 먼저 가르는 필터로 작동합니다.
parity 체크리스트
- 연산 한 번이 +1, -1, +2, swap처럼 단순한가
- 정확히 K번 수행해야 하는가
- 도달 가능 여부만 빠르게 물어보는가
- 합이나 개수만 보면 상태가 많이 압축되는가
- 짝짓기, 대칭, 회문, 균등 분배 같은 표현이 있는가
반대로 parity가 맞는다고 해서 항상 가능한 것은 아닙니다. parity는 보통 강한 필요조건이지만 충분조건이 아닐 수 있습니다. 그래서 parity 체크 뒤에는 나머지 제약도 반드시 확인해야 합니다.
코드 예시 1
아래 코드는 현재 합에서 목표 합으로 가는 데 필요한 차이와 연산 횟수 parity를 비교하는 가장 작은 예시입니다. 실전 문제의 모든 제약을 담은 코드는 아니지만, parity 체크가 어디에 들어가는지 감각을 잡기 좋습니다.
from typing import List
def can_reach_target_sum(nums: List[int], target_sum: int, moves: int) -> bool:
current_sum = sum(nums)
diff = target_sum - current_sum
if diff < 0:
return False
# 한 번의 연산이 합을 정확히 1 증가시킨다고 가정
if diff > moves:
return False
return diff % 2 == moves % 2마지막 줄이 핵심입니다. 남은 차이와 연산 횟수의 parity가 맞지 않으면, 숫자를 어떻게 바꿔도 정확히 그 상태에는 도달할 수 없습니다.
코드 예시 2
회문 문제는 parity가 배치 가능성을 가르는 대표 예시입니다. 정렬이나 백트래킹보다 먼저 개수 parity를 보는 것이 더 자연스럽습니다.
from collections import Counter
def can_form_palindrome(s: str) -> bool:
counts = Counter(s)
odd_count = sum(1 for count in counts.values() if count % 2 == 1)
if len(s) % 2 == 0:
return odd_count == 0
return odd_count == 1길이가 짝수면 홀수 개수가 0개여야 하고, 길이가 홀수면 홀수 개수가 1개여야 한다는 규칙이 그대로 코드가 됩니다.
swap parity 힌트
조금 더 어려운 문제에서는 인접 swap과 inversion parity가 등장하기도 합니다. 다만 이 단계는 전제가 더 많으므로, 입문자라면 먼저 값의 parity, 이동 횟수 parity, 합과 개수의 parity 세 가지를 확실히 잡는 편이 좋습니다.
이 세 가지가 익숙해지면 더 복잡한 parity 문제를 만나도 무엇을 먼저 봐야 할지 훨씬 빨리 감이 옵니다.
마무리
애드혹 문제에서 parity는 답을 억지로 끼워 맞추는 요령이 아닙니다. 상태를 가장 작은 정보로 줄였을 때도 남는 규칙이 있는지 확인하는 기본기입니다.
문제를 읽다가 연산이 단순하고, 정확히 K번 같은 조건이 붙고, 도달 가능 여부가 중요해 보인다면 먼저 홀수와 짝수부터 확인해보세요. 그 한 번의 체크만으로도 완전탐색을 시작하기 전에 답의 절반이 정리되는 경우가 많습니다.
관련해서 애드혹 사고 흐름을 더 보고 싶다면 애드혹 문제란 무엇인가, 정렬 후 스캔이 통하는 순간, 누적합과 차분 배열 글을 함께 읽어보면 좋습니다. parity의 수학적 정의는 Parity (mathematics)와 Invariant (mathematics)를 참고할 수 있습니다.
