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

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

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

생각하는 프로그래밍(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 ]

Books by Example2008.01.03 13:26
요즘들어 SW 분야의 명저들을 찾아 읽어보는 데 굉장히 많은 시간을 할애하고 있습니다. 최근에 보고 있는 책들 중 탁월하다고 생각하는 것으로는 "실용주의 프로그래머(The Pragmatic Programmers)", "생각하는 프로그래밍(Programming Pearls)", 그리고 "컴퓨터 프로그램의 구조와 해석(SICP)" 등이 있습니다.

보통 컴퓨터 분야의 책을 읽을 때, 많은 사람들이 연습문제는 건너뛰고 잘 풀어보질 않습니다. 하지만 저는 이 연습문제들에 본문에서 얻을 수 있는 지식 + 알파가 녹아있다고 믿습니다. SW 분야의 명저가 된 책들에는 이런 연습문제들이 풍부하고, 굳이 연습문제가 아니더라도 많은 예제들이 포함되어 있습니다.

이런 문제들을 풀어보고 프로그램을 만들 떄 마다, 이 블로그에 올려보도록 하겠습니다. 단순히 정리한다는 목적도 있고, 저와 비슷한 고민을 하는 다른 사람들에게 유용한 정보를 제공하고자 하는 목적도 있고, 보다 많은 사람들을 이런 명저로 이끈다는 목적도 있습니다. 부디 제가 올리는 모든 문제들과 해설이, 그런 목적에 충실하기를 바랍니다.

현재까지 이와 관련하여 올려진 글들의 목록은 다음과 같습니다. 

"컴퓨터 프로그램의 구조와 해석(SICP)"


"생각하는 프로그래밍(Programming Pearls)"

이 목록은 이 주제에 대한 새로운 포스팅이 올라올 때 마다 업데이트됩니다.

신고
Posted by 이병준

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

  1. 저는 스터디 그룹에서 온라인으로 공부한 흔적은 남기기로 했기에
    연습문제를 블로그에 올리기로 했습니다.
    (아직 위키에 적응이 완료되지 않아서....OTL....)
    계속 좋은 글 부탁드립니다.^^

    2008.01.03 16:07 신고 [ ADDR : EDIT/ DEL : REPLY ]
  2. 지나가다 글 남깁니다.
    저는 운좋게도 학부때 관련 교재로 수업을 할 수 있었죠.
    좀 힘들긴 했지만 가장 인상적인 과목 중 하나였습니다.
    시간 나면 다시 한 번 보고 싶네요.
    연습문제 답 모아놓는 위키도 있으니 참고하세요.
    http://sicp.org.ua/sicp

    2008.01.03 23:50 신고 [ ADDR : EDIT/ DEL : REPLY ]

Books by Example/SICP2007.12.16 03:55

연습문제 1.21은 너무 쉬우므로 생략합니다. 1.22는 이미 있는 소스 코드를 가지고 search-for-primes라는 프로시저를 작성하는 것입니다. 기존의 프로시저를 아무 수정없이 사용할 수는 없는데, 그것은 start-prime-test가 검사 대상 수 n이 prime이 아닐 때 false를 반환하도록 구현되어 있지 않기 때문입니다. 그래서 아래의 소스 코드 붉은 색으로 표기된 부분에 false를 반환하는 코드를 넣었습니다. (저것말고 더 쉬운 방법이 있을텐데 지금으로선 잘 모르겠네요. ㅋ)

아 그리고, PLT-scheme은 SICP 책에 나오는 runtime이라는 함수를 제공하지 않습니다. 대신 current-seconds나 current-milliseconds같은 함수들을 제공합니다. (language를 PLT 아래에 있는 것 중 하나로 선택하면 사용할 수 있습니다.) 그래서 그 함수들을 사용하도록 코드를 고쳤습니다. (아래에 녹색 표시된 부분)

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (square x) (* x x))

(define (divides? a b)
  (= (remainder b a) 0))

(define (prime? n) (= (smallest-divisor n) n))

(define (timed-prime-test n)
  (start-prime-test n (current-milliseconds)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime n (- (current-milliseconds) start-time))
      (= 1 0)))

(define (report-prime n elapsed-time)
  (newline)
  (display n)
  (display " is prime and ")
  (display elapsed-time)
  (display " milli-seconds have passed"))

