Even Permutation (1) 썸네일형 리스트형 수열의 홀짝성 feat. [ICPC] 백준 5000 - 빵 정렬 수열의 홀짝성 일단 순열 {1, 2, 3}이 있고 6! 만큼 순열을 나열하는 경우를 살펴보자. 각 순열에 대해 다음과 같은 연산을 시행한다고 해보자. 순열에서 임의의 두 인접한 원소를 교환한다.(이하 transposition) 여러 번 하다 보면 흥미로운 현상을 관찰할 수 있다. transposition을 반복하다 보면 어떤 순열 a에서 순열 b로 만들 수 없는 경우가 존재한다는 것이다. 여기서 두 집합을 살펴보자. 집합 A에 속한 순열과 집합 B에 속한 순열들은 transposition으로 서로 다른 집합에 속한 순열로 만드는 것이 불가능하다. 그리고 각 집합에 속한 순열들에 대해 inversion number를 세면 공통점을 발견할 수 있다. *inversion number: 수열의 i번째 원소 $a.. 이전 1 다음
