요세푸스 문제를 세 층위로 푸는 방법

n 명이 둥글게 서서 한 사람씩 건너뛰며 제거할 때 마지막에 남는 사람을 찾는 문제다. 같은 답을 세 가지로 구했다.

그대로 시뮬레이션

def last_live(n):
    li = [i for i in range(1, n + 1)]
    b = []

    while li != []:
        li.append(li.pop(0))
        b.append(li.pop(0))

    return b[-1]

맨 앞을 빼서 뒤로 보내고(살리고), 그 다음 사람을 빼서 b 에 넣는다(제거한다). 리스트가 비면 b 의 마지막이 최후의 생존자다.

원형을 따로 만들지 않고 앞에서 빼서 뒤에 붙이는 것으로 회전시킨다. 제거된 순서가 b 에 그대로 남는 것도 덤이다.

n 번 반복하고 매번 pop(0) 을 하므로 리스트 전체가 밀린다.

2의 거듭제곱으로

from math import *

n = 40
p = (n - 2**int(log(n) / log(2))) * 2 + 1

n 보다 작거나 같은 최대 2의 거듭제곱을 찾아 n 에서 뺀 나머지를 두 배 하고 1을 더한다.

n 이 정확히 2의 거듭제곱이면 남는 게 없어서 답이 1이다. 사람 수가 2의 거듭제곱이면 한 바퀴 돌 때마다 정확히 절반이 남고, 시작점이 그대로 유지되기 때문이다.

그렇지 않으면 2의 거듭제곱이 될 때까지 먼저 몇 명을 제거하고, 그 시점에서 시작점이 옮겨간 만큼을 계산하는 것이다.

log(n) / log(2) 로 밑을 바꾼다. int 로 내림한다. 부동소수점이라 n 이 2의 거듭제곱일 때 값이 아슬아슬하게 밑돌면 어긋날 수 있는 형태다. n.bit_length() - 1 이면 정수 연산으로 끝난다.

이진수를 왼쪽으로 돌리기

n = 40
a = bin(n)
p = int(a[3:] + a[2], 2)   # Left rotate

bin(40) 은 '0b101000' 이다. a[2] 가 최상위 비트인 '1' 이고 a[3:] 가 나머지 '01000' 이다. 앞의 1을 떼어 맨 뒤로 보내면 '010001' 이 되고 이건 17이다.

앞의 공식과 같은 이야기다. 최상위 비트를 떼는 것이 2의 거듭제곱을 빼는 것이고, 뒤에 붙이는 것이 두 배 하고 1을 더하는 것이다. x 를 두 배 하면 이진수에서 왼쪽으로 한 칸 밀리고, 1을 더하면 맨 뒤 자리에 1이 들어온다.

식으로 쓰던 걸 표기법으로 옮기니 계산이 사라졌다. 문자열 자르기와 붙이기만 남는다.

값 확인

2의 거듭제곱인 2와 16에서 1이 나온다. 7은 '111' 을 돌려도 '111' 이라 자기 자신이다.