(define (search-for-primes start-from count)
  (if (> count 0)
      (if (even? start-from)
          (search-for-primes (+ start-from 1) count)
          (if (timed-prime-test start-from)
              (search-for-primes (+ start-from 2) (- count 1))
              (search-for-primes (+ start-from 2) count)))))

(display (sqrt 10))
(search-for-primes 1000000000 3)
(newline)
(search-for-primes 10000000000 3)
(newline)
(search-for-primes 100000000000 3)
(newline)
(search-for-primes 1000000000000 3)

맨 마지막의 8줄은 실행 결과를 확인하기 위한 부분입니다. sqrt 10이 대략 3입니다. search-for-primes의 실행 결과는 탐색이 시작되는 수의 자릿수가 10이 증가할 때 마다 대략 3배씩 늘어납니다. (따라서, 책에서 '정말 그러한가?'하고 묻는 부분에 대한 답은 'yes'라고 할 수 있겠습니다.)

아이가 아파서 늦게까지 잠을 잘 수가 없었는데, 이제 열도 떨어지고 했으니 그만 자야겠습니다.


신고
Posted by 이병준

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

  1. runtime이 안되어 고생하였는데 먼저 해결책을 알려주셔서 고맙습니다.^^ㅜㅜ

    2008.01.17 15:20 신고 [ ADDR : EDIT/ DEL : REPLY ]

Books by Example/SICP2007.11.17 17:50

본문에 나오는 이야기입니다만, T(a,b): (a <- a + b, b <- a)라고 하고, T 규칙을 순차적으로 n번 적용한 것을 T^n이라고 하면, T^n(1,0)은 n번째 피보나치 수열이죠.

그런데 사실 이 규칙 T는

  T_{p,q}(a,b): (a <- bq + aq + ap, b <- bp + aq)

의 특별한 케이스(p=0, q=1)입니다.

여기까지를 알고 있을때, 규칙 T_{p,q}를 연속적으로 두 번 적용해 보면(T_{p,q}^2) 어떻게 되나요?

a <- (bp + aq)q + (bq+aq+ap)q + (bq+aq+ap)p
       = b(2pq+q^2) + a(2pq+q^2) + a(p^2+q^2)
b <- (bp+aq)p + (bq+aq+ap)q
       = b(p^2 + q^2) + a(2pq+q^2)

결국, p^2+q^2 = p', 2pq+q^2 = q'로 놓게되면

  a <- bq' + aq' + ap', b <- bp' + aq'

이 됩니다.

그렇다면 피보나치 수열을 계산하는데 필요한 인자를 a, b, p, q의 네 가지로 보았을 때, 이터레이션의 수를 반으로 줄이고 싶으면 그럴 때 마다 a, b, p, q를 a, b, p^2+q^2, 2pq+q^2로 바꾸면 되겠군요. 그렇게 할 수 없을 때에는 a, b, p, q를 bq+aq+ap, bp+aq, p, q로 바꾸면 되고요.

맨 마지막에는 이렇게 해서 만들어진 최종 4-tuple을 다시 (a, b, p, q)라고 했을 때 b를 반환하도록 하면 되겠습니다.

그렇다면 결국 책에 나온 Scheme 문제는 다음과 같이 채우면 되겠군요.

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
           ((even? count) (fib-iter a b (+ (* p p) (* q q)) (+ (* 2 p q) (* q q)) (/ count 2)))
           (else (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- count 1)))))

이 문제는 Scheme 식으로 생각하는 문제라기 보다는 수학 문제처럼 느껴진다는...


신고
Posted by 이병준

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

  1. 전 피보나치 수열을 로그 차수가 나오는 알고리즘이 있다는 점이 무척 신기했습니다.^^

    2008.01.14 11:31 신고 [ ADDR : EDIT/ DEL : REPLY ]

Books by Example/SICP2007.11.15 22:27
1.16번

연습문제 1.16은 b를 n번 곱하는 문제의 복잡도를 어떻게 n에서 log n 으로 (밑수는 2)로 낮출 수 있느냐 하는 문제입니다. b * b * b * b * ... 이렇게 하는 대신 b를 계속해서 제곱해 나가다가 (b --> b^2 --> b^4 --> ... ) 마지막에 n이 홀수냐 짝수냐에 따라서 그 결과에 b를 한 번 더 곱해주거나 아니면 그냥 놔두거나 하면 되겠죠.

