중복순열
중복순열 정의
중복순열이란 서로 다른 원소들로 구성된 집합에서 일부 원소를 반복하여 선택하면서 순서를 고려하는 조합 방식입니다. 예를 들어, 숫자 1, 2, 3이 있을 때 2개씩 뽑아 만드는 중복순열은 (1,1), (1,2), (1,3), (2,1), … (3,3)처럼 원소가 반복될 수 있으며, 순서도 중요하게 취급됩니다. 이는 컴퓨터 비밀번호 생성, 게임 시뮬레이션, 제품 코드 조합 등에 자주 활용됩니다.
중복순열 공식
n개의 서로 다른 원소 중에서 중복을 허용하여 r개를 선택하는 중복순열의 수는 n^r(n의 r제곱)으로 계산됩니다. 예를 들어, 알파벳 3개(A, B, C) 중에서 2개를 중복 가능하게 뽑는다면 가능한 조합 수는 3² = 9개가 됩니다. 이 공식은 계산이 간단하면서도 다양한 실생활 예제에 적용됩니다.
일반 순열과의 차이
일반 순열은 한 번 선택된 원소는 다시 선택하지 않으며, 순서를 중요하게 여기는 조합입니다. 반면 중복순열은 동일한 원소를 여러 번 선택 가능하며 역시 순서를 고려합니다. 예를 들어 일반 순열로 (A, A)는 불가능하지만, 중복순열에서는 가능하므로 문제의 조건에 따라 어떤 순열을 적용해야 할지 판단하는 것이 중요합니다.
활용 예시
중복순열은 비밀번호나 시리얼 코드 생성, AI 시뮬레이션 경로 탐색, 통계 샘플링, 복권 번호 조합 등에서 유용하게 활용됩니다. 특히, 데이터 중복이 허용되는 상황이나 반복 선택이 자연스러운 환경에서 자주 사용됩니다. 예를 들어, 길이 4의 비밀번호를 숫자 0~9로 만들 경우, 총 10⁴ = 10,000개의 조합이 가능합니다.
문제 해결 전략
중복순열 문제를 풀 때는 **원소의 개수(n)와 뽑을 개수(r)**만 알면 공식 n^r을 적용해 바로 계산할 수 있지만, 조건이 있는 문제에서는 조합을 체계적으로 나열해보는 것도 도움이 됩니다. 특히, 프로그래밍 알고리즘 문제에서는 백트래킹(backtracking) 기법을 활용하여 중복순열을 구현하는 경우가 많습니다. 이 경우 중복 허용 여부를 조건문으로 명확히 분리해주는 것이 중요합니다.