우리가 알고 있던 셔플 알고리즘, 사실 거꾸로 돌고 있었다면?

안녕하세요, 8년차 개발자 김테크입니다.

백엔드 개발을 하다 보면 간혹 데이터를 무작위로 섞어야 할 때가 있습니다. 카드 게임의 덱을 섞거나, 추천 시스템에서 아이템의 순서를 임의로 바꿀 때 말이죠. 대부분의 개발자는 언어 차원에서 제공하는 shuffle 함수를 사용하지만, 그 내부가 어떻게 구현되어 있는지 들여다본 적이 있으신가요?

가장 표준적이고 널리 알려진 알고리즘은 피셔-예이츠 셔플(Fisher-Yates Shuffle)입니다. 시간 복잡도 O(N)으로 완벽하게 무작위 순열을 만들어내는 아주 우아한 알고리즘이죠.

보통 우리가 배우는, 그리고 파이썬 라이브러리 내부 등에서 실제로 사용되는 구현은 다음과 같이 리스트의 뒤에서부터 앞으로 루프를 돕니다.

import random

def fisher_yates_shuffle(a):
    # 인덱스 i는 n-1에서 1까지 감소
    for i in range(len(a) - 1, 0, -1):
        j = random.randint(0, i)  # 0 이상 i 이하의 정수
        a[i], a[j] = a[j], a[i]

코드를 보면 인덱스 i가 배열의 끝에서 시작해 0 방향으로 줄어듭니다. 그런데 문득 이런 의문이 들지 않나요? "왜 굳이 거꾸로 돌릴까? 그냥 앞에서부터 순서대로 섞으면 안 되나?"

사실, 루프를 앞에서부터 돌리는 변형된 구현도 가능합니다. 단순히 인덱스의 진행 방향만 바꾸는 것이죠. 아래 코드를 한번 보겠습니다.

def forward_shuffle(a):
    # 인덱스 i는 1에서 n-1까지 증가
    for i in range(1, len(a)):
        j = random.randint(0, i)  # 0 이상 i 이하의 정수
        a[i], a[j] = a[j], a[i]

이 코드는 표준 구현과는 다릅니다. 표준적인 방식은 뒤쪽의 '확정된 자리'를 만들어가는 방식인 반면, 이 '전방향(Forward)' 방식은 앞쪽에서부터 스왑을 진행합니다. 흥미로운 점은 이 방식 역시 수학적으로 완벽하게 균등한 확률 분포를 보장한다는 것입니다.

증명 방식은 꽤 직관적입니다. 표준 피셔-예이츠 셔플이 일련의 스왑 연산을 뒤에서부터 수행한다면, 이 전방향 셔플은 정확히 동일한 무작위 스왑 연산들을 그저 역순으로 수행하는 것과 같습니다. 어떤 무작위 순열이 균등하게 분포한다면, 그 순열의 역(inverse) 또한 균등하게 분포하기 때문입니다.

그렇다면 왜 전공 서적이나 표준 라이브러리들은 굳이 역방향(Backward) 방식을 고집하는 걸까요?

단순히 관습 때문만은 아닙니다. 여기에는 실무적인, 특히 시스템 성능과 관련된 이유가 숨어 있습니다.

첫째, 부분 셔플(Partial Shuffle)의 효율성 때문입니다.

역방향 방식(표준)을 다시 생각해보면, 루프가 한 번 돌 때마다 리스트의 맨 뒤쪽 요소 하나는 '완벽하게 섞인 상태'로 확정됩니다. 만약 여러분이 100만 개의 데이터 중 무작위로 5개만 뽑고 싶다면 어떻게 할까요? 표준 방식을 쓰면 루프를 5번만 돌리고 멈추면 됩니다. 그 뒤쪽 5개는 이미 전체 집합에서 무작위로 추출된 결과와 같습니다. 하지만 전방향 방식은 루프가 끝까지 돌아야만 모든 요소의 확률이 확정되므로, 중간에 멈출 수가 없습니다.

둘째, 메모리 접근 패턴입니다.

표준 방식은 뒤쪽에 '완료된 구역'을 남기고, 앞쪽의 '섞여야 할 구역'의 크기를 점점 줄여나갑니다. 섞어야 할 대상 범위가 점점 좁아지기 때문에 캐시(Cache) 효율 측면에서 미세하게 유리할 수 있습니다. 반면 전방향 방식은 루프가 진행될수록 스왑 대상의 범위(0부터 i까지)가 점점 커지므로 메모리 접근 범위가 계속 늘어납니다.

물론 전방향 방식이 쓸모없는 것은 아닙니다. 이 방식은 인사이드-아웃(Inside-Out) 알고리즘이라는 이름으로 불리며, 리스트의 전체 크기를 미리 알 수 없는 경우(예: 스트림 데이터)나 외부 소스에서 데이터를 받아오면서 동시에 섞어야 할 때 매우 유용하게 사용됩니다.

오늘의 결론입니다. 우리가 무심코 사용하는 표준 알고리즘에는 "왜 그렇게 만들었는지"에 대한 이유가 분명히 존재합니다. 하지만 그 이유를 이해하고 나면, 상황에 따라 "거꾸로 된" 방식이 더 적합한 경우도 발견할 수 있습니다.

개발자로서 "원래 그렇다"라는 말보다는, "이 코드는 왜 이 방향으로 흐를까?"라는 질문을 한 번 더 던져보는 건 어떨까요? 작은 호기심이 때로는 시스템의 성능을 최적화하는 열쇠가 되기도 하니까요.