굉장히 간단한 아이디어입니다만, 의외로 실무에서 프로그래밍을 하다 보면 이렇게 간단한 부분도 놓치게 되는 일이 많은 것 같습니다.

비슷한 종류의 사례로 strcat에 관한 것도 있는데, 이에 대해서는 "조엘 온 소프트웨어"라는 책에 보면 나옵니다. strcat이 보통 '널 문자'를 찾기 위해 포인터를 문자열 앞에서 뒤 방향으로 계속 검색해 나가는데, 그런 이유로 strcat을 여러번 적용하면 문자열을 여러 개 합칠 경우 그 계산 복잡도가 n^n으로 바뀌고 만다, 뭐 그런 이야기였습니다.

아무튼 이 문제의 Scheme 식 해답은 다음과 같습니다.

(define (fast-expt-iter b n)
  (define (fast-expt-iter-part b m c)
    (cond ((= c 0) m)
          ((even? c) (fast-expt-iter-part (* b b) m (/ c 2)))
          (else (fast-expt-iter-part b (* b m) (- c 1)))))


  (fast-expt-iter-part b 1 n))

(fast-expt-iter 2 32)

"되도는 알고리즘보다 반복하는 알고리즘을 짜는 것이 더 어렵다"고 해서 (사실 그렇습니다) 문제 풀기전에 좀 겁먹었습니다만, 문제 자체가 쉬워서 크게 어려울 것은 없었습니다.

1.17번, 1.18번

그러면 a * b를 그런 식으로 계산할 수도 있겠군요. a * b를 덧셈만으로 구현한다고 하면 a를 b 번 더해나가야 되겠습니다만, a를 2a, 4a, 이런 식으로 계속 두 배 해 나가는 식으로 하면 더 빨리 돌도록 구현할 수 있겠습니다. 원래는 17번은 재귀 프로세스, 18번은 반복 프로세스로 구현하는 것인데, 재귀 프로세스로 구현하는 것은 반복 프로세스로 구현하는 것에 비해 쉬으므로, 반복 프로세스로 구현하는 경우만 보였습니다.

(define (double x) (* 2 x))

(define (halve x) (/ x 2))

(define (mul a b)
  (define (f adder result count)
    (cond ((= count 0) result)
          ((even? count) (f (double adder) result (halve count)))
          (else (f adder (+ result adder) (- count 1)))))
  (f a 0 b))

(mul 3 7)

신고
Posted by 이병준

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

Books by Example/SICP2007.11.10 16:11

