3. 프로그래머가 이름에 대해 가지는 잘못된 믿음들 (번역)

김모씨의 페북에서 가져온 기사의 적절(하다고 주장하는)한 번역
일본어 중역을 약간 포함했습니다.

출처 : http://www.kalzumeus.com/2010/06/17/falsehoods-programmers-believe-about-names/

———————————————————————-

오늘 John Graham-Cumming은 그의 성에 잘못된 문자가 있다고 하는 컴퓨터 시스템에 대해 불평하는 기사를 썼다. 물론 그의 이름에는 ‘잘못된’ 곳 따위는 없다. 어떤 사람이 제공한 이름이라는 것은, 정의대로라면 그것으로 적절히 자신을 식별하라고 준 것일 것이다. 당연하게도 존은 이 사태에 대해 불평을 쏟아냈고 그러는 것도 당연하다. 사실상 정의대로라면, 이름은 인간의 정체성의 가장 중요한 부분이기 때문이다.

나는 개발자로써 일본에서 수년을 일했었고, 그곳에서 이름에 특정한 형식만을 받는 시스템을 시연삼아 몇번이나 크래시 시켜보았다.  (대부분의 사람들이 나를 Patrick McKenzie라고 부르지만, 나는 내가 인식하고 있는 6개의 “풀네임”이 있고, 내가 이용한 어떠한 시스템도 내 이름을 적절하게 처리하지 못했다.) 마찬가지로, 나는 무지막지한 초거대기업이 글로벌 비즈니스를 진행하기 위해 만드는, 이론적으로 온갖 이름을 처리할 수 있는 시스템도 개발해 보았지만, 나는 단 한번도 이름을 적절하게 처리하는 컴퓨터 시스템을 본 적이 없다. 존재 자체가 의심스러울 정도다.

어쨌든 공공의 이익을 위해, 당신이 이름을 다룰 때 사용했던 가정들을 몇 가지 나열해보았다. 이 모든 가정들은 잘못되었다. 다음부터는 이런 가정들을 최대한 배제하도록 노력해보자.
1. 정식 풀네임은 오로지 하나이다.
2. 통용되는 풀네임은 오로지 하나이다.
3. 현 시점에서의 정식 풀네임은 오로지 하나이다.
4. 현 시점에서의 통용되는 풀네임은 오로지 하나이다.
5. 임의의 n에 대해, 사람은 정확히 n개의 이름을 가지고 있다.
6. 이름은 일정한 길이의 공간 안에 전부 쓸 수 있다.
7. 이름은 변하지 않는다.
8. 이름이 변하는 기회는 한정되어 있다.
9. 이름은 ASCII로 다 쓸 수 있다.
10. 이름은 특정한 문자 셋 하나로 다 쓸 수 있다.
11. 이름은 유니코드 코드포인트로 전부 매핑 가능하다.
12. 이름은 대소문자를 구별한다.
13. 이름은 대소문자를 구별하지 않는다.
14. 이름에 붙는 접두사나 접미사는 깔끔하게 무시해도 된다.
15. 이름에는 숫자가 들어가지 않는다.
16. 이름은 전부 대문자로 쓰여지지 않는다.
17. 이름은 전부 소문자로 쓰여지지 않는다.
18. 이름은 특정한 순서대로 배열될 수 있다. 동일한 배열 방법은 어떤 시스템에서든 동일한 결과를 낸다.
19. 성과 이름은 반드시 다르다.
20. last name, family name 등, 가족 관계를 나타내는 공유되는 요소가 존재한다.
21. 이름을 식별자로 사용할 수 있다.
22. 이름을 ‘대략적인’ 식별자로 사용할 수 있다.
23. ㅇㅇ 알았으니까 어쨌든 대충 백만명 정도면 이름으로 구별할 수 있다고 하자.
24. 내 시스템은 중국인 이름을 다루지 않는다.
25. 일본인도
26. 한국인도
27. 아일랜드인, 영국인, 미국인, 스페인, 멕시코, 브라질, 페루, 러시아, 스웨덴, 보츠와나, 남아프리카, 트리니다드, 아이티, 프랑스, 클링온 제국 같은 ‘이상한’ 알파벳을 쓰는곳도
28. 클링온 제국은 농담이다.
29. 문화상대주의 같은 개소리는 집어치워! 적어도 ‘내가 사는 곳’에는 이름을 쓰는 상식적인 룰이라는게 있다고!
30. 이름을 변환하고 복원하는 손실없는 알고리즘이 존재한다. (ㅇㅇ 걍 입력 받은걸 그대로 돌려주면 됨. 나 존나 머리 좋은듯)
31. 비속어를 이름으로 쓰는 사람따윈 없다.
32. 사람의 이름은 태어날 때 정해진다.
33. 어… 대충 태어나고 얼마 안돼서 정도?
34. 알겠으니까 1년 정도로 퉁치자.
35. 5년?
36. 우웅… 지금 저 놀리는거죠?
37. 한 사람은 2개의 다른 시스템에서 같은 이름을 쓴다.
38. 시스템이 잘 짜여져 있다면, 서로 다른 시스템 안의 이름 입력을 담당하는 부분은 한 사람의 이름에 대해 정확히 같은 문자열을 받는다.
39. 내 시스템을 망가트릴 정도의 희한한 이름을 가진 사람은 거의 없다. 그런 사람은 적절히 변환된 이름을 넣을 것이다. अशोक라던지. (원문은 田中太郎(다나카 타로))
40. 인간은 이름이 존재한다.

