백준에 순열 사이클 분할(permutation cycle decomposition)이라는 태그가 있어서 공부를 하게 되었다.
기본적인 개념은 다음과 같다.
어떤 순열 $(a_1, a_2, \dots , a_n)$이 있으면 $a_i = f(i)$인 함수가 있다고 생각해보자.
$f^2(i) = f(f(i))$라고 할 때 $i = f^k(i)$인 $1 \le k \le n$을 찾을 수 있다.
그럼 $k$번 연산하는 과정에서 나온 수들을 모으면 $(f(i), f^2(i), \dots, f^k(i))$가 나올 것이고 이것을 하나의 순열 사이클이라고 한다.
순열 사이클 안에 존재하는 원소들은 모두 같은 순열 사이클이 될 것이다.
모든 원소에 대해 수행하면 여러개의 순열 사이클이 나오는데 이를 구하는 것을 순열 사이클 분할이라고 한다.
예를 들어보자.
https://www.acmicpc.net/problem/10451
위 문제의 첫번째 예시는 $(3,2,7,8,1,4,5,6)$이다.
$i=1$부터 시작하면 $1 \rightarrow 3 \rightarrow 7 \rightarrow 5 \rightarrow 1$이다.
이를 모든 원소에 대해 수행해보자.
$i=2 : 2 \rightarrow 2$
$i=3 : 3 \rightarrow 7 \rightarrow 5 \rightarrow 1 \rightarrow 3$
$i=4 : 4 \rightarrow 8 \rightarrow 6 \rightarrow 4$
$i=5 : 5 \rightarrow 1 \rightarrow 3 \rightarrow 7 \rightarrow 5$
$i=6 : 6 \rightarrow 4 \rightarrow 8 \rightarrow 6$
$i=7 : 7 \rightarrow 5 \rightarrow 1 \rightarrow 3 \rightarrow 7$
$i=8 : 8 \rightarrow 6 \rightarrow 4 \rightarrow 8$
중복을 제거하면 순열사이클은 $(1,3,7,5), (2), (4,8,6)$으로 3개가 나오게 된다.
이런식으로 순열사이클을 직접구하거나 개수를 세는 문제가 주로 나온다.
또한 지난번에 포스팅한 현대대수학에 굉장히 유사한 내용이 있다.
문제에서 나타내는 순열을 치환으로 보자.
그럼 순열 사이클은 궤도가 된다.
그리고 위 포스트에 "모든 유한집합의 치환들은 여러개의 서로 소인 순환치환들의 곱으로 나타낼 수 있다."라는 성질이 있기 때문에 하나의 순열은 반드시 순열 사이클 분할이 가능하다는게 보장된다.
# O(N)
# arr의 범위를 0~n-1로 가정
def permutation_cycle_decomposition(arr):
n = len(arr)
check = [False] * n
ans = []
for i in range(n):
if not check[i]:
ix = arr[i]
tmp = [i]
check[i] = True
while ix != i:
tmp.append(ix)
check[ix] = True
ix = arr[ix]
ans.append(tmp)
return len(ans), ans
'프로그래밍 > 알고리즘' 카테고리의 다른 글
[알고리즘] Codeforces Round #775 (Div. 2, based on Moscow Open Olympiad in Informatics) (0) | 2022.03.09 |
---|---|
[알고리즘] Codeforces Round #774 (Div. 2) (0) | 2022.03.05 |
[알고리즘] Codeforces Round #772 (Div. 2) (0) | 2022.02.21 |
[알고리즘] Codeforces Round #771 (Div. 2) (0) | 2022.02.15 |
[알고리즘] Codeforces Global Round 19 (0) | 2022.02.14 |