02. 두 번째 수업: 줄 세우기, 그리고 팩토리얼 (Factorial !)

1장 순열에서 우리는 $[1등, 2등, 3등]$ 까지만 슬롯을 까놓고 반복 연산을 중단하여 커트(Cut) 했습니다. (그래서 $_5P_3$ 의 뒤쪽 곱셈 찌꺼기인 $2 \times 1$ 은 버려지고 $5 \times 4 \times 3$ 만 취했죠.)

하지만 만약 세상이 미쳐 돌아가, 교실에 앉아있는 30명의 반란군 전원을 복도 바깥 체육관 땡볕에 모조리 끌어내서, “1번 자리부터 끝번호 30번 자리 꽁무니까지 전원 다 열맞춰 한 줄 직렬로 배열 렌더링 세팅해버려!” 라고 명령을 한다면 이 경우의 수 우주의 가지 수는 도대체 몇 개로 찢어질까요?

팩토리얼 폭발과 원순열의 붕괴 SVG

1. 전원 강제 소집 스크립트! 느낌표 기호의 충격

다섯 놈만 가지고 전원 줄 세우기를 해봅시다. (이것은 순열 $P$ 코드로 $_5P_5$ 이라 씁니다.) 첫 슬롯부터 맨 뒤 슬롯까지 얄짤없이 계속 찌그러지며 줄어듭니다.

  • 1번 마이크 자리 후보: $5$마리
  • 2번 자리 후보: $4$마리 남음
  • 3번 통과 구멍: $3$마리 남음
  • 4번 방: $2$마리 남음
  • 5번, 마지막 찌꺼기 뒷방: 불쌍한 떨거지 최종 단 $1$마리가 남아서 울며 겨자 먹기로 뒷문에 강제 배정.

이 연쇄 곱의 트리 루프는 $= \mathbf{5 \times 4 \times 3 \times 2 \times 1}$ 로 터져 나갑니다. 결과는 $\mathbf{120}$개 시나리오 렌더링.

수학자들은 숫자가 1씩 카운트다운되면서 끝내 바닥 한계치인 ”$\mathbf{1}$”에 도달하여 마감 셧다운 락킹(Lock) 이 걸릴 때까지, 모든 중간 배열 숫자들을 한 치 오차 없이 무자비하게 죄다 곱해버리는 이 악랄한 루핑 연산 파이프라인의 폭력성에 경악을 금치 못했습니다. 그래서 이 미친듯한 팽창 렌더링 함수에 경고의 의미로 느낌표(!) 라는 강력한 기호를 냅다 박아서 이름 짓고 코드로 등록시켰습니다!

$\mathbf{N!}$ (N 팩토리얼 Factorial): $\mathbf{N \times (N-1) \times (N-2) \times \dots \dots \times 3 \times 2 \times 1}$

2. 엄청난 초팽창 버그 (Factorial Explosion)

팩토리얼($!$) 함수 엔진은 겉보기엔 정말 귀엽고 앙증맞은 기호 디자인에 불과해 보입니다. “$10!$ (십팩)” 이라고 쓰면 애기들 장난 같죠.

자, 과연 장난일까요? 단지 교실 책상 분단에 $\mathbf{10}$명의 학생을 일렬로 줄 세우는 방식을 시켰을 뿐입니다. $10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 =$ ?

정답: $\mathbf{3,628,800}$ 갈래 멀티버스!! (약 362만 개의 평행우주 시나리오)

파이썬 알고리즘 사이트(백준이나 프로그래머스) 코딩 테스트에 갔는데 “단 한 명의 낙오자 없이 $10$놈을 대상으로 배열 노가다 시뮬레이션을 구현하세요.” 라는 완전탐색 재귀 함수(DFS Permutation) 문제가 출제되었다 칩시다. 이걸 수작업으로 돌리면 당신의 PC 쿨러 팽팽 돌아가는 팬 모터가 연기를 내뿜으며 약 $\mathbf{362만}$번의 for 문의 이중 중첩 루프 지옥에 빠져 CPU를 터뜨릴 것입니다. (물론 10팩이면 요즘 컴으론 $0.1$초 컷이긴 합니다. 하지만 15팩토리얼만 가더라도, $\mathbf{1조}$ 갈래 우주가 넘어가서 Time Limit Exceeded 뻗어버립니다!)

3. 원탁 조작 버그: “야! 꼬리랑 머리가 합쳐졌네?!”

직선 한 줄 줄 세우기($N!$) 가 질리자, 도박꾼들이 악명을 떨칠 새로운 트릭을 하나 가져옵니다. “이 일자선 기차 꼬리를 잡고 휘어서, 둥근 도넛 원탁 회의(원탁 테이블) 에 둥글게 사람을 돌려 앉히면 어떻게 될까?”

이 원탁(Circular Permutation) 배열에서는 소름 돋게도 배열 위치값이 “방향” 이라는 중심 가이드라인을 잃어버리고 파괴됩니다. $A, B, C, D$ 가 일렬($!$) 로 서 있을 때는 자리가 확실했지만, 둥근 테이블에 앉으면 다 같이 오른쪽으로 의자를 한 칸씩 드르륵 굴려서 이동해도 서로를 바라보는 구조(옆 사람) 가 완벽히 똑같은 복제 Clone이 됩니다. (원탁이 한 칸 돌려진 것일 뿐, 배치 순서 상대성이 안 변함)

  • 즉, $4$명을 한 줄로 나열! $\rightarrow \mathbf{4!}$
  • 그런데, 이 녀석들이 앉은 의자가 $\mathbf{4}$칸이 모두 동그랗게 대칭이니까 다 똑같이 겹치네? 중복 오차 발생!
  • 중복 제거 압축 락다운: $\frac{4!}{4} = 3 \times 2 \times 1 = \mathbf{(4-1)!} = \mathbf{3!}$ 로 배열 우주들이 압축 붕괴(너프) 되어 쪼그라듭니다!

원순열 공식: $N$명을 둥근 테이블에 둘러앉히는 가지 수 = $\mathbf{(N - 1)!}$ (한 놈을 테이블 기준점 록으로 박아버려야 해결됨!)

줄 세우기의 폭력적 질서를 보았으니, 다음 3강 편에서는 드디어 “순서가 뒤죽박죽이든 $A-B$ 든 $B-A$ 든 아 몰랑, 똑같은 대표 바구니 그룹이잖아!!” 라고 평등하게 파이프라인을 부숴서 갈아버리는 궁극의 조합 압축 필터(Combination “C”) 의 코드를 조립하러 넘어갑니다.

서브목차