Letter Sequence

문자열 가지고 놀기

우리는 매일 글자와 숫자를 쓴다. 보통은 주어진 기본 글자들이 있고, 그것들을 나름의 법칙으로 조합해서 이어서 쓰면 단어를 이루고, 그것을 다시 엮어 문장을 이루고, 문장은 문단을 이루며 그것들로 생각을 드러낸다. 숫자도 마찬가지고 수학의 언어도 마찬가지다. 과학의 언어라고 부릴 수도 있는 수학은 그 자체로 하나의 언어체계다. 보통의 문자 글자들처럼 이것들도 기본 알파벳들과 글을 이루는 분명한 문법을 주면 문자 없이 순수하게 기호로만 나타낼 수도 있다.

어쨌든 거기서 중요한 것은 기호 자체가 아니라, 그것들의 조합으로 된 '내용' 이었다. 그런데, 만약 가장 단순한 기호들만 이어서 쓴다는 지극히 단순한 규칙만 있는 문자열만을 생각해본다면 거기에는 무언가 흥미로운 문제가 생길 수 없을까? 우리는 차차 보게되겠지만 매우 단순한 문자열도 그것을 가지고 놀다 보면 그 안에는 심오한 뜻이 담겨 있다는 것을 보게 된다. 단지 머리와 가슴만 즐겁게 하는 것이 아니다. 이 문제를 해결하는 동안, 우리는, 처음에 예상하기 힘들었던 사실을 알게 된다. 매일 쓰는 전화기나 레이다에 응용되고, 임학, 경제학, 생물학 분야까지 광범위하게 응용된다. 문자열 자체로부터 제기되는 문제와 아울러 처음엔 문자열과 전혀 별개의 문제로 보였지만, 문자열의 도움을 받아 푸

용어 약속

어떤 알파벳들의 집합 $\mathrm {A}$ 이 주어졌다고 하자. 여기서 골라내 알파벳을 하나 이상 이어서 쓴 것을 문자열(string)라 부르기로 약속하고, 문자열이 k 개 까지라면, 'k개 문자열' 또는 '문자열의 길이가 k' 라고 부르자. 이것들 안에 있는 것들 중 연속하는 부분 문자열을 '단어라 부를 것이다.

사례

여기서 나올 용어를 약속하는게 우선이다. 헷갈리지 않기 위해서다.

우리 주위에서 자주 보는 알파벳들의 예를 먼저 보자. 이것들은 시간이 지나오면서 변화를 거쳤다. 앞으로 또 어떻게 발전해갈지 알 수 없다. 지금 표준이 된 것들.

• 한국어 알파벳 집합 : 24글자. (닿소리 14, 홀소리 10)

ㄱ

ㄴ

ㄷ

ㄹ

ㅁ

ㅂ

ㅅ

ㅇ

ㅈ

ㅊ

ㅋ

ㅌ

ㅍ

ㅎ

ㅏ

ㅑ

ㅓ

ㅕ

ㅗ

ㅛ

ㅜ

ㅠ

ㅡ

이것들로 만든 단어들의 예는 굳이 들지 않아도 될 것 같다. 여기 써진 대부분의 글자들이 바로 예니까. 그래도 굳이 골라 보면, '골라' 이라는 문자열의 길이는 다섯 개로 되어 있다. 이것의 부분 집합으로 '단어'라고 부를 수 있는 것들은 '고', '골', '라' 같은 것들이 있다.

• 영어 알파벳 집합 : 26글자.

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z

우리말에서는 글자 하나로 된 단어는 없지만, 영어에서는 가능하다. 예를들어 '나'를 뜻하는 I 나 a 같은 것이 있다. 영어 단어의 예로, they 를 보자. 문자열의 길이는 4 다. 이것의 부분 문자열로는 t, y, th, the, he, hey 같은 것들이 가능하다. 이 중에서 실제로 영어 단어로 쓰이는 것만 해도 여럿이다. 영어에서 단어로 된 사전에 나온 것중 아직까지 가장 긴 것으로 보통 Pneumonoultramicroscopicsilicovolcanoconiosis 로 진폐증을 나타내는 학술용어다. 이것의 문자열은 45다.

• 10진법 체계 수의 알파벳 집합 : 10개

1

2

3

5

6

7

8

9

0

10진법 체계다. 2진법이라면 2개의 기호 만으로도 모두 나타낼 수 있다. 자연수는 그냥 이것들로만 나타낼 수 있고, 정수나 실수는 약간의 기호를 더 해준다. 고작, 두 개, 음수를 나타내는 것과 소수점을 나타낼 수 있으면 된다. 수를 나타내는 숫자는 앞의 문자와 달리 끝없이 길어질 수 있다.

문자열을 가지고 노는 문제

• 단어가 되풀이 안되는 문자열 : 알파벳이 n 개 일 때, m 개의 단어들로 문자열을 쪼갰을 때, 어떤 단어도 반복해서 나오지 않을 가장 긴 문자열 k 는 ?