파스칼의 세모꼴(Pascal's Triangle) 문제는 널리 잘 알려진 문제입니다. 하지만 안타깝게도 이 책을 읽기 전에 저는 이 문제를 함수형 언어에서는 풀어본 적이 없습니다. 파스칼의 세모꼴 모양은 흔히 알려져 있는 대로, 다음과 같습니다.

http://www.mathsisfun.com/pascals-triangle.html

출처: http://www.mathsisfun.com/pascals-triangle.html


이 문제를 저는 이렇게 풀기로 했습니다. 우선 위에서 부터 아래쪽으로, 1부터 증가하는 번호를 매깁니다. 이것을 x라고 했습니다. 그리고 왼쪽에서 오른쪽으로 역시 1부터 증가하는 번호를 매깁니다. 이것을 y라고 합니다. 그렇다면 x와 y의 값에 따라서, 모든 수는 (x, y)의 유일한 좌표 값을 가집니다. 이 x, y 사이의 관계를 알 수 있으면 어떤 좌표에 있는 값이 무엇인지 알 수 있습니다.

(define (f x y)
  (if (or (= y 1) (= x y)) 1
      (+ (f (- x 1) (- y 1)) (f (- x 1) y))))


그 값을 알아내는 공식은 위와 같습니다. 이 공식을 만든 다음에, 이 공식을 사용해서 파스칼 삼각형을 화면에 출력하도록 했습니다. 안타깝게도 출력에 관한 사항을 어떻게 처리할 지는 그다지 배운 바가 없어서, 대충 출력하도록 만들었습니다. 적당히 잘 뜯어고치면, 이것보다는 더 나은 출력을 만들 수 있을 거라 믿습니다.

(define (pascal n)
  (define (pascal-iter x y)
    (cond ((and (= x n) (= y (+ n 1))) (display ""))
          ((= y (+ x 1)) (display "\n") (pascal-iter (+ x 1) 1))
          (else (display (f x y)) (display " ") (pascal-iter x (+ y 1)))))
  (pascal-iter 1 1))


이 코드를 다음과 같이 하여 실행합니다.

(pascal 5)

그러면 아래의 삼각형을 얻습니다. (5 보다 큰 수를 입력하면 출력이 영 볼썽 사납습니다 ㅋㅋ)

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1


그런데 문제를 풀고보니 화면 출력에 대한 내용까지를 풀 필요는 없고, 각 좌표의 수가 무엇인지를 알수만 있으면 되는 것 같습니다. (괜히 삽질했구나 하는 생각이 듭니다 -_-;;)

화면 출력에 관한 코드를 만들 때 곤란했던 부분은, 흔히 C++에서는 다음과 같이 표현되는 루프를 어떻게 만들 것이냐 하는 점이었습니다.

for ( int i = 1; i <= n; ++i ) {
    for ( int j = 1; j <= n; ++j ) {
        ...
    }
}


뭐 보시다시피 대충 해결했습니다. ^O^;;

신고
Posted by 이병준

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

  1. estel

    정보 감사합니다!

    2016.01.21 19:53 신고 [ ADDR : EDIT/ DEL : REPLY ]

Books by Example/SICP2007.11.10 09:50

이 문제는 되도는 프로시저를 사용해 되도는 프로세스와 반복 프로세스를 구현해 보는 문제입니다. 되도는 프로세스는 흔히 "재귀적 프로세스"라고 부르는 것이고, 반복 프로세스는 "iterative process"입니다. (프로시저와 프로세스는 다른 개념인데, 프로시저는 코드라고 생각하면 되고, 프로세스는 그 코드에 의해 만들어지는 실행 궤적이라고 생각하면 됩니다. 따라서 프로시저는 재귀적으로 구현되더라도, 그 실행 궤적 자체는 반복적이 되는 일이 Scheme같은 언어에서는 발생할 수 있습니다. C에서라면 좀 곤란하지만요.)

C와 같은 언어에서 전자는 흔히 '함수의 재귀적 호출'에 의해 구현되고 반복 프로세스는 for나 while과 같은 별도의 문법에 의해 구현됩니다만, lisp는 for와 같은 문법을 지원하지 않기 때문에 재귀적 프로세스나 반복 프로세스나 전부 재귀적인 프로시저에 의해 구현해야 합니다. 처음에는 이것이 이해가 잘 되지 않을 수 있습니다. 책에서는 재귀적 프로세스와 반복 프로세스의 차이를 다음과 같이 언급하고 있습니다.

반복하는 프로세스에서는 프로그램 변수가 프로세스 단계마다 어떤 상태에 있는지 정확하게 나타내기 때문에, 계산을 잠시 멈추더라도 각각의 변수의 값만 알면 실행기가 곧바로 계산을 이어갈 수 있다. 하지만 되도는 프로세스는 그렇지 않다. 프로세스 안에 상태변수도 없을 뿐더러, 뒤로 미뤄 둔 연산의 끈을 이어가면서 '어디까지 계산했는지' 알아내려면, 실행기 속에 숨은 정보가 더 있어야 한다. 끈이 길 수록 그런 정보는 더 많아진다.



1.11번 문제는 함수 f(n) = (n-1) + 2f(n-2) + 3f(n-3) (n < 3일때는 f(n) = n)을 재귀적 프로세스와 반복 프로세스 두 가지 다른 버전으로 구현해 보는 것입니다. 통상 재귀적 프로세스는 하향적으로 문제 풀이가 전개되는 반면, 반복 프로세스는 상향적으로 문제 풀이가 전개됩니다. 전자는 좀 연역적인 성격이 있고, 후자는 좀 귀납적인 성격이 있다, 이렇게도 볼 수 있겠습니다. 그 점을 염두에 두면 문제풀이가 쉬워지는 것 같습니다.

답은 아래에 있습니다.

(define (func n)
  (if (< n 3) n
      (+ (- n 1) (* 2 (func (- n 2))) (* 3 (func (- n 3))))))

(define (func-iter n)
  (define (func-iter-part a b c count)
    (if (= count n) (+ (- count 1) (* 2 b) (* 3 c))
        (func-iter-part (+ (- count 1) (* 2 b) (* 3 c)) a b (+ count 1))))
  (if (< n 3) n
      (func-iter-part 2 1 0 3)))

(func 8)

(func-iter 8)

이렇게 할 수도 있습니다.

(define (func-iter n)
  (define (func-iter-part a b c count)
    (if (= count (+ n 1)) a
        (func-iter-part (+ (- count 1) (* 2 b) (* 3 c)) a b (+ count 1))))
  (if (< n 3) n
      (func-iter-part 2 1 0 3)))


거의 같은데 루프를 한 번 더 도는 것만 다르죠. ㅋㅋ 그런데 이 문제에 대한 인터넷 해답을 보니, 인터넷에서의 해답이 제 답과 조금 다르군요. 왜 그런가 잠시 생각해봤는데... 책에 오타가 있습니다 ㅎㅎ

To English Readers: There's typo in the exercise 1.11 of korean version of SICP. So. ignore the above answer - the answer for the 'wrong' question. Correct answer is given below (only the iterative version of the answer. I didn't give the recursive version of the answer, because it's too easy).

오타가 있어도 문제가 안풀리는 건 아닙니다만, 아무튼 답은 조금 달라집니다. 원서에 실린 문제 공식은 f(n) = (n-1) + 2f(n-2) + 3f(n-3)이 아니라 f(n) = f(n-1) + 2f(n-2) + 3f(n-3) 입니다. (한글판에는 f가 빠졌습니다.) f가 있을 경우의 해답은 다음과 같습니다. 역시 반복 프로세스의 경우만 싣습니다. 재귀적 프로세스의 경우에는 답이 뻔해서...

(define (f-b n)
  (define (f-b-iter a b c count n)
    (if (= count n) a
        (f-b-iter (+ a b c) (* 2 a) (* 3 (/ b 2)) (+ 1 count) n)))
  (f-b-iter 2 2 0 2 n))




사용자 삽입 이미지


이제 조금 익숙해지긴 했습니다만, 그래도 어렵긴 어렵군요. ㅋㅋ

신고
Posted by 이병준

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

  1. 어쩐지 이상하다 했습니다.OTL....
    저는 n 파라메터를 따로 만들었는데, 앞에서 배운 블록구조 안에 숨겨서 변수를 그대로 쓸 수 있다는 것을 깜박했습니다.
    좋은 정보 고맙습니다.^^

    2008.01.04 10:54 신고 [ ADDR : EDIT/ DEL : REPLY ]

Books by Example/SICP2007.11.09 00:13
밤마다 한시간씩 SICP 문제를 풀어보고 있습니다. 오늘은 1.8을 풀어봤습니다. Scheme 언어에 익숙해지려면 아무래도 시간이 좀 많이 걸리겠군요. 문제 1.8은 이렇습니다.

세제곱근 cube root를 구하는 뉴튼 법은, x의 세제곱근에 가까운 값을 y라고 할 때 다음 식에 따라 y보다 더 가까운 값을 계산하는 것이다.

(x + y^2 + 2y) / 3

제곱근 프로시저처럼, 이 식을 써서 세 제곱근 프로시저를 짜보자.


글쎄 뭐 짜는 것 까지는 좋습니다. 다음과 같은 코드를 작성했습니다.

(define (cube_root x)
  (if (or (= x 0) (< x 0)) 0 (cube_root_iter 1.0 x)))

(define (cube_root_iter guess x)
  (if (good_enough? guess x) guess (cube_root_iter (improve guess x) x)))

(define (good_enough? guess x) (< (/ (abs (- (cube guess) x)) x) 0.01))

(define (cube x) (* x x x))

(define (improve y x) (+ (/ x (* 3 (* y y))) (/ (* 2 y) 3)))

(cube_root 5)


이 간단한 코드를 짜는 데만도 한시간이 걸렸습니다. 그런데 처음에는 이상하게 값이 잘 안나오고 무한루프에 빠지더군요. 의심가는 데가 있어서 google에게 물어봤는데, 아무래도 책(번역판)에 나온 뉴튼법 공식이 좀 잘못된 것 같습니다. 다음과 같이 되어야 할 것 같습니다. (책에 나온 수식의 첫 번째 +가 /로 바뀌면 됩니다.)

사용자 삽입 이미지

위의 코드에서 빨간색으로 표시된 부분이, google이 알려준 뉴튼법 공식에 따라 수정된 부분입니다. 이렇게 고치고 나니, 프로그램이 정상적인 결과를 내 놓았습니다.

이 오류가 한글판의 오류인지 아니면 원서의 오류인지 잘 모르겠어서 구글신에게 다시 물어봤습니다. 한글판의 오류입니다. -_-; 좋은 책입니다만, 40페이지를 넘어가기도 전에 오류를 하나 발견하고 나니 어쩐지 맥이 빠지는 기분입니다[각주:1].

이런 기분인거냐?

이런 기분인거냐?



아무튼, 매일 잠들기 전에 하나씩 풀어볼 문제가 생겼다는건 기분 좋은 일이로군요. 아 이제 선형 대수학 책도 봐야하는데... -_-
 

  1. 역자분들의 노고를 폄하하거나 할 의도가 없음을 밝혀둡니다. 어쨌든 좋은 책이고, 사람이란 실수를 하게 마련이니까요. [본문으로]
신고
Posted by 이병준

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

  1. Programming Pearls 를 다 보고 이 책을 보려고 작정하고 있습니다. 나중에 연습 문제 풀 때 여기 자주 와야 되겠네요. 전 이거 두권이면 올 겨울은 그냥 지나갈 듯 합니다. ㅎㅎ

    2007.11.09 10:29 신고 [ ADDR : EDIT/ DEL : REPLY ]
  2. 명백한 오타네요. ㅡㅡ;;
    사람의 일이라 피하기 힘들다지만... 이런 사항이 보고될 때마다 가슴이 두근두근 댑니다.
    또 다른 대형 사고는 없는지.... 얼마나 더 지나야 안심할 수 있을런지.... 휴~

    지적하신 사항은 오탈자 사이트에 반영해 놓겠습니다.

    2007.11.09 15:48 신고 [ ADDR : EDIT/ DEL : REPLY ]
  3. 어쩐지 제가 뉴튼법으로 구한 식과 책에 적혀있는 것이 다르다고 했습니다.OTL....

    2007.12.18 12:35 신고 [ ADDR : EDIT/ DEL : REPLY ]
  4. 저도 같은 일을 겪었어요. 어쩐지 값이 안 나와서 뒷장의 뉴튼 부분을 참고하니 풀리더라고요. :)

    2008.08.31 15:44 신고 [ ADDR : EDIT/ DEL : REPLY ]

