최근에 중학생 한명에게 프로그래밍을 가르치고 있습니다. 저는 프로그래밍을 업으로 삼으면서도 이 일에 대한 확신이 부족해서 그런지 (능력이 없으니 당연하겠죠 -_-;;) 그 학생에게 프로그래밍에 관심을 가지는 것은 좋지만, 벌써부터 업으로 하겠다는 생각은 하지 말라고 충고했습니다. ㅋㅋ 존 카멕과 같은 걸출한 프로그래머는 중학생때 이미 자신의 인생의 방향을 결정해서 성공하기도 했는데 말이죠. 아무튼 그건 그렇고.

이 학생을 가르치면서, 컴퓨터의 구조와 컴퓨터 언어에 대해서 아무 것도 모르는 사람에게 프로그래밍 언어를 가르친다는 것이 얼마나 힘든 일인지 새삼 깨닫게 되더군요. 사실 저는 예전에 대학에서 컴퓨터 프로그래밍 언어를 계절학기 동안 가르쳤던 적도 있고, 비트 컴퓨터 교육센터에서는 한 3년간 일년에 한두번씩 C++을 강의하기도 했었습니다. 그래서 처음에는 쉬울 거라고 생각했죠. 그런데 아니더군요.

가르친지 한 석달이 넘었는데, 아직도 이 학생은 컴퓨터를 사용해서 문제를 해결하지 못하고 있습니다. 뭐, 뻔한 결론입니다만, 강사 탓이겠죠. 이 학생의 최초 희망은 컴퓨터 게임 프로그래머였는데, 날이 갈수록 그 희망으로부터 조금씩 멀어지고 있다는 것을 느낍니다. 사실 가장 큰 장애물은 이 학생이 컴퓨터 앞에 앉아 있을 시간이 없다는 거예요. 컴퓨터 앞에 앉아 있으면 부모님들이 학교 공부 안한다고 싫어하시거든요. (아무래도 이 아르바이트도 오래 못갈듯.. ㅋㅋ)

그래서 요즘은 이 학생에게 "중학교 수학을 Java로 푸는" 과제들을 내 주고 있습니다. 아무래도 학교 공부와 관련된 것을 하면, 이 학생이 시간을 할애하기가 좋을 것 같다는 계산에서죠. 최근에 풀어본 문제로는, "사람이 하는 나누기 계산 과정을 프로그램으로 흉내내기"같은 것이 있습니다. 1/3을 계산해서 double 형 변수에 저장하면 0.333333333334 이렇게 나오잖아요? 실제로는 순환소수(무한소수죠)인데, 표현력 한계상 중간에서 저렇게 짤리고 말죠. 이 '표현력 상의 한계'를 좀 뛰어넘어 보자는 것이 과제의 목적이었습니다. 최소한 0.3333333333333333333333333333333333333333333333333333.... 이런 식으로 출력될 수 있도록 하자는 것이었죠.
이 문제는 간단히 풀 수 있었습니다. Ruby로 풀어보자면 이렇습니다

#constant
LIMIT = 1000

def 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 = 100

def 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

def 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
end

result = get_double_array(13,1700000)

if result.length < LIMIT
  puts "유한소수."
  exit 0
end

decision = decide_if_repetition( result )

if decision == 0
  puts "순환소수인지 판정할 수 없음."
else
  puts "순환소수 후보: 윈도우 사이즈는 " + decision.to_s
end

뭔가 더 개선할 여지도 있겠습니다만, 제가 생각할 수 있는 것은 이정도로군요. 사실 알고리즘의 '목표'를 포기하려면, 알고리즘이 적용되어야 하는 Context와, 그 Context가 주는 Assumption들이 그럴 수 있도록 허용을 해 주어야 합니다. 그러니, 결국 가장 중요한 것은 Fact인 셈이죠. 적용할 수 없다면, 위와 같은 튜닝은 공염불에 불과한 거니까요.


신고
Posted by 이병준