이 리스트가 모든 오류를 나열한 것은 아니다. 혹시 위 가정이 틀렸음을 나타내는 현실의 예를 알고 싶다면, 기꺼이 몇몇 예를 알려줄 수 있다. 리스트에 추가하고 싶은 예가 있다면 자유롭게 댓글로 달아주시라. (주: 원문의 댓글) 그리고 만약 어떤 사람이 last_name 컬럼과 first_name 컬럼을 사용하는 천재적인 데이터베이스 테이블을 제안했을 때, 이 포스트를 한 번 보여주시라.

———————————————–

적절한 예시

11. http://ja.wikipedia.org/wiki/満田かずほ – 이 사람(미츠다 카즈호)의 이름은 유니코드에 있는 한자로 쓰지 못합니다.

15. 안녕하세요에 나온 ‘이0’씨 라던지…

18. CP949와 EUC-KR과 UTF-8로 쓰여진 한국어 이름을 사전순으로 배열해봅시다. (심지어 EUC-KR에선 설믜라는 이름을 가진 사람은 존재하지 않는다고 합니다.)

20. 아이슬란드에선 아버지의 이름이 A면 아들의 성은 A+sson, 딸의 성은 A+dottir가 됩니다. (부모자녀의 성이 전부 다릅니다.)

28. 클링온은 스타트렉에 나오는 외계 종족입니다. 스타트렉 덕후들 중엔 해외 모임에서 영어가 안통해서 클링온어로 대화한적도 있다는 전설이 있다고 합니다.

29. DQN네임

30. 혐오스런 마츠코의 일생의 감독인 中島哲也(나카시마 테츠야)의 성은 일반적으로 나카’지’마 라고 읽습니다. 희귀한것 같아도 의외로 흔합니다.

35. 스웨덴에는 법이 마음에 안든다고 5살까지 이름을 안 붙이다가 Brfxxccxxmnpcccclllmmnprxvclmnckssqlbb11116라는(…) 이름을 붙인 부모가 있습니다.

36. 일본어로 읽어야 맛깔납니다.

 

Read More

1-1.0 PP Project 1 Test Program

bpy

SNU Principles of Programming Fall 2014

Duststorm test program

Download Link : pp_prj1_test

 

Author : KINETC_ (Jhoo Ho Young / [email protected]) 2014/11/22
Developed with Qt, PySide, PyDev, cx_freeze
Available for Windows
Released as open source under LGPL license

——— how to use ———–
in ocaml
1. move prj1_test.ml to project 1 folder
2. ocamlc prj1.ml
3. ocaml prj1.cmo prj1_test.ml
4. copy results (robots, shelters, results)

in windows
5. run build/prj1_test.exe
6. paste results in each text browser
7. click assign button
8. …
9. PROFIT!

 

—————————–

pp 플젝 1번 테스트를 하려고 했더니 답이 없어서

그냥 프로그램을 만들어버렸다.

한번도 안써본 Qt를 다뤄보려니…

역시 비주얼 베이직 써볼걸 그랬군

Read More

1-0. 1/3-2/3 Conjecture

순서론에서의 한 추론이다. 무려 50년이 되도록 미증명상태

 

0. 기본 지식

어떤 유한한 set이 있다고 하자. 대충 A = {a, b, c} 의 부분집합들의 집합