Books by Example/SICP2007.11.06 00:38
예전같으면 거뜬히 풀었을것도 같은데 (정말?) 이제 답 근처까지 가는건 가능해도 정답을 맞추는게 잘 안되네요. 문제는 이렇습니다. 다음의 소스 코드를 보면 sqrt-iter를 정의하면서 if를 사용한 부분이 있는데, 이 if 대신 new-if (이 함수의 정의도 소스 코드에 포함되어 있습니다)를 사용하면 어떻게 되느냐는 겁니다.

new-if는 코드를 보면 알 수 있듯이, if가 하는 일을 흉내내는 '함수'이고, sqrt-iter는 sqrt 함수, 즉 제곱근을 구하는 함수를 구현하기 위해 내부적으로 사용된 함수입니다.

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x) x)))

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (square x)
  (* x x))

(define (sqrt x)
  (sqrt-iter 1.0 x))

(sqrt 2)  ==> 실행 결과로 1.4 어쩌구... 의 값을 내놓습니다.



답의 힌트는 윗 단락의 밑줄 그은 부분에 있습니다. new-if로 if가 하는 일을 대체할 수 있을 것 같지만, 문제가 그리 간단치 않습니다. Scheme 함수는 함수 body를 수행하기 전에, 인자들을 전부 evaluation합니다. 그러니 new-if의 세 인자도 new-if 수행 전에 전부 evaluation되어야 합니다.

