이 글에서는 드래곤 커브(Dragon Curve) 수열의 n번째 항을 구하는 C++ 프로그램을 살펴보겠습니다.
드래곤 커브 수열은 무한히 이어지는 이진수 수열입니다. 수열은 1로 시작하며, 각 단계마다 이전 항의 각 원소를 차례대로 살펴보면서 그 뒤에 1과 0을 번갈아 추가하고, 맨 앞에는 항상 1을 붙여 다음 항을 완성합니다.
- 제1항 : 1
- 제2항 : 110
- 제3항 : 1101100
- 제4항 : 110110011100100
생성 과정을 조금 더 자세히 보면, 먼저 결과 문자열을 1로 초기화한 뒤 이전 항의 문자를 하나씩 붙이고, 그때마다 0과 1을 교대로 추가합니다. 예를 들어 제2항 "110"에서는 1 뒤에 0, 다음 1 뒤에 1, 마지막 0 뒤에 0을 붙여 제3항 "1101100"을 얻습니다. 이렇게 새로 만든 항이 현재 항이 되면 같은 과정을 반복하여 원하는 n번째 항까지 수열을 생성할 수 있습니다.
예제 코드
#include <iostream>
using namespace std;
string dragCurveTerm(int n) {
string term = "1";
for (int i = 2; i <= n; i++) {
string temp = "1";
char prev = '1', zero = '0', one = '1';
for (int j = 0; j < term.length(); j++) {
temp += term[j]; //원본 문자열에서 문자를 하나씩 가져옴
if (prev == '0') {
temp += one;
prev = one;
} else {
temp += zero;
prev = zero;
}
}
term = temp;
}
return term;
}
int main() {
cout << "4th term of Dragon Curve Sequence: " << dragCurveTerm(4);
}코드의 동작 방식은 다음과 같습니다. 우선 첫 항을 "1"로 설정하고, 2번째 항부터 n번째 항까지 반복문을 돌립니다. 각 반복에서 임시 문자열을 다시 1로 초기화한 후, 이전 항의 모든 문자를 순서대로 붙이면서 직전에 추가한 비트(prev)가 0이었으면 1을, 1이었으면 0을 번갈아 이어 붙입니다. 한 항이 완성될 때마다 이를 현재 항으로 갱신하므로, 함수가 반환하는 값이 곧 n번째 항이 됩니다.
실행 결과
4th term of Dragon Curve Sequence: 110110011100100
실행 결과는 앞서 살펴본 제4항 "110110011100100"과 정확히 일치하는 것을 확인할 수 있습니다.