파이썬으로 코넬 시퀀스(Connell Sequence)의 n번째 항 구하기

코넬 시퀀스(Connell Sequence)는 홀수와 짝수를 일정한 규칙에 따라 교차 배치한 흥미로운 수열입니다. 이 수열은 다음과 같은 방식으로 만들어집니다.

첫 번째 홀수 1개를 취합니다: 1
다음 짝수 2개를 취합니다: 2, 4
그다음 홀수 3개를 취합니다: 5, 7, 9
이어서 짝수 4개를 취합니다: 10, 12, 14, 16

이런 식으로 그룹의 크기를 하나씩 늘려가며 홀수와 짝수를 번갈아 나열하면 다음과 같은 수열이 완성됩니다.

1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, 19, 21, ...

예를 들어 입력값이 12라면 출력 결과는 21이 됩니다.

접근 방법

n번째 항을 효율적으로 구하기 위해 다음 단계를 따릅니다.

i := 1로 초기화합니다.
(i × (i + 1) / 2)의 몫이 n + 1보다 작은 동안 i를 1씩 증가시킵니다.
idx := i × (i + 1) / 2 (몫만 사용)
num := i²
num − 2 × (idx − n − 1)을 반환합니다.

동작 원리

이 알고리즘의 핵심은 각 그룹이 제곱수로 끝난다는 점입니다. 첫 번째 그룹은 1(=1²), 두 번째 그룹은 4(=2²), 세 번째 그룹은 9(=3²), 네 번째 그룹은 16(=4²)으로 끝납니다. 또한 k번째 그룹까지의 전체 항 개수는 삼각수인 k(k+1)/2와 같습니다. 따라서 삼각수를 이용해 목표 항이 속한 그룹을 찾은 뒤, 그룹의 마지막 값(제곱수)에서 뒤쪽으로 갈수록 2씩 감소한다는 규칙을 적용하면 원하는 항을 바로 계산할 수 있습니다.

예제 코드

class Solution:
    def solve(self, n):
        i = 1
        while (i * (i + 1) // 2) < n + 1:
            i += 1
        idx = i * (i + 1) // 2
        num = i**2
    return num - 2 * (idx - n - 1)

ob = Solution()
print(ob.solve(12))