따라서, 위의 코드에서 sqrt-iter 안에서 사용된 if를 new-if로 대체하게 되면, 그 세 번째 인자로 주어진 (sqrt-iter ...) 부분을 먼저 evaluation 해야하고, 그 결과로 재귀 호출이 발생하고, new-if가 다시 호출됩니다. 그 결과로 무한루프가 발생하고, 메모리 제한 조건을 적절히 설정해 두지 않았다면 Scheme 시스템이 뻗습니다.


아 진땀

아 역시 그런거였나?



그런데, 이 정도의 답도 빨리 못 내어 놓는 걸 보니 제 머리가 굳긴 굳은것 같군요. -_-; 앞으로 연습문제를 좀 충실히 풀어봐야겠습니다. 굳은 머리를 풀려면...


신고
Posted by 이병준

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

  1. 전 처음에 무한반복을 예상했으나
    코드가 제대로 실행되는 것을 보고 당황했습니다.
    알고보니 기존의 sqrt-iter 프로시저에 if 대신 new-if로 바꾸지 않았더군요.OTL....
    그것도 모르고 '세상 참 신기하네..'라며 감탄하고 있었다니..OTL....

    sqrt-iter 프로시저에서 else-clause에 있는 sqrt-iter이 재호출되기 때문이 맞죠?
    메모리 제한을 걸지 않고 별 생각없이 구경하고 있다가 재부팅할 뻔했습니다.OTL.....

    2007.12.18 10:39 신고 [ ADDR : EDIT/ DEL : REPLY ]
  2. 아아 이런 .... OTL

    sqrt 를 정의 하지도 않고 빌트인 sqrt 를 써서 .....

    "이게 안되야하는데 왜 될까?" 하고 삽질했습니다 ㅋ

    2007.12.26 06:27 신고 [ ADDR : EDIT/ DEL : REPLY ]
  3. 디버깅 중에 good-enough?의 리턴이 참이 되는되도 guess가 아닌
    sqrt-iter로 계속 넘어가게 되어서 생각중이었는데 답은 함수의 동작에
    있었군요....ㅡㅡㅋ Scheme을 조금 더 공부해야 겠네요...^^

    2008.02.01 00:43 신고 [ ADDR : EDIT/ DEL : REPLY ]
  4. 낭만고양이님의 "Scheme 함수는 함수 body를 수행하기 전에, 인자들을 전부 evaluation합니다."
    라는 문장을 보고 순간 "아차;" 싶었습니다-_-;
    scheme이 기본적으로 인자를 먼저 계산하는 메소드를 채택하고 있다는 사실을
    잊어버리고 있었던채;;;
    여튼, 좀 속을 끙끙 앓고 있었는데 덕분에 명쾌한 답변이 되었던것 같습니다^^

    2008.03.29 18:37 신고 [ ADDR : EDIT/ DEL : REPLY ]
    • 도움이 되었다니 기쁘네요.
      이 책 놓고 있은지 꽤 오래 되었는데,
      다시 좀 봐야겠습니다. 책이 커서 그런지, 보는 중간에
      이런 일 저런 일 참 많이 생기네요.. ㅎㅎ

      2008.03.30 09:10 신고 [ ADDR : EDIT/ DEL ]

