Loading [MathJax]/jax/output/CommonHTML/jax.js

본문 바로가기

순열 사이클 분할1

순열 사이클 분할:백준 25577, 7805, 10451 1. 기본 개념순열

$(a_1, a_2, \dots, a_n)$ 이 주어졌을 때, 이를 함수

$f(i)$ 로 표현할 수 있다. 여기서

$f(i)$ 는

$i$ 번째 원소를 다른 원소의 위치로 매핑하는 함수이다.예를 들어, 순열

$(2, 3, 1)$ 이 있다면:

$f(1) = 2$ : 첫 번째 위치의 원소는 두 번째 위치로 간다.

$f(2) = 3$ : 두 번째 위치의 원소는 세 번째 위치로 간다.

$f(3) = 1$ : 세 번째 위치의 원소는 첫 번째 위치로 간다.2. 함수의 반복적 적용

$f^2(i) = f(f(i))$ : 함수

$f$ 를 두 번 적용한 결과이다.

$f^k(i)$ :

$f$ 를

$k$ 번 반복 적용한 결과이다.만약

$i = f^k(i)$ 가 되는 최소

$k$ 를 찾으면, 이는

$i$ 가 순환하는 주기이다.3. 순열 사이클$i.. 2025. 1. 9.

이전 1 다음

티스토리툴바