소중한 의견, 감사합니다. ^^

  1. mskyt

    1. 유한한 길이의 배열에서 순환마디를 구한다는 것은 문제가 명확하지 않습니다. 그저 배열 끝부분에 아무리 짦은 길이라도 두번이상 패턴이 반복된다면 순환마디로 볼 수 있을까요? 극단적인 가정으로, 배열 마지막이 x.xxxxx....xx33 과 같이 같은 숫자로 끝났다면, 정의상 3이 순환마디가 되어야 하는 건 아닐겁니다. (물론 '순환소수의 후보'라고 표현하셔서 할말은 없습니다)
    일단, 글쓴님께서 정의하신 대로 하고 넘어갑시다.


    2. O( {n}^2 )의 알고리즘에서 안쪽 루프에서 'j = j+i' 으로 하면 안될것 같습니다. 다시한번 최악의 예를 들어서, 소수가 0.xxxx3xxx3xxx3xxx3xxx3xxx3... (각각의 x는 임의의 수) 라고 한다면, 본 알고리즘은 순환마디의 길이가 4라고 판별해버릴겁니다. (사실 소수 초반부터 LIMIT 자리까지 이러한 우연적인 반복이 일어나기는 쉽지 않을 것입니다. 하지만 LIMIT 끝쪽에서 우연히 두 숫자가 일치하기는 매우 쉽죠)

    2. 구현하신 두번째 알고리즘은 O( NlogN )의 복잡도를 같습니다. 연산량은 sum( length / i ) for i=1~length/2 인데요. 아리스토텔레스의 체의 복잡도를 계산하는 것과 마찬가지 방식으로 이것은 O(NlogN)의 복잡도를 갖습니다

    3. 'j = j+i' 대신 'j = j+1' 로 하시면 O( {n}^2 )의 정확히 순환마디의 길이를 찾아내는 알고리즘이 됩니다. 순환마디의 길이를 알면 첫번째 알고리즘처럼 brute-force한 방식으로, 또는 두번째 알고리즘에서 3~4줄의 코드를 추가해서 순환마디의 위치도 알 수 있습니다. 그리고 이러한 방법은 KMP 알고리즘과 작동방식이 거의 일치합니다.


    4. 지금까지는 사실 '유한소수'와 '무한소수'의 특성은 전혀 고려하지 않고, 유한한 길이의 배열내에서 반복되는 패턴이 있는지 검사하는 것이었습니다. 기본적인 수학적 성질을 조금만 추가하시면 더 정확하고 빠른 프로그램을 만들 수 있습니다.

    - 처음부터 배열을 뒤집어서 순환마디를 판별하면 좋을것입니다. 배열내에서 순환마디를 이룬다면 마지막 숫자는 만드시 순환마디에 포함되기 때문이죠. 마지막 숫자가 순환마디를 이루지 않는다면 바로 포기해도 좋습니다. 모든 길이에 대해 연산을 수행한다면, 이런 알고리즘은 O( N )의 복잡도를 갖습니다.

    - 아예 통째로 뜯어고쳐서, 나눗셈을 하는 동시 순환마디를 판별할 수 있습니다. 순환소수의 나눗셈을 손으로 직접하다보면 아시겠지만, 나머지(p%q)가 한번이라도 반복되면 순환하게 됩니다. 즉 get_double_array함수의 루프안에서, m에 같은 숫자가 두번째 출현한다면, 그 이전 상황과 정확히 똑같기 때문에 순환될 것이라는 것을 알 수 있습니다. (이논리를 이용하면 순환마디의 최대길이가 제수(변수 todev)의 크기임을 유추할 수 있습니다) 따라서 지금까지 나왔던 m들과 겹치는지 확인해서, 순환하는지 확인할 수 있습니다. 중복검사 방법으로는 해쉬함수를 사용하거나, 빠르게 sorting되는 자료구조(AVL-tree, RB-tree)를 사용하면 좋을 것 같습니다.


    * 변수명 dev와 todev는 디바이드divide에서 따오신것 같은데, div가 맞겠죠

    * 쓰다보니 심한 태클이 된것 같은데요, 너그러이 용서해주세요. 잠깐 알고리즘에 발을 담갔던 사람으로써 태클드렸습니다

    2009.06.16 20:02 신고 [ ADDR : EDIT/ DEL : REPLY ]
    • 태클이라뇨? 지적 감사합니다. 다 구구절절 옳으신 말씀입니다. 코드까지 보여주셨으면 더 좋았을 것을... 앞으로도 종종 훈계좀 해주세요. ^^ 제가 알고리즘쪽으론 아는게 시원찮아서 아마 마땅찮으셨을겁니다. 더 배워야 하는데.. 쩝~ 어쨌든 블로그가 이런 거 하자고 있는 데니까 부담 안가지셔도 됩니다. :-)

      2009.06.17 12:12 신고 [ ADDR : EDIT/ DEL ]
  2. 7TB

    취미삼아 checkio 문제를 끄적끄적 푸는데, 똑같은 문제가 있네요.
    http://www.checkio.org/mission/repeating-decimals/

    입출력 예
    convert(1, 3) == "0.(3)"
    convert(5, 3) == "1.(6)"
    convert(3, 8) == "0.375"
    convert(7, 11) == "0.(63)"
    convert(29, 12) == "2.41(6)"
    convert(11, 7) == "1.(571428)"
    convert(0, 117) == "0."
    convert(4, 2) == "2."

    이건 제 답안입니다.
    def convert(numerator, denominator):

    --->repeat_point = 0
    --->history = []
    --->demical = ""

    --->demical += str(int(numerator/denominator))
    --->demical += '.'
    --->numerator = (numerator%denominator)*10

    --->while numerator != 0 :
    --->--->demical += str(int(numerator/denominator))
    --->--->history.append(numerator)
    --->--->numerator = (numerator%denominator)*10
    --->--->if numerator in history :
    --->--->--->repeat_point = len(history) - history.index(numerator)
    --->--->--->break

    --->if repeat_point == 0 :
    --->--->return demical

    --->return demical[:-repeat_point] + '(' + demical[-repeat_point:] +')'

    2015.02.25 17:00 신고 [ ADDR : EDIT/ DEL : REPLY ]

