김건우

Polya's Enumeration Theorem을 이용한 카운팅 문제 해결

개요 Polya’s Enumeration Theorem(포여 열거 정리)는 어떤 작용에 대한 equivalence class의 개수를 구할 때 사용됩니다. 대표적인 예시로 돌리거나 뒤집어서 같은 것을 하나로 볼 때, 서로 다른 목걸이의 개수를 구하는 문제가 있습니다. 이 글에서는 Burnside Lemma와 그것의 일반화인 Polya’s Enumeration Theorem을 소개한 후 이를 적용하여 문제를 해결하는 과정을 서술하겠습니다. 관련 문제는 백준 문제집 또는 알고리즘 분류에서 찾아볼 수 있습니다. 해당 태그를 가진 문제가 9문제에 불과한 만큼 CP에서 자주 등장하는 주제는 아닙니다. 그렇지만 특정 형태의 카운팅 문제를...