Books by Example/SICP2007.11.05 23:04
"컴퓨터 프로그램의 구조와 해석(이하 SICP)"에 대한 서평 아닌 서평을 일전에 올린 적이 있었습니다. 그 글을 올리고 한동안 책을 들춰보지 않았었는데요. 오늘 갑자기 그 책에 다시 손을 대게 되었습니다. 이러다가 평생 제대로 된 책 한권 다 읽지 못할지도 모른다, 는 공포심 같은 것이 들었다고나 할까요. 제 자신의 게으름에 물릴 대로 물렸다, 뭐 그런 겁니다.

SICP는 Scheme이라는 Lisp 언어를 대상으로 하고 있습니다. 고백하건대 저는 학부때 프로그래밍 언어 특론을 중도에 수강 포기했었습니다. Lisp 언어의 근간을 이루는 Lambda Calculus를 전혀 이해하지 못했기 때문이죠. Wikipedia의 Lambda Calculus 관련 페이지에서 한 단락을 인용해 보겠습니다.

The Lambda Calculus can be thought of as an idealized, minimalistic programming language. It is a close cousin of the Turing Machine, another minimalist abstraction capable of expressing any algorithm. The difference between the two is that the Lambda Calculus takes a functional view of algorithms, while the original Turing machine takes an imperative view. That is, a Turing machine maintains 'state' - an arbitrary long 'notebook' of symbols that can change from one instruction to the next. The imperative paradigm can be seen in programming languages like C or Basic. By contrast, the Lambda Calculus is stateless, it deals exclusively with functions which accept and return data (including other functions), but produce no side effects in 'state' and do not make alterations to incoming data (immutability.) The functional paradigm can be seen in modern languages like Lisp, Scheme and Haskell


