순환 소수의 순환 마디를 찾는 알고리즘 :: 2008/03/27 10:18
|
|
최근에 중학생 한명에게 프로그래밍을 가르치고 있습니다. 저는 프로그래밍을 업으로 삼으면서도 이 일에 대한 확신이 부족해서 그런지 (능력이 없으니 당연하겠죠 -_-;;) 그 학생에게 프로그래밍에 관심을 가지는 것은 좋지만, 벌써부터 업으로 하겠다는 생각은 하지 말라고 충고했습니다. ㅋㅋ 존 카멕과 같은 걸출한 프로그래머는 중학생때 이미 자신의 인생의 방향을 결정해서 성공하기도 했는데 말이죠. 아무튼 그건 그렇고.
이 학생을 가르치면서, 컴퓨터의 구조와 컴퓨터 언어에 대해서 아무 것도 모르는 사람에게 프로그래밍 언어를 가르친다는 것이 얼마나 힘든 일인지 새삼 깨닫게 되더군요. 사실 저는 예전에 대학에서 컴퓨터 프로그래밍 언어를 계절학기 동안 가르쳤던 적도 있고, 비트 컴퓨터 교육센터에서는 한 3년간 일년에 한두번씩 C++을 강의하기도 했었습니다. 그래서 처음에는 쉬울 거라고 생각했죠. 그런데 아니더군요.
가르친지 한 석달이 넘었는데, 아직도 이 학생은 컴퓨터를 사용해서 문제를 해결하지 못하고 있습니다. 뭐, 뻔한 결론입니다만, 강사 탓이겠죠. 이 학생의 최초 희망은 컴퓨터 게임 프로그래머였는데, 날이 갈수록 그 희망으로부터 조금씩 멀어지고 있다는 것을 느낍니다. 사실 가장 큰 장애물은 이 학생이 컴퓨터 앞에 앉아 있을 시간이 없다는 거예요. 컴퓨터 앞에 앉아 있으면 부모님들이 학교 공부 안한다고 싫어하시거든요. (아무래도 이 아르바이트도 오래 못갈듯.. ㅋㅋ)
그래서 요즘은 이 학생에게 "중학교 수학을 Java로 푸는" 과제들을 내 주고 있습니다. 아무래도 학교 공부와 관련된 것을 하면, 이 학생이 시간을 할애하기가 좋을 것 같다는 계산에서죠. 최근에 풀어본 문제로는, "사람이 하는 나누기 계산 과정을 프로그램으로 흉내내기"같은 것이 있습니다. 1/3을 계산해서 double 형 변수에 저장하면 0.333333333334 이렇게 나오잖아요? 실제로는 순환소수(무한소수죠)인데, 표현력 한계상 중간에서 저렇게 짤리고 말죠. 이 '표현력 상의 한계'를 좀 뛰어넘어 보자는 것이 과제의 목적이었습니다. 최소한 0.3333333333333333333333333333333333333333333333333333.... 이런 식으로 출력될 수 있도록 하자는 것이었죠.
이 문제는 간단히 풀 수 있었습니다. Ruby로 풀어보자면 이렇습니다
#constant
LIMIT = 1000def get_double_array(dev,todev)
p = dev
q = todev
m = 0
result = []
(0 .. LIMIT-1).each do |i|
result[i] = (p / q)
break if (m = p % q) == 0
p = m * 10
end
return result
end
위의 함수를 피젯수와 젯수를 인자로 주어 실행하면 그 계산 결과가 배열 형태로 나옵니다. 배열의 각 자리에 0 3 3 3 3 3 이런 식으로 계산 결과가 저장되죠. 이 함수는 다음과 같이 실행하면 됩니다.
result = get_double_array(13, 17)
위와 같이 실행하면, 13을 17로 나눈 결과를 배열 형태로 돌려 줍니다. 그런데 이 배열을 입력으로 사용해서, 순환 마디를 찾는 문제를 풀어보려고 하니 생각보다 문제가 간단치 않더군요. 결국 찾아낸 해법은 다음과 같습니다. 굉장히 brute-force한 알고리즘이죠. (따지고 보면 별로 그렇지도 않습니다만.) 이 알고리즘은 "완전한" 해법은 아닙니다. 정말로 제대로 된 알고리즘이 필요하다면, KMP(Knuth-Morris-Pratt) 알고리즘의 패턴 전처리 알고리즘을 해보는 것이 좋겠죠. 그냥, "이렇게 생각해 볼 수도 있겠다" 정도로 보아주시기 바랍니다.
def decide_if_repetition(anArray)
(1).upto(anArray.length-2) do |i| # 시작 위치
puts anArray[i]
(1).upto(anArray.length/2) do |w| # 간격
cnt = 0
j = 0
while ( i + j + w < anArray.length )
if anArray[i+j] == anArray[i+j+w]
cnt = cnt + 1
else
cnt = 0
break;
end
j = j + w
end
if ( cnt > 1 )
return i, w
end
w = w + 1
end
end
return 0, 0
end
알고리즘의 개요는 간단합니다. 일단 순환 마디를 찾기 위한 검사 시작 지점을 정합니다. i가 그 검사 시작 지점의 위치입니다. 1씩 증가합니다. 그리고 검사 시작 지점의 위치가 정해지면, 그 위치에서부터 간격(w)을 달리해서 그 위치에 있는 모든 원소들을 비교합니다. 그러니까 다음과 같은 비교를 하는 거죠.
i가 1일때:
w == 1 : anArray[1] == anArray[2] == anArray[3] == ...
w == 2 : anArray[1] == anArray[3] == anArray[5] == ...
w == 3 : anArray[1] == anArray[4] == anArray[7] == ...
...
이런 식으로 비교하다가, 비교가 성공하는 w를 만나면, i와 w를 반환합니다. 그 즉시 나머지 비교는 중단해 버리는 거죠. 그러면 순환 마디의 시작 부분과 그 너비를 구할 수 있습니다.
이 알고리즘은 간단합니다만 O(n^{3})의 복잡도를 가진다는 단점이 있습니다. 장점이라면 순환 마디에 들어 있는 모든 w개의 문자를 비교하지 않는다는 점입니다. 이 장점은 또다른 단점이 될 수도 있습니다. 예를 들어서 보자면, 이 알고리즘은 다음과 같은 순환소수가 있을 경우 w의 크기를 잘못 계산해 낼 수 있습니다.
0.1213141512131415...
실제로는 w 크기가 8인데, 2로 계산해 내는 오류를 범할 수 있다는 것이죠. (물론 저런 순환소수가 있다는 가정 하에서.) 그런 단점을 눈감아 준다면, 이 알고리즘은 그럭저럭 쓸만하다고 할 수도 있겠습니다.
그런데 이 알고리즘을 튜닝해서 성능을 개선한다면, 과연 어디에 집중해야 할까요? O(n^{3})에 달하는 계산 복잡도를 낮추는 데 집중해야 할까요? 아니면 이 알고리즘을 만들때 두었던 가정들을 좀 더 완화해야할까요?
위의 알고리즘의 경우 "순환 마디가 어디서부터 어디까지인지를 찾는다"는 목적을 포기하면, 좀 더 복잡도가 낮으면서도 빠른 알고리즘을 얻을 수도 있습니다. 그냥 '순환소수일 가능성이 있는지 없는지, 그리고 순환소수일 것 같다면 그 순환 마디의 길이가 얼마정도인지 알고싶다'고 한다면, 복잡도를 O(n^{2})까지 낮출 수도 있다는 것이죠.
그 전체 코드를 보시면...
# constants
LIMIT = 100def get_double_array(dev,todev)
p = dev
q = todev
m = 0
result = []
(0 .. LIMIT-1).each do |i|
result[i] = (p / q)
break if (m = p % q) == 0
p = m * 10
end
return result
enddef decide_if_repetition(anArray)
i = 1
while (i < anArray.length / 2)
j = 0
cnt = 0
while ( j + i < anArray.length )
if anArray[j] == anArray[j+i]
cnt = cnt + 1
else
cnt = 0
end
j = j + i
end
if cnt > 1
return i
end
i = i + 1
end
return 0
endresult = get_double_array(13,1700000)
if result.length < LIMIT
puts "유한소수."
exit 0
enddecision = decide_if_repetition( result )
if decision == 0
puts "순환소수인지 판정할 수 없음."
else
puts "순환소수 후보: 윈도우 사이즈는 " + decision.to_s
end
뭔가 더 개선할 여지도 있겠습니다만, 제가 생각할 수 있는 것은 이정도로군요. 사실 알고리즘의 '목표'를 포기하려면, 알고리즘이 적용되어야 하는 Context와, 그 Context가 주는 Assumption들이 그럴 수 있도록 허용을 해 주어야 합니다. 그러니, 결국 가장 중요한 것은 Fact인 셈이죠. 적용할 수 없다면, 위와 같은 튜닝은 공염불에 불과한 거니까요.
