나의 큰 O는 log x야

오래 살진 않았지만 지금까지 내 삶을 정리할때 지금의 나를 만든 제일 중요한 시기를 꼽아보자면 2000년, 초3 때일것이다.때는 바야흐로 20세기가 끝나고 21세기가 태동하려는 시기. IT붐이 막 일고 있던 시기였다. 야후 코리아의 위상이 하늘 같았고, 한미르가 살아있던 시기. 이때 초3의 인생을 바꿀 커다란 사건 2개가 일어났는데, 그 중 하나는 홈페이지 제작이었다. (다른 하나는 스타크래프트로 다음 이야기에서 다뤄야할듯) 2014년 현재까지도 꿋꿋이 살아남아 발행을 계속하고 있는 과학소년 언젠가부터 엄마가 과학소년이라는 과학 잡지가 있었는데, 거기에 뜬금없이 '나만의 홈페이지 만들기'라는 주제로 글이 하나 실려왔고 그걸 본 초3 소년은 어마어마한 감명을 받은것이었다. 초등학생들을 대상으로 하는 잡지였..

적분史 2014. 4. 5. 15:05

카라슈바 알고리즘까지는 쉽게 이해했는데,톰-쿡 알고리즘은 괜히 어려워 보여서 그동안 접근하지 못했는데 사실 알고보면 단순한 거였슴다! 일반적인 곱셈 방법으로는 n자리 수 간의 곱셈을 수행하게 되면 총 n^2번의 곱셈이 필요하게 된다. 당연한 말씀.예를 들어을 곱하고자 한다면 각 자리수마다 한 번씩 곱셈을 해야하니 총 36번의 곱셈을 해야겠지요.. 근데 안드레이 톰과 스테픈 쿡이라는 학자가 발상의 전환을 했어요. (카라슈바마냥ㅋ) 숫자를 다항식으로 보고, 다항식끼리 곱하는거야 (그나마 간단한 톰-3 알고리즘을 중심으로 설명할게요.) 숫자 n과 m을 다항식으로 바꾸기 위해 3조각으로 나누도록하겠습니다. 한 조각의 단위는 100으로 잡으면 되겠네요. 자 이 조각을 계수로 이용해서 다항식을 만들어봅시다. 참 쉽..

프로그래밍/Multi precision 2014. 3. 30. 05:49

페이스북에 뭔가 연동해서 앱 만들겠다는 생각은 작년에 웹시개 과제하면서 조원의 아이디어로 하게 된건데,생각보다 재미난걸 많이 할수 있죠~근 사흘간 여러가지 시도를 해봤는데, 생각보다 페이스북 연동 관련해서 정책이 까다롭더군요.혹시나 연동하는 어플 개발하시는 분들은 참고하시길 바래요. * FQL 과다하게 날리면 페이스북은 그 앱을 악성앱으로 판단하고, 그 앱뿐만 아니라 앱 소유자 계정까지 일시정지시켜버립니다. 악성앱이 아니었음에도 이용자가 폭주해서 쿼리가 많을 경우도 차단당할 수 있어요. (이렇게 차단당하는 경우 그 앱은 아예 삭제당합니다.) * 사용자의 허락 없이 무단으로 게시물이나 사진을 올리거나 태그, 댓글 등을 달면 안됩니다. 이게 발견되면, 페이스북에서 그 앱의 publish_stream 권한을 ..

프로그래밍 2014. 3. 23. 04:28

생각해보니, 추상문법트리에서 실제 바이트 코드를 생성하는 부분은 글을 안 썼었군요... 왜 다 끝냈다고 착각하고 있었지... 짬나는대로 정리해서 올리도록 하겠습니다~ㅠㅠ

프로그래밍/PG어 2014. 3. 21. 04:40

