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

이 학생을 가르치면서, 컴퓨터의 구조와 컴퓨터 언어에 대해서 아무 것도 모르는 사람에게 프로그래밍 언어를 가르친다는 것이 얼마나 힘든 일인지 새삼 깨닫게 되더군요. 사실 저는 예전에 대학에서 컴퓨터 프로그래밍 언어를 계절학기 동안 가르쳤던 적도 있고, 비트 컴퓨터 교육센터에서는 한 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 ]

생각하는 프로그래밍(Programming Pearls)의 8장을 보면, 최대 부분합을 구하는 알고리즘을 고안하는 절차가 기술되어 있습니다. 이 책의 다른 부분도 멋집니다만, 저는 특히 이 8장이 굉장히 멋지다고 생각합니다. (아직도 이해가 잘 안되는 부분이 있긴 하지만 말입니다.)

Network Algorithmics라는 책이 있습니다. 이 책은 인터넷을 아우르는 네트워크 장비들이 오늘날같이 발전되어 오기까지 수많은 연구자들이 알고리즘을 어떤 식으로 개선시켜왔는지를 보여주는 멋진 책입니다. 그런 면에서 보면, Programming Pearls와 지향하는 바가 같다고 볼 수도 있겠습니다.

이런 책을 읽다보면 느끼는 것입니다만, 알고리즘의 개선은 알고리즘이 실제로 적용될 데이터와, 알고리즘이 돌아갈 시스템에 대한 깊은 이해가 없이는 성취하기 힘든 것이 아닌가 하는 생각이 듭니다. 그런 것들을 이해한 뒤에야, 결국 "문제 그 자체"를 제대로 이해했다고 말할 수 있다는 것이죠. 결국 우리가 알고리즘을 통해 풀어야 하는 문제는, 알고리즘과 데이터, 그리고 시스템에 걸쳐 퍼져 있음을 이해해야 한다는 뜻이 되겠군요.

각설하고.

이 책의 8장 4절을 보면 O(n)의 복잡도를 갖는 scanning 알고리즘이 나와 있습니다. 이 부분을 보기 전에 저도 같은 문제를 (아무 생각없이) Ruby로 한 번 풀어봤습니다. 제가 알고리즘을 구현할 때 착안한 점은 다음과 같습니다.

부분합이 음수가 되면, 그 때 까지 계산한 부분합은 버려도 된다
그 아이디어를 대락 십분 정도 걸려서 구현하고, 정확성을 검증한 다음에, 책에 나온 알고리즘과 성능 비교를 한 번 해봤습니다. 소스 코드는 다음과 같습니다. 원래 책에 나온 대로 구현한 알고리즘이 first_version이고, 제가 구현한 형태의 알고리즘이 second_version입니다.

def make_array(size)
  array = []
  size.times do
    array << rand(10000) - 5000
  end
  return array
end

def max(l, r)
  return (l>r)?l:r
end

def first_version(array)
  maxsofar = 0
  maxendinghere = 0
  for i in (0..array.length-1)
    maxendinghere = max(maxendinghere + array[i], 0)
    maxsofar = max(maxsofar, maxendinghere)
  end
  return maxsofar
end

def second_version(array)
  sum = 0
  left = 0
 
  max_sum = 0
  max_left = 0
  max_right = 0
 
  for i in 0 .. array.length - 1
    sum  = sum + array[i]
    if ( sum < 0 )
      sum = 0
      left = i+1
    elsif ( sum > max_sum )
      max_sum = sum
      max_left = left
      max_right = i
    end
  end

  return array.length, max_sum, max_left, max_right
end

def print_values(*value_array)
  (0..value_array.length-1).step(1) do |i|
    print value_array[i]
    if ( i != value_array.length-1 )
      print ", "
    end
  end
  puts ""
end

#
# main starts
#

(10000..150000).step(10000) do |i|
 
  test_array = make_array(i);
 
  start_time = Time.now.to_i
  max = first_version(test_array)
  end_time = Time.now.to_i
 
  print_values("f", test_array.length, max, (end_time - start_time))
 
  start_time = Time.now.to_i
  len, max, left, right = second_version(test_array)
  end_time = Time.now.to_i
 
  print_values("s", len, max, left, right, (end_time - start_time))
end

성능 비교 결과는 다음과 같습니다. 원래 알고리즘의 실행 결과는 그 줄 앞에 "f"가 붙어 출력되고, 제가 만든 알고리즘의 실행 결과는 그 줄 앞에 "s"가 붙어 출력되므로 확인하기 어렵지는 않습니다.