제 9장은, 코드 튜닝에 관한 부분입니다. 이 책에 실린 내용은 전반적으로 까다롭습니다만, (물론 제가 머리가 나빠서 그럴지도 모릅니다) 특히 9장에 실린 내용은 더 까다로운 편입니다. 하지만 그 까다로움을 넘어서면, 이거다 싶어서 무릎을 치게 되는 일이 생기죠.

9장을 보면 이진 탐색이라는 문제에 대한 초기 해법을 어떻게 가다듬어 보다 좋은 성능을 내는 알고리즘으로 변모시킬 수 있는 지가 나옵니다. 저정도면 나도 할 수 있겠다 싶은 대목도 있습니다만, 그렇지 않은 부분도 많습니다. 아래의 알고리즘을 한 번 보죠. 179페이지부터 180페이지에 걸쳐 나오는 알고리즘입니다. 이진 탐색을 할 대상 수 집합의 크기가 1000이라는 점을 이용하는 코드입니다. 같은 수가 여러 개 있는 상황을 허용하고, 그 중 첫 번째 수의 위치를 찾는 것을 목표로 하고 있기 때문에, 흔히 보던 이진 탐색 알고리즘과는 좀 다를 수 있습니다.

i = 512
l = -1

if x[511] < t
    l = 1000 - 512
while i != 1
    /* invariant : x[l] < t && x[l+i] >= t && i = 2^j */
   
nexti = i / 2
    if x[l+nexti] < t
        l = l + nexti
        i = nexti
    else
        i = nexti
/* assert i == 1 && x[l] < t && x[l+i] >= t */
p = l + 1
if p > 1000 || x[p] != t
    p = -1

여기서 저자는 빨간 색으로 표시된 부분의 코드를 똑똑한 컴파일러라면 어떻게 최적화할지를 묻고, 그에 대한 답을 보여줍니다. (컴파일러가 최적화하는 순서를 보이지는 않습니다.) 사람이라면 어떻게 최적화할까요?

(1)
nexti = i / 2
if [l + nexti] < t
    l = l + nexti
i = nexti

i = nexti를 하는 부분은 if 블럭과 else 블럭에 공통적이니까 굳이 if-else 블럭 안에 둘 필요는 없습니다. 밖으로 끄집어 내면 되죠.

(2)
i = i / 2
if [l + i] < t
    l = l + i

if 블럭 안에서 nexti에 대해 side-effect를 발생시키는 부분이 없으므로, i에 nexti를 대입하는 부분은 if 문 위쪽으로 끌어올릴 수 있습니다.

이 정도는 뭐 나도 쉽게 할 수 있겠다, 싶습니다만, 막상 코드를 작성하다 보면 그렇지 않은 경우도 많습니다. 알고리즘을 차근차근 뜯어볼 시간적 여유가 주어지지 않는 경우도 많거든요. 이 책이 갖는 강점은, 독자에게 그런 류의 사고를 할 수 있는 드문 기회를 제공한다는 점입니다.

