수열의 홀짝성 feat. [ICPC] 백준 5000 - 빵 정렬

수열의 홀짝성

일단 순열 {1, 2, 3}이 있고 6! 만큼 순열을 나열하는 경우를 살펴보자.

 

각 순열에 대해 다음과 같은 연산을 시행한다고 해보자.

 

순열에서 임의의 두 인접한 원소를 교환한다.(이하 transposition)

 

여러 번 하다 보면 흥미로운 현상을 관찰할 수 있다. transposition을 반복하다 보면 어떤 순열 a에서 순열 b로 만들 수 없는 경우가 존재한다는 것이다. 여기서 두 집합을 살펴보자.

 

집합 A에 속한 순열과 집합 B에 속한 순열들은 transposition으로 서로 다른 집합에 속한 순열로 만드는 것이 불가능하다. 그리고 각 집합에 속한 순열들에 대해 inversion number를 세면 공통점을 발견할 수 있다.

 

*inversion number: 수열의 i번째 원소 $a_{i}$에서 $a_{i}$보다 뒤에 있는 원소들 중 $a_{i}$보다 작은 원소의 개수들을 모든 i에 대해 합한 값

 

한 집합에 속한 순열들의 inversion number parity는 같다.

 

그렇다. 서로 같은 패리티를 가진 순열은 transposition으로 같게 만드는 것이 가능하다. 그리고 이 transposition은 다른 연산으로도 표현할 수 있다. 예를 들어 인접한 세 원소 A B C에 대해 C A B로 쉬프팅 하는 것이 있다. 이 연산도 어떻게 보면 transposition과 동치이다.

 

이렇게 수열에서 inversion number의 패리티를 수열의 홀짝성이라 부르며 패리티가 홀수면 odd permutation, 짝수면 even permutation이라 부른다. 이걸로 어떻게 문제를 푸는지 콘테스트 문제와 ICPC 기출을 통해 알아보자.

Swap Hats

https://atcoder.jp/contests/abc244/tasks/abc244_d

D - Swap Hats

이 문제는 그냥 위에 설명한 예시의 {1, 2, 3}이 {R, G, B}로 바뀐 것뿐이다. 우리는 이제 수열의 홀짝성이 뭔지 알고 있으니 간단하게 풀 수 있다.

ICPC 빵 정렬

https://www.acmicpc.net/problem/5000

5000번: 빵 정렬

문제를 잘 읽으면 transposition을 통해 두 순열을 같게 만들 수 있는지 물어보는 문제다. Inversion number는 펜윅 트리를 통해 $O(NlogN)$의 시간 복잡도로 inversion counting을 하여 구할 수 있음이 알려져 있고 이를 통해 두 순열의 홀짝성이 같은지 확인하면 된다.

중복된 원소가 있는 수열

지금까지 설명한 예시는 전부 각 원소가 한 번만 등장하는 순열에 대해 다뤘다. 그렇다면 중복 원소가 있는 임의의 수열은 어떻게 될까?

 

중복 원소가 존재하는 경우에는 transposition을 통해 수열의 패리티가 바뀌는 것을 알 수 있다.(직접 해보자) 따라서 중복 원소가 있으면 홀짝성 상관없이 무조건 같게 만들 수 있다.

 

중복이 존재할 수 있는 수열에 대한 홀짝성 매칭은 다음 문제로 연습할 수 있다.

 

https://atcoder.jp/contests/arc136/tasks/arc136_b

B - Triple Shift

 

마찬가지로 두 수열의 홀짝성을 확인하면 되는 문제며, 원소가 같지 않은 경우가 있을 수 있으니 이를 유의해야 한다.

 

지금까지 우리는 수열의 홀짝성에 대해 알아보았다. 마이너한 주제인 것 같으면서도 생각보다 출제 빈도가 높으니 확실히 익혀두면 수열 문제에 대해 한층 더 높은 대응력을 기대할 수 있을 것이다.