f, 10000, 671773, 0
s, 10000, 671773, 884, 6580, 0
f, 20000, 572515, 0
s, 20000, 572515, 1839, 13202, 0
f, 30000, 540911, 0
s, 30000, 540911, 9561, 25188, 0
f, 40000, 1074401, 0
s, 40000, 1074401, 11395, 35425, 0
f, 50000, 1138364, 0
s, 50000, 1138364, 27126, 34215, 0
f, 60000, 539056, 1
s, 60000, 539056, 19715, 29205, 0
f, 70000, 560118, 0
s, 70000, 560118, 59001, 69944, 0
f, 80000, 1785579, 0
s, 80000, 1785579, 11987, 79133, 0
f, 90000, 961688, 1
s, 90000, 961688, 57476, 82005, 0
f, 100000, 1058398, 0
s, 100000, 1058398, 38817, 73416, 0
f, 110000, 1226686, 1
s, 110000, 1226686, 62664, 107244, 0
f, 120000, 1368168, 0
s, 120000, 1368168, 77202, 119980, 0
f, 130000, 1585253, 0
s, 130000, 1585253, 30075, 100395, 0
f, 140000, 1203882, 1
s, 140000, 1203882, 43789, 99896, 0
f, 150000, 653564, 0
s, 150000, 653564, 16504, 41747, 1

그 결과, 원래 알고리즘보다 이해하기도 훨씬 낫고 (정말로?) 원래 알고리즘보다 더 많은 정보를 제공하는 알고리즘을 만들 수 있었습니다. 조금 깊이 들여다보면 알수 있는 일입니다만, 제가 구현한 알고리즘은 원래 알고리즘과 똑같은 알고리즘입니다. 소스 코드의 양만 많을 뿐이죠.

사실 제가 만든 알고리즘은 원래 이중 루프를 사용하고 있었습니다(부분합이 음수가 되면 버리는 로직이 있어서 이중 루프를 쓰더라도 선형적으로 수행될 것으로 기대했었습니다. 하지만 그렇게 하니까 최악 수행 시간이 굉장히 나빠지는 문제가 있더군요). 그런데 오늘 이 글을 적으면서 안쪽 루프가 필요 없다는 사실을 깨달았고, 결국 코드를 고쳤죠.

이 글을 적기 위해 샘플 프로그램을 만들면서 느낀 것이지만, 역시 가장 중요한 것은 알고리즘을 어떻게 만들어 나갈 것이냐 하는 문제입니다. 원래 제가 만들었던 second_version 함수의 성능은 오늘 뜯어고친 버전에 비해 그 성능이 굉장히 좋지 못했습니다. 그런 알고리즘이 누군가에게 팔릴 소프트웨어의 핵심적인 부분에 들어가 있었다면, 누구도 그 소프트웨어를 사지 않았을 것입니다.

그리고 한편으로는 이런 생각도 듭니다. 책에 나오는 O(n) 알고리즘은 사실 이해하기가 여간 어려운 것이 아닙니다. 하지만 그 알고리즘을 조금 다른 각도로 바꿔서 생각해 보면, 결국 제가 마지막으로 구현한 알고리즘과 동일한 일을 하는 알고리즘임을 깨달을 수 있습니다. 제가 알고리즘을 만들기 시작하면서 착안했던 지점과 책의 저자가 착안했던 지점은 조금 다릅니다만, 결국 알고리즘을 다듬고 다듬고 다듬어 얻은 결과물은 똑같아진 것이죠.

결국, 알고리즘을 만드는 데 있어서 중요한 것은 "문제를 끊임없이 개선해 나가려는 노력"이라는 소리가 되겠군요. 그런데 실무에서 프로그래밍을 하다 보면, 이런 사소한 진리를 망각하게 되는 일이 아주 빈번히 벌어집니다. 적당히 돌아가게 만들어 둔 알고리즘을 프로그램 안에 넣어놓고 연동시험이 끝나는 순간 그에 대해 잊어버리는 것이죠. (물론 그런 부분이 존재한다는 사실은 나중에 프로파일링 과정에서 드러나기는 하겠습니다만...)

위의 예제를 구현하면서, 새삼 제가 예전에 저질렀던 수많은 게으름의 흔적들이 떠올라 부끄러워졌습니다. 앞으로는 좀 더 열심히 해야겠어요. :-)




신고
Posted by 이병준

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

  1. 아.. 저두 스캐닝 알고리즘을 한참 동안 봤습니다. ^^

    2008.10.09 14:46 신고 [ ADDR : EDIT/ DEL : REPLY ]