이 코드의 마지막 버전은 더 재미있습니다. 저자는 "심장이 약한 사람은 보지 말 것"을 권하고 있기도 합니다. 이 코드는, 루프 선체를 펼쳐서 루프를 도는 데 드는 오버헤드와, i를 2로 나누는 연산을 제거해버렸습니다.

l = -1
if ( x[511] < t ) l = 1000 - 512
    /* assert x[l] < t && x[l+512] >= t */
if ( x[l+256] < t ) l += 256
    /* assert x[l] < t && x[l+512] >= t */
if ( x[l+128] < t ) l += 128
if ( x[l+64] < t ) l += 64
if ( x[l+32] < t ) l += 32
if ( x[l+16] < t ) l += 16
if ( x[l+8] < t ) l += 8
if ( x[l+4] < t ) l += 4
if ( x[l+2] < t ) l += 2
    /* assert x[l] < t && x[l+2] >= t */
if ( x[l+1] < t ) l += 1
    /* assert x[l] < t && x[l+1] >= t */

p = l + 1
if p > 1000 || x[p] != t
    p = -1

이런 코드 튜닝은, 코드 튜닝이 어떤 일을 할 수 있는지를 보여주는 '극한의' 사례라고 할 만 합니다. 이렇게 튜닝된 코드는 원래 버전의 이진 탐색에 비해 36% 향상된 속도를 보여준다고 합니다.

이 정도로 코드를 다듬는 것이 항상 가능하지는 않고, 그럴 필요가 없을 때도 있습니다만, 속도가 문제가 되는 상황은 생각보다 자주 발생합니다. 그럴 때에는 가능한 옵션을 찾아 이리저리 프로파일링을 해 보게 마련인데요. 프로파일링을 하면 병목구간을 찾아낼 수는 있는데, 발견된 병목구간을 어떻게 해소할 지는 분명하지 않은 경우가 많습니다. 병목구간을 해소하는 방법으로 많은 경우 구조적인 해결방법(architectural solution)을 최우선으로 고려하게 되는데, 그런 해결 방법은 의외로 높은 비용을 요구할 때도 있죠.

그러므로 정말 속도가 문제가 된다면, 이런 해법이라도 모색해보는 편이 좋겠습니다. 물론, 이런 코드 튜닝은 굉장히 많은 경험을 요구합니다.

가령, 이 9장의 8번 연습문제를 보면, 추가의 메모리를 사용해서 삼각함수 계산비용을 낮추는 사례가 소개되어 있습니다. 이 사례는 "본 프로그램은, 5도 배수의 인자에 대해서만 삼각함수 계산을 요구한다"는 단순한 사실에서 출발해서, "테이블 형태의 메모리 테이블을 구성하고, 그 테이블을 조회하는 함수"를 구현하여, 삼각함수 계산 비용을 낮추었습니다. 즉, "알고리즘의 실행 환경"을 면밀히 분석한 다음, "그 실행 환경이 갖는 특이성"을 적극적으로 이용하여 성능을 개선한 것입니다. 이런 일이 가능하려면, 프로파일링을 공격적으로 하는 것 뿐 아니라, 사실(fact)을 적극적으로 공략하는 마음가짐이 중요합니다.

수학적인 사고도 요구될 때가 있습니다. 가령 연습문제 12의 경우,

y_{0} = a_{n}
y_{1} = x * a_{n} + a_{n-1}
        = x * y_{0} + a_{n-1}
...
y_{m} = x * y_{m-1} + a_{n-m}

을 유도할 수 있으면 2n이 아닌 n짜리 알고리즘을 만들어 실행시간을 반으로 줄일 수 있습니다. 대부분의 프로그래머는 이정도는 하실 수 있겠습니다만, 저처럼 머리가 나빠서 앉은 자리에서 생각을 해 낼 수가 없다면 실행시간의 반을 까먹는 일이 생기게 되겠죠.

그러니 결국 좋은 알고리즘을 위해서는 Fact에서 출발해 Context에 대한 Assumption을 만들고, 거기에 Experience를 섞어서 Solution을 찾아야 하는 셈입니다. 약자를 다 모으면 FACES로군요. ㅋㅋ 세상 문제들의 다양한 측면들(Faces)을 두루 볼 수 있어야 그 문제에 대한 좋은 알고리즘이 나온다는 뻔한 결론이랄까요.

신고
Posted by 이병준

소중한 의견, 감사합니다. ^^