앞의 글에서는 역사를 배워야하는 이유에 대해서 이야기했었는데요, 이번 글에서는 본격적으로 역사학에서는 무엇을 공부하는지 이야기해보도록 하겠습니다. : 역사학에서는 무엇을 배우나요? 사실 중고등학교 때 사회/역사 시간에 졸지 않았다면 사학에서 뭘 배우는지 정도는 다들 알겁니다. 1392년에 조선이 건국되고, 1492년에 콜럼버스가 신대륙을 발견하고, 1592년에 임진왜란이 발발했으며....의무교육 과정에서 배우는 역사는 (연도, 일어난 사건)의 순서쌍을 일일히 외우고, 이걸로 시험을 보는 일에 지나지 않습니다. 사실 몇몇 역덕들을 제외한 일반인들 입장에서는 저렇게 몇년에 뭐가 일어났고, 그 다음해에 뭐가 일어났는지 외우는 일은 정말로 지루하고 어렵습니다. 이것 때문에 역사공부를 포기하는 사람도 많죠.하지만..

잉여/미래 2014. 3. 18. 17:02

뜬금없이 역사 이야기를 쓰게 되었습니다. 시리즈물로 기획한 건 아닌데, 계속해서 이어서 써 나갈수있으면 좋겠네요. 저는 사학을 전공하면서도 관심은 공학 계열에 가 있는지라 수많은 이공계 사람들을 만나왔는데요, 그들이 인문학(그중에서도 특히 역사학)에 대해 가지고 있는 편견을 자주 볼 수 있었죠. 많은 인문학도들이 그들의 오해를 풀어주기 위해 이런 저런 설명을 해왔지만, 그 설명이 이공계열의 사람들에게는 충분히 와닿는 설명이 아니었던 것 같아요. 그래서 나름 중간지점에 끼어있는 사람으로서, 인문학도의 말을 이공계열 사람들의 말로 번역을 해주고 싶어졌어요. 이것이 이 글을 쓰게 된 목적입니다. : 역사를 왜 공부하나요? 사실 역사에서 무엇을 배우는가보다도 앞서서 던져야할 질문은 "역사를 왜 공부해야하는가"가..

잉여/미래 2014. 3. 16. 02:54

곱셈은 앞서(http://bab2min.tistory.com/405)에서 이미 구현했습니다. 다 좋은데 시간복잡도가 O(n^2)이라 숫자가 커지면 커질수록 너무 느려진다는 단점이 있죠. 하지만 이런 문제를 겪을줄 알았는지 이미 일찍이 수학자들이 여러 가지 빠른 곱셈 알고리즘을 발명해 놓았습니다. 여기에서는 곱셈 알고리즘 중 두번째로 구현이 간단한(그 댓가로 뒤에서 두번째로 빠른) 카라슈바 알고리즘(Karatsuba Algorithm)을 구현해보도록 할것입니다. 카라슈바 알고리즘의 개요는 다음과 같습니다. 2자리수 간의 곱을 계산하려면 일반적인 곱셈법으로는 한 자릿수 곱셈이 총 4번이 필요한데, 카라슈바는 한 자릿수 곱셈을 3번만 하고, 덧셈/뺄셈으로 나머지 부분의 결과를 구해내는 아이디어를 떠올립니다. ..

프로그래밍/Multi precision 2014. 3. 11. 23:54

앞서서 곱셈을 구현했으니, 이제 나눗셈을 구현할 차례겠죠?근데 문제는 나눗셈을 구현하는게 생각보다 까다롭다는거지요. 일반적으로 우리가 학교에서 배우는 나눗셈 방법은 장제법(long division)이라고 하는데,이게 얼마나 어려운지는 초등학생들이 더 잘 압니다.http://bab2min.tistory.com/54 자세한 알고리즘에 대한 설명은 위 페이지로 대신합니다.우리가 나눗셈을 할때 나누는 수랑 나눠지는 수 자리를 맞춰서 계산하죠. 자리 맞추기 위해 숫자들을 왼쪽으로 옮기고 오른쪽으로 옮기고 하는데, 2진법에서 이것과 근본적으로 같은 연산이 비트 시프트 연산입니다.다른말로 하면 나머지를 구하는 나눗셈 연산을 위해서는 먼저 시프트 연산을 구현할 필요가 있다는 거지요. void xl_setnan(PXLA..

프로그래밍/Multi precision 2014. 3. 2. 02:34