B = {{}, {a}, {b}, {c}, {a, b}, {a, c}. {b, c}, {a, b, c}}

를 가정하자.

이 때, B의 각 원소를 원소의 갯수에 따라 정렬한다고 하면 {}, {a} 같이 대소 비교가 되지만 {a}, {b} 같이 대소 비교가 안되는 놈이 존재한다.

그래도 어쨌든 대소비교가 되는것 끼리 모일 수 있으므로 대충 저 위의 꼴과 비슷하게

{} -> {a},{b},{c} -> {a, b}, {b, c}, {c, a} -> {a, b, c} 순으로 정렬 된다. (각 step의 내부의 순서는 무시하고)

요런 놈을 partially ordered set, 줄여서 poset이라고 한다. (원소간에 대소비교가 불가능한게 있어도 된다. 만약 임의의 원소 두개에 대해 전부 가능하면 totally ordered set이라고 한다.)

대소 비교를 할때는 반드시 대소 비교를 하는 부등호가 존재하므로 위에서 정렬 할 때 사용한 부등호를 <= 라고 하자.

그러면 한 집합을 <=에 대해 poset이 되게 정렬하려면 <= 는 다음의 성질을 만족해야 한다.

(1) a<=a

(2) a<=b, b<=a -> a=b

(3) a<=b. b<=c -> a<=c

3가지 모두 당연한 성질이지만, (2)번 때문에 대소 비교가 되지 않는 두 원소는 대소가 같은것이 아니라 그냥 대소 비교 자체가 정의가 되지 않은것으로 처리된다.

그러면 자연히 그 두 원소의 비교가 가능하게 만드는 부등호로 위의 <=를 확장 시킬 방법이 있는지 찾게 될텐데 (예를 들면 위의 A를 알파벳 순으로 정렬한다던가)

그놈을 <=*라 하면 <=*는 <=의 linear extension 이라고 한다.

 

1. Conjecture의 내용

이 때, partially ordered set이면서 totally ordered가 되지 않은 유한집합 P가 있다고 하자. 정렬은 부등호 <=로 한다.

그러면 p가 totally ordered가 아니므로 <=의 linear extension들이 여러개 존재하게 된다.

이 <=의 linear extension들의 집합을 L이라고 하자. (P가 유한집합이기 때문에 L도 당연히 유한집합이다.)

그러면

“P의 어떤 두 원소 x, y에 대해

|L| * 1/3  <= { x(<=”)y | (<=*)는 L의 원소} <= |L| * 2/3

이 되는 x, y가 항상 존재한다.”

가 Conjecture의 내용이다.

 

세줄로 요약하면

“대소비교를 정의하는 도중에

어떤 두 원소의 대소를 정의해버리면

남은 정렬 방법의 수가 1/3이상 2/3이하가 되는 두 원소가 존재한다.”

 

좀 더 실용적으로 말하자면

a<b<c<d

1<2<3<4

현재까지 이렇게 정렬되어있다고 할 때,

a<4를 정의하는 것 보다 d<1을 정의 하는 것이 남은 정렬 방법의 수가 훨씬 적어지게 된다.

문제는 이걸 임의의 집합에서 임의의 정렬 상태와 step에 대해 정렬 방법의 수를 언제나 2/3 이하로 줄일 수 있는 두 원소를 찾을 수 있냐는 것이다.

 

2.

대충 생각하면 정렬 방법의 갯수는 n!개고 항상 찾을 수 있다면 알고리즘을 잘 짜면

정렬 시간이 log_(2/3) n! ~ O(n logn)이 된다는 소린데

수많은 O(n logn) 알고리즘들이 있는걸 보면 말이 되는것 같기도 하고…

문제는 이게 증명도 반증도 안되어있다는 걸 보면 또 그렇게 간단한것도 아닌것 같다.

 

이런 conjecture가 나온 배경에는

a<=b 가 정의되어 있고 거기에 c를 끼워 넣을때

a<=b<=c, a<=c<=b, c<=a<=b, 3가지 경우가 존재하는데

a<=c를 정의하면 남는건 왼쪽 2개밖에 없고, b<=c를 정의하면 왼쪽 1개밖에 안 남아서

딱 남은 정렬의 갯수가 1/3-2/3 사이에 놓이게 된다.

이게 원소가 n개일때도 가능하냐는 말이지.. (이렇게 보니 되게 제한이 빡빡하군)

 

가능 할것 같은데…

 

 

 

Read More