그런데 이제와서 골치아프기까지 한데다 "먹고 사는 문제하고도 하등의 상관이 없는" 언어로 씌여진 책을 다시 공부해보겠다고 설치는 이유는 뭘까요? 첫 번째는 'Lisp나 lambda calculus라는 것이 생각보다는 어렵지 않더라', 는 깨달음인 것 같고, 두 번째는 ... 설명하기 좀 곤란하니까 넘어가도록 하죠 ^^;

아무튼, 이 책을 읽으려면 Scheme 컴파일러, 디버거 등등의 시스템이 필요합니다. 잘 알려진 Scheme 시스템으로 MIT/GNU Scheme이 있고 PLT-Scheme이 있는데, 둘 다 Windows에서는 잘 깔립니다. Linux에서는 Ubuntu라면 모르겠지만 Fedora라면 깔기가 좀 난감합니다. 설치 메뉴얼 대로 해봐도 다 잘 안되죠.  (제 리눅스는 Fedora Core 6 입니다) 거기다 MIT/GNU Scheme의 Windows 인터페이스(Erwin이라고 부릅니다만)는 하필이면 제가 익숙치 않은 Emacs 기반의 인터페이스입니다. -_-;

그러니, Windows에서건 Linux에서건 PLT-Scheme쪽이 더 낫습니다. 설치도 간단하고 (Windows에서는 인스톨러만 실행하면 되고, FC 6에서는 yum install plt-scheme이라고만 하면 됩니다) 인터페이스도 훨씬 더 직관적입니다.

PLT-Scheme 실행 화면

PLT-Scheme 실행 화면


위의 그림은 제 집 컴퓨터(Windows XP)에서 PLT-Scheme을 돌려 본 화면입니다. 리눅스가 깔린 회사 노트북(LM 70)에서도 설치해서 돌려봤는데, 저거랑 똑같은 형태로 실행됩니다. -_-

PLT-Scheme의 GUI는 DrScheme이라고 불립니다. MzScheme이라고 GUI가 없는 형태의 cheme 구현도 포함되어 있는데, MzScheme은 Unix에서 좀 더 사용하기가 편합니다.

http://www.plt-scheme.org/에서 다운받아 사용할 수 있습니다.

신고
Posted by 이병준

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

  1. 저두 그 책을 공부할려고 , scheme 을 깔려고 했던게 기억나네요. 트랙은 저는 원래 emacs 유저라 emacs 에다 붙이는 걸 남깁니다. (__

    2007.11.20 15:56 신고 [ ADDR : EDIT/ DEL : REPLY ]
  2. 반갑습니다. 뉴스2.0을 타고 왔습니다.
    오늘부터 해당 책으로 동아리에서 스터디에 들어갑니다.
    (책은 잘 모르고 하자니 따라하는 수준...OTL.....)
    해당 임플리멘테이션이 페도라에는 잘 설치가 되지 않는군요.OTL...
    (전 Fedora 7에서 오늘 8으로 올릴 생각입니다.)
    좋은 정보 고맙습니다.^^

    2007.11.23 12:22 신고 [ ADDR : EDIT/ DEL : REPLY ]
    • 아. 반갑습니다. 스터디 하신다니 좋으시겠군요.
      PLT-Scheme이면 페도라에도 잘 깔릴텐데 이상하군요.
      아무튼 잘 되길 바랍니다. :-)

      2007.11.23 12:55 신고 [ ADDR : EDIT/ DEL ]
  3. 멋지십니다. >_<//
    저도 이번주부터 학교 친구들 모아서 스터디에 들어갑니다.
    이런 뜻있는 분들이 모두 모인다면 정말 공부하는데 도움이 될듯 합니다.
    응원해주세요! -_- 중간에 포기하지않기를요 ^^

    앞으로 낭만고양이님 신세좀 많이 지겠습니다. ^^

    2007.12.17 14:31 신고 [ ADDR : EDIT/ DEL : REPLY ]
    • 스터디하신다니 부럽군요. 전 혼자 하려니 힘듭니다 ㅎㅎ 꼭 끝까지 완독하시길 바랍니다! 화이팅~

      2007.12.17 16:40 신고 [ ADDR : EDIT/ DEL ]
  4. 퍼갑니다^^ 참 좋은 정보 들이 많군요~~^^ㄳㄳ

    2008.07.23 01:30 신고 [ ADDR : EDIT/ DEL : REPLY ]