교내 프로그래밍 대회에서 내가 출제한 문제 중 하나가 바로 후위 표기법(Postfix Notation) 을 계산하는 쉬운 문제였는데, 이 문제에서 양수와 음수 모두의 사칙연산을 처리해 줘야 하는 것이 함정이라서 생각보다 정답률이 높지는 않았다.




C. 후위 표기법


그런데 대회가 끝나고 나서, 이 문제에 대해 본인이 테스트 할 때는 제대로 답이 나오는데 Judge 는 오답이라고 판정하는 이유를 아무리 생각해도 모르겠다며 나를 찾아온 후배가 있었는데, 어떤 부분이 잘못 되었는지 토론하던 중에 이런 이야기가 있었다.

"문제의 기술에서는 음수의 나눗셈에서 몫만 계산한다고 할때 -10 / 3 = -3 이 아닌 -4 가 될 수 있는데, 이 부분이 ambiguous 하지 않은가??"

결론적으로, 오늘 claim 을 했던 후배의 소스코드를 검토한 결과 소스코드의 오류는 divide by zero 이후의 수식을 제대로 예외처리 하지 않은 문제였다. 그런데 음수의 나눗셈에 대한 문제는 나도 좀 애매해서 인터넷을 찾아보니 다음과 같은 명쾌한 설명이 있었다.

agile 이야기 :: 표면적 단순함과 심층적 단순함 : -5/4 는 얼마일까

저 글을 참고하면 결론적으로, "음수의 나눗셈은 프로그래밍 언어마다 다르게 구현된다" 가 정답이고, 실제로 수학자들 사이에서도 -10/3 = -3 인지 -10/3 = -4 인지는 논란이 되고 있으며, 일반적으로 어느 쪽으로 정의하느냐에 따라 해당 정리에 맞게 사용된다고 한다.
( C 나 C++, Java 에서는 -10 / 3 = -3 이 되고, Python, Ruby 에서는 -10 / 3 = -4 가 된다. )

다만, 이 프로그래밍 대회에서는 "사용 언어를 C 와 C++ 로 규정지었으므로, C 와 C++ 의 나눗셈연산 결과를 사용하는 것이 맞다" 라고 결론을 지었다.

그냥 지나칠 수 있는 이런 미묘한 부분까지 덕분에 새롭게 리뷰할 수 있어서, 나 자신에게도 좋은 공부가 되는 기회가 된 것 같다. =)  사실 이 문제의 샘플 인풋에서는 의도적으로 음수의 나눗셈을 표시하지 않았는데 이것을 샘플 인풋에서 오픈했더라면 이런 오해는 없지 않았을까 하는 생각도 든다. ;)

사용자 삽입 이미지
참고 ) Wikipedia 의 Integer Division 설명



신고
댓글을 달아주세요!
  1. BlogIcon 규욱 2007.09.12 19:39 신고  댓글주소  수정/삭제  댓글쓰기

    음.. 언어마다 다른거였군요.. 저도 지금까지 몰르고있었네요.. ㅎㅎ

    • BlogIcon mynotepad 2007.09.13 03:24 신고  댓글주소  수정/삭제

      좋은 소프트웨어 엔지니어가 되려면 역시 여러가지 프로그래밍 언어와 컴파일러들의 다양성과 차이점을 아는 것이 중요하드라... 나는 주로 C, C++ 만 쓰는지라 다른 언어는 잘 몰라서 이렇게 언어간의 차이점을 발견할 때 마다 알아두려고.. ㅋ

  2. BlogIcon 김정희 2007.09.17 12:21 신고  댓글주소  수정/삭제  댓글쓰기

    음.. 언어마다 다른것은 좀 의외네요...

    • BlogIcon mynotepad 2007.09.17 15:06 신고  댓글주소  수정/삭제

      교수님 말씀이 음수의 나눗셈은 수학자들 사이에서도 각자 정의가 다르다고 하네.. ;)
      그래서 이런 생각을 해봤어. 만약 음수를 나누는 문제가 출제되었는데 python 으로 구현하는 사람과 C++ 로 구현하는 사람이 있다면 각각 답이 다르게 나올테니 사용 언어에 따라 정답이 다를 것이라는...;; 이런 경우엔 문제에 조건을 명확하게 명시해야 겠군. ;)

  3. 새빛 2007.11.20 12:02 신고  댓글주소  수정/삭제  댓글쓰기

    안녕하세요. floor 함수 (greatest integer less than or equal to 함수)에 대해서 검색하다 들르게 되었습니다.

    이견을 말씀드리자면, 수학에서 (정수)÷(자연수) 의 몫과 나머지를 정의하는 방법은
    제가 알기로는, 절대 수학자마다 다르지 않습니다.

    고등학교 교과서(10-가)에서도 그렇고, 대학에서 교재로 쓰이는 정수론이나 추상대수학 책들을 보면
    모두 한가지 원칙에 근거해서 정수 나눗셈을 정의하고 있습니다.
    그 원칙이란 다름 아닌 "나머지의 범위가 0 이상 제수 미만"이어야 한다는 것입니다.

    -1을 3으로 나누면, 몫이 0이고 나머지가 -1인게 아니라, 몫이 -1이고 나머지가 2입니다.
    -2를 3으로 나누면, 몫이 0이고 나머지가 -2인게 아니라, 몫이 -1이고 나머지가 1입니다.
    -3을 3으로 나누면, 몫이 -1이고 나머지가 0입니다.
    -4를 3으로 나누면, 몫이 -1이고 나머지가 -1인게 아니라, 몫이 -2이고 나머지가 2입니다.
    -5를 3으로 나누면, 몫이 -1이고 나머지가 -2인게 아니라, 몫이 -2이고 나머지가 1입니다.
    등등등.......

    이렇게 정의하는 이유는 아마도 다음과 같은 일관성을 유지하기 위한 것으로 생각됩니다.
    가령 3으로 나눈다고 했을때, 가능한 나머지는 0,1,2 의 3가지입니다.
    그러면 정수를 3을 가지고 3부류로 나눌 수 있는데

    [3으로 나눴을때 나머지가 0인 것] = { ... , -9, -6, -3, 0, 3, 6, 9, ... } ::::: (*)
    [3으로 나눴을때 나머지가 1인 것] = { ... , -8, -5, -2, 1, 4, 7, 10, ... } :::: (*) 에다 1씩 더한거입니다.
    [3으로 나눴을때 나머지가 2인 것] = { ... , -7, -4, -1, 2, 5, 8, 11, ... } :::: (*) 에다 2씩 더한거입니다.

    이렇게 자연수에서 가능한 것을 자연스러운 방법으로 정수로 확장할 수 있습니다.

    그러나 -10 나누기 3을, 몫이 -3이고 나머지가 -1이라고, 이런 방식으로 (음수)÷(자연수)를 정의한다면
    분모(피제수)가 자연수일 때 성립하는 위와 같은 성질이 그대로 성립하지 않습니다.
    당장 가능한 나머지의 가짓수도 3가지에서 5가지로 늘어나죠. 복잡해집니다.
    복잡해진 반면에 거기서 얻을 수 있는 것은 그다지 별로 없구요.

    • BlogIcon mynotepad 2007.11.20 13:15 신고  댓글주소  수정/삭제

      좋은 의견 감사드립니디. ^^
      제가 음수의 나눗셈에 대해서 수학전공 교수님에게 여쭤어 보았는데 음수의 나눗셈 연산정의에 대해서 일부 수학자들 사이에서 위와 같은 이견이 있다고 하셨고, 제가 알아본 결과도 이런 소수의견이 존재하는 것으로 알고 있습니다. ( 교과서나 주요 정수론 서적에서는 말씀하신 것 처럼 우리가 알고있는 일반적인 정의가 사용되지만요.. ) 그래서 프로그래밍 언어에서도 각기 다른 정의가 적용 되는 것이겠지요.

  4. 새빛 2007.11.20 12:12 신고  댓글주소  수정/삭제  댓글쓰기

    정수의 나눗셈에서 논란이 되는 것은 분자(피제수)가 음수인 경우가 아니라, 분모(제수)가 음수인 경우입니다.
    앞서 말한 원칙인 "0 이상 제수 미만"이라는 것 자체가 넌센스가 되어 버리니까요.

    이 문제를 해결하는 방법은 두 가지가 있습니다.
    첫째. 나머지의 밤위를 '0 이상 |제수| 미만' 으로 한정시키는 방법. (| | 기호는 절대값을 의미)
    둘째, 나머지의 범위를 '제수 초과 0 이하'로 한정시키는 방법. (제가 기억이 확실하지 않아서... 제수 이상 0 미만일수도 있음.. :)

    • BlogIcon mynotepad 2007.11.20 13:25 신고  댓글주소  수정/삭제

      사실 저는 수학전공이 아닌 전산학 전공의 일반 프로그래머이기 때문에, 본문에 언급한 정도 수준이면 제가 처음에 가졌던 의문점을 풀 수 있었다고 생각해서 더 이상 자세히 알아보지는 않았는데, 말씀하신 내용도 매우 합리적이군요.. 덕분에 좋은 공부가 되었습니다. ;)

  5. 새빛 2007.11.20 16:35 신고  댓글주소  수정/삭제  댓글쓰기

    감사합니다. 검색질을 좀 해보니, 컴퓨터 쪽에서는 몫을 0쪽으로 절삭(truncate towards zero)하는 방식으로 정수 나눗셈이 동작하는 경우가 흔하네요. 포트란 시절 부터 그래왔다고 하며, C99 표준에서도 아예 이러한 방식으로 못을 박아 버렸습니다. (C90에서는 이를 따로 정의하지 않았지만, 많은 수의 컴파일러가 이 방식으로 동작했다고 합니다.)

    심지어 인텔 플랫폼의 IDIV명령(부호있는 정수 나눗셈 명령)도 이와같은 방식으로 동작하네요. 아, 그리고 C언어의 int 타입 캐스팅(혹은 int() 캐스팅 함수)도 같은 방식입니다.

    이유가 뭘까 궁금해지네요. 단지 과거(이를테면 포트란, 과거에 나온 C 컴파일러)와의 호환성 때문이라고 말해버리기엔 그 이상의 뭔가 있어 보이는데... 왜냐면 포트란은 과학 기술용으로 만들어진 언어이고, 그렇기 때문에 상식적으로 생각해 봤을 때 수학에서 동작하는 방식과 같은 방식으로 정수 나눗셈이 동작하도록 했을 법한데 그렇게 하지 않았다는 것이거든요. 그렇다면 뭔가 다른 이유가 있어서 'truncate towards zero'의 방식으로 정수 나눗셈 방식을 결정한 것은 아닐까 하는 생각이 드는데, 그 이유가 뭔지는 저도 아직 잘 모르겠네요. :)

    참고:
    * [C언어의 진화] ② C99의 신기술들 (ZDnet Korea)
    http://www.zdnet.co.kr/builder/dev/c/0,39030803,39131011,00.htm

    * 나머지 연산자의 동작 (KLDP)
    http://kldp.org/node/55978

    * 나머지 연산자 (KLDP)
    http://kldp.org/node/74561

    * IDIV--Signed Divide (Intel)
    http://www.intel.com/software/products/documentation/vlin/mergedprojects/analyzer_ec/mergedprojects/reference_olh/mergedProjects/instructions/instruct32_hh/vc135.htm

    저는 수학교육을 전공하고 있는 학부생이며 프로그래밍은 취미로 이리 저리 찔러보는 정도입니다... :)

    • BlogIcon mynotepad 2007.11.26 22:48 신고  댓글주소  수정/삭제

      답변이 늦었네요..
      좋은 지적 감사드립니다. ^^
      일부 인어에서 몫을 0으로 절삭하는 방식으로 동작하도록 설계한 이유가 새삼 궁금해집니다... 가만 생각할때 특별히 유리한 점이 뭐가 있는지 사실 잘 모르겠습니다만... ^^

  6. BlogIcon shinlucky 2008.10.15 23:08 신고  댓글주소  수정/삭제  댓글쓰기

    어셈블러에서 기계어 나머지 연산을 시스템콜을 사용하지 않고 구현하는 과제를 하던 도중인데,
    덕분에 좋은 글들 읽고 갑니다.
    감사합니다^^;

    저도 수학전공은 아니지만 -.-;
    프로그램 짜느라 짱구좀 굴려보다보면 나눗셈에서 문제가 된 것이

    제수가 음수일 경우에는 문제가 되지 않지만(피제수가 양수라 가정)
    정작 가장 문제가 되는 것은 피제수(나눔을 당하는수-dividend)가 음수일때 문제가 됩니다.
    피제수가 음수면 제수가 양수 또는 음수일 경우
    위에서 언급한 여러 프로그램들마다 다른방식으로 처리하듯이 나머지를 양수로 처리하느냐, 그 외로 처리하느냐 고민하게 됩니다.

    피제수가 양수이면 제수가 양수이면 몫이 양수가 나오고, 음수이면 몫도 음수이기 때문에 나머지 연산에 지장이 없으나,
    피제수가 음수일 경우 어떤 방식으로 해나갈지 큰 고민에 빠지게 됩니다.

    어셈블리어의 경우 최적화된 나눗셈 알고리즘을 사용하게되는데..... 결국 C 형식으로 택하게 되었습니다.
    (프로그램짜는 입장에서 그방식이 훨씬 사용성이 좋다고 생각합니다.)


    아.. 잡설이었고 아무튼 좋은 링크와 글 잘보고 갑니다^^

이름 암호 홈페이지