12.2.1 드 부루인 수열

드 부루인 수열

드 브루인 수열(De Bruijn sequence) 은 문자열의 일종으로, 글자의 종류가 $k$일 때 만들 수 있는 길이가 $n$인 모든 문자열을 정확히 한 번씩 포함하는 것을 말한다. 드 브루인 수열의 길이는 $k^n+n-1$이 된다. 예를 들어 $n=3$이고 $k=2$일 때, 드 브루인 수열의 예는 다음과 같다.

$$0001011100$$

이 문자열의 길이가 3인 부분 문자열은 3bit의 모든 조합인 $000,001,010,011,100,101,110,111$이다.

길이가 $n-1$인 모든 문자열이 노드에 대응되고, 수열에 한 글자를 덧붙이는 것이 간선에 대응되는 그래프를 생각하자.¹ 드 브루인 수열은 이 그래프의 오일러 경로와 항상 대응된다. 예를 들어 그림 14의 그래프는 $n=3$이고 $k=2$인 경우에 대응된다. 드 브루인 경로를 찾기 위해서는 임의의 노드에서 시작하여 모든 간선을 정확히 한 번 방문하는 오일러 경로를 찾으면 된다. 시작 노드와 간선의 글자를 차례로 더하면 $k^n+n-1$개의 글자로 이루어진 문자열이 되고 이는 올바른 드 브루인 수열이 된다.

• 그림 14. 오일러 경로를 이용하여 드 브루인 수열 찾기
  • 
  • 현재 노드의 뒤에 글자 하나를 추가한 뒤, 가장 앞의 글자를 버리고 다시 길이 2로 만든 것이 다음 노드

예를 들어 다음과 같이 이동할 수 있다.

$$00\stackrel{0}{\to }00\stackrel{1}{\to }01\stackrel{0}{\to }10\stackrel{1}{\to }01\stackrel{1}{\to }11\stackrel{1}{\to }11\stackrel{0}{\to }10\stackrel{0}{\to }00$$

시작 노드 00을 먼저 적고, 지나간 간선의 글자를 순서대로 붙이면

$$00+0+1+0+1+1+1+0+0=\boxed{0001011100}$$

구현 방법

• 오일러 회로 기반 일반 구현 → 히어홀처 알고리즘
• 메모리를 적게 쓰는 직접 생성 → FKM 알고리즘
• 이진 수열의 간단한 탐욕 생성 → Prefer-one 알고리즘

생각해볼 문제

• 똑똑한 도둑 - JUNGOL

Footnotes

1. 혹은, 문자열의 맨 앞 글자를 제거하고 맨 뒤에 한 글자를 추가하는 것이 간선에 대응된다고 생각할 수도 있다. ↩