파이, 수학에서의 패턴

1998년에 개봉한 <파이>라는 영화가 있다. 제목은 음식 파이가 아니라 원주율 파이를 가리킨다. 구체적인 내용은 본인도 기억이 안 난다만 배경은 아마 20세기 중반 정도의 가까운 과거이고, 수학 덕후 주인공과 유대교 랍비가 나오고 '쿵쿵따다 쿵쿵따다 쿵쿵따다 쿵따~' 이런 인상적인 BGM이 나오고, 이례적으로 흑백으로 만들어진 좀 마이너 매니악한 취향의 영화이다.

벤허처럼 1950년대에도 컬러로 만들어진 영화가 있는 반면, 1990년대에 일부러 흑백으로 만들어진 영화도 소수나마 있다. 내가 아는 건 쉰들러 리스트와 저것밖에 없다.
뭐, 킬 빌은 녹엽정 격투 장면이 수위 조절(사지가 날아다니고 피가 철철 튀고..)을 위해서 일부 흑백으로 촬영됐다고는 하는데.. 그런 일부 장면 말고 작품 전체가 흑백인 것 말이다.

과거에 텔레비전의 화질이 디지털 HD로 한층 업그레이드 되자, 출연자들의 피부 표면이 예전보다 훨씬 더 선명하게 보이기 시작했다. 이 때문에 분장· 화장을 맡은 방송 스탭들의 수고가 더 커졌다고 한다.
그리고 텔레비전이 흑백으로 컬러로 바뀌었을 때에도 예전에 대충 하면 되던 각종 보정이나 특수효과들이 이제는 통하지 않게 되었다고 한동안 난리가 났다고 한다. 예를 들어, 없는 눈을 만들어서 눈 내리는 장면을 만들기가 흑백 시절보다 훨씬 더 어려워진 것이다.

하지만 그 반대도 그저 만만하지는 않다. 컬러 찍듯이 평범하게 세팅을 한 뒤에 영상에서 채색을 제거하고 명도만 남긴다고 해서, 보기 좋은 흑백 영화를 만들 수 있는 건 물론 아니라고 한다. 흑백으로 찍었을 때 배경과 인물 분간이 잘 되게 별도의 방법론을 동원해야 한다.
얘기가 좀 옆길로 새었다만 아무튼.. 저 pi 영화에서는 다음과 같이 주인공의 신념(가설)이 담긴 독백 대사가 나온다.

사용자 삽입 이미지

1. 수학은 자연의 언어이다.
2. 우리 주변의 만물들은 수를 통해 표현되고 이해될 수 있다.
3. 그 수들을 그래프로 표현해 보면 패턴이 나타난다.
그러므로 자연에는 패턴이 어디에나 존재한다.


1번을 반영하여 <컨택트>(1997)라는 영화에서는 외계인이 무슨 심장 박동 같은 신호를 2 3 5 7 11... 소수 간격으로 보내는 장면이 나온다. 수학은 지구인이나 외계인이나 다같이 공감할 자연의 언어이니까 말이다.
2번은.. 오늘날 디지털 컴퓨터에서 맨날 하는 짓이 바로 이것이다. 양자화, 전산화, DB화... 인간이 접하고 취급하는 사물의 모든 현상과 정보를 숫자로 표현했기 때문에 컴퓨터가 글과 그림, 소리를 출력할 수 있다.

그리고 3번과 그 이후는 정말 그러한지는 알 수 없다. 단지 그런 패턴을 발견해서 깔끔한 수식으로 아름답게 표현하는 것이 세상 모든 수학자들의 로망인 건 사실이며, 영화에서는 이를 더욱 드라마틱하게 표현했을 뿐이다.
그런데 패턴이라...;; 이 시점에서 본인은 <말죽거리 잔혹사>의 대사가 떠오르지 않을 수 없었다.

사용자 삽입 이미지

"2 로그 2에 4를 푼다. 우선 2로그에서 앞에 있는 2를 뒤로 쭉 빼. 그리고 4 위에 살짝 올려. 왜? 패턴이니까. 수학은 논리가 아니고 뭐다?"


로그값 계산을 저렇게 거창하게.. 무슨 집 맞은편 편의점까지 모험을 떠나고, 동네 뒷산으로 에베레스트 등반을 하듯이 하는 풀이는 처음 본다. ㅠㅠ

당연히, 두 말할 나위도 없이..
전자의 영화에서 말하는 그 심오한 패턴이랑, 후자의 영화에서 말하는 그냥 시험 문제 풀이 테크닉에 가까운 패턴은.. 격이 완전히, 달라도 너무 다른 용어이다.
(뭐, 안 내상 씨도 혹시 진짜 현업 수학 교사를 불러다가 연기 시킨 게 아니냐는 말을 들을 정도로 연기를 잘하긴 했다.;; ㄲㄲ)

말죽거리 잔혹사는 영어 명사의 종류 고추X집물뿐만 아니라 수학에서도 그 당시의 참 비효율적인 입시 위주 암기 위주 교육을 그럭저럭 풍자했다.
하지만 뭐든지 다 잘하는 천재 괴수들은 그런 교육 체제에서도 다 100점 받고 할 거 다 하긴 했다.

Posted by 사무엘

2018/11/03 08:36 2018/11/03 08:36
, ,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/1550

Trackback URL : http://moogi.new21.org/tc/trackback/1550

Leave a comment

본인은 평소에는 15년 넘게 개발하고 있는 날개셋 한글 입력기의 개발에 대부분의 역량이 집중되기 때문에 타 유명 프로그래머 고수들에 비해 타 플랫폼· 언어· 최신 프로그래밍 기술에 대한 개인적인 관심은 덜한 편이다. 뭐, 자주 언급을 안 할 뿐이지 직장에서는 아무래도 갑님이 시키는 대로 해야 하니, 무엇이건 업무와 생존에 필요한 최소한의 맛보기 정도는 한다. 다만 그런 생소한 분야는 본인이 특장점이 없이 그냥 여느 평범한 프로그래머 A, B의 역량과 다를 바 없다.

먼 옛날에 Windows API와 MFC, Visual C++를 처음으로 공부할 때 그러했고, macOS나 안드로이드 개발을 처음으로 익힐 때도 마찬가지이다. 코드와 리소스가 어떤 방식으로 연결되는지 감을 잡는 게 참 어려웠다. 이건 그야말로 프로그래밍 언어뿐만 아니라 각 플랫폼별 바이너리 실행 파일(DLL/EXE)의 구조, 개발툴의 기능에 대한 총체적인 이해가 필요한 부분이니까 말이다.

그래도 리소스(대표적으로 대화상자/화면 레이아웃)의 기술을 위해 XML을 쓰는 요즘 플랫폼에 비해, Win32 API의 rc 파일은 정말 구닥다리이구나 싶은 생각이 든다. 뭐, resource.h와 R.java처럼 개념상 일말의 공통점이 발견되는 것도 있다(개발툴이 자동으로 생성해 주는 리소스 ID 리스트).

또한 안드로이드의 경우, 굉장한 뒷북이긴 하다만 Eclair니 Froyo니 하던 시절과 비교했을 때 개발 환경이 몇 년 사이에 정말 엄청나게 달라져 있었다. 여전히 이클립스를 쓰는가 했더니 Android Studio라고 전용 개발툴로 진작에 갈아탔으며, 무엇보다 에뮬레이터도 x86과 arm이라는 엄청난 CPU 구조 차이를 어떻게 극복했는지 속도가 꽤 빨라졌다.
그도 그럴 것이 그 구글 내부에서 안드로이드 OS에만 달라붙어 있는 세계구급 날고 기는 프로그래머 엔지니어들이 도대체 얼마나 되며, 이들이 매일 생산하는 코드의 양은 또 얼마나 될까?

2010년대 이후에나 등장한 IDE가 copyright이 왜 엄청 옛날인 2000부터 시작하는지 궁금해서 검색을 해 봤더니.. 이건 그 옛날부터 개발되어 온 타 회사의 IDE를(이클립스 말고) Google이 인수해서 자체적으로 발전시킨 것이어서 그렇다고 한다. 으음..

이럴 때마다 늘 드는 생각인데, 새로운 문물이나 지식을 아주 빨리빨리 잘 익히고 남에게 가르치는 것까지 가능할 정도로 머리가 좋은 사람들이 개인적으로 굉장히 부럽다. 난 굳이 말하자면 애초에 남이 안 하는 짓을 골라서 하는 일에 일가견이 있다. 그래서 정보 올림피아드도 공모 부문에서만 입상하고, 코딩과 논문으로 그럭저럭 지금까지 지내 왔다.
그게 아니라 남과 똑같은 조건에서 뭔가를 빨리 달달 외우고 응용하는 능력이라면 본인은 남들 평균보다 못하면 못하지 결코 뛰어나지는 않다.

컴퓨터 쪽에 우글거리는 수많은 고수 괴수들 중에.. 김 상형 님이라고 한때 winapi.co.kr 이라는 사이트를 운영했고 지금은 '소프트웨어 공학'을 일본어 스타일로 축약한 '소엔'이라는 사이트로 여러 유용한 프로그램 개발 정보를 무료로 공유 중인 대인배가 계신다.
사이트 이름에서 유추할 수 있듯 한때 이분의 전문 분야는 Windows API였다. 텍스트 에디터를 그냥 C++만으로 혼자서 처음부터 끝까지 다 만들었고, 그 테크닉을 소스까지 통째로 책을 출간한 바 있다..;;

한 분야의 기술만 통달하기에도 벅찬데 이분은 안드로이드, HTML, 자바스크립트 등 온갖 분야를 다 탐독해서 책을 쓰고 학원 강사로 뛰고 있다.
그냥 위에서 내려오는 회사 업무나 감당하기 위해서 여러 기술들을 찔끔찔끔 서바이벌 수준으로 익히는 게 아니다. 그야말로 남을 가르치고 책을 쓸 정도로 전문가가 되기 위해서 혼자서 도대체 공부를 어떤 방식으로 얼마나 한 걸까? 비결이 궁금해지지 않을 수 없다.

이렇게 강의와 저술만으로 먹고 사는 데 지장 없는 분들은 굳이 회사 들어가서 조직에 매일 필요가 없다. 물론 프리랜서는 월급쟁이보다야 소득이 훨씬 불안정하고 복불복이 심하다. 보통은 자기 친구들에게도 "걍 회사에서 월급 받으며 지내는 게 짱이야, 아무리 엿같은 동료나 상사가 있더라도 어지간해서는 거기서 절대로 뛰쳐나올 생각 마라" 이렇게 권유를 할 정도라고는 하지만..
이것도 자기 하기 나름이다. 엄청난 능력자라면 을임에도 불구하고 여러 기업들을 상대로 갑질을 하면서 자유롭고 편하게 일을 할 수도 있을 것이다.

그리고 컴퓨터가 나왔으니 영어도 빠질 수 없다.
지금보다 자료 접근성이 훨씬 열악했던 옛날에 독학으로 이를 악물고 영어를 마스터해서 198, 90년대에 이미 유명 영어 교재의 저자로 등극한 사람들이 참 대단하다는 생각이 든다.
최 은경 어린이 영어, 오 성식 생활 영어/pops English, 김 인환, 정 철 ... 그리고 최근에는 Arrow English로 유명한 최 재봉 이런 분들.

난 무슨 영문과 교수나 영어 교사, CNN 리포터-_-;; 이런 거 지향하는 게 아닌 이상, 국내에서 영어 때문에 스트레스 받을 일은 없는.. "반도 토박이치고는 뭐 그럭저럭 하네" 딱 그 정도까지만 영어가 된다. 자막 없이 영화를 다 알아듣거나, 토익 만점 이런 경지는 아니다. 그리고 그마저도 나이는 자꾸 먹고 있는데 영어를 당장 쓸 일은 없으니 감이 점점 쇠퇴-_-하는 중이다.
도무지 들리지가 않는 것, 그리고 아무리 머리를 짜내도 독해 속도를 도저히 더 올릴 수 없는 건 그냥 내 머리의 한계인 것 같다.

영어를 잘하려면 뭐 영어식 사고방식과 어순 감각을 익혀야 되고 무슨 발상의 전환을 해야 하고.. 이런 것들은 그냥 기초가 없고 첫 단추부터 완전 잘못 끼운 생짜 영어 포기자한테는 꽤 유효한 조언일지 모른다. 영어 점수 2~30점을 6~70점으로 올리는 데는 도움이 될 것이다.

하지만 90점을 95점으로 올리는 건 무리임. 저런 기초적인 문법과 어순 감각은 이미 다 갖춰져 있고, 거기서 상위권에서 최상위권으로 가려면 그냥 닥치고 영어라는 빅데이터에 수시로 많이 노출돼서 감을 유지하는 것밖에 답이 없다. 외국 어학 연수는 개나 소나 아무나 가는 게 아니라 딱 이 정도 기초가 갖춰진 애들이 가야지 효과가 높아진다.

그런데, 저런 여러 영어 전문가들이 공통으로 말하는 영어 마스터 비결은.. 학창 시절에 영어 교과서 텍스트들을 몽땅 통째로 암송· 암기했다는 것이다. 사실 인간의 언어에는 굉장히 무작위하고 arbitrary하고, 그냥 문맥이 곧 용례를 결정하는 그런 정보가 많다. 암송· 암기는 학습자에게 괴로운 과정이긴 하지만 그래도 그거 효력은 확실한가 보다.
나도 테이큰의 전화 통화 대사 40초 분량은 통째로 줄줄 외우고 있긴 하다만.. -_- I don't know who you are ... I will find you. And I will kill you. 같은 거.. 그런데 영어를 잘하려면 그런 거 암기를 더 많이 해야 한다.

일본은 개개의 국민들이 다 영어를 못 하더라도 국가 차원에서 번역을 엄청 많이 잘 해 놨다고 그런다. 하지만 우리나라는 모든 국민들이 다 영어를 잘하는 것도 아니고, 번역을 깔끔하게 잘한 것도 아니니 뭔가 문제가 있어 보인다.

끝으로, 어려운 과목의 끝판왕인 수학이 있다. 수학은 영어와 달리 유행을 별로 안 탄다. 한편으로는 노력한 만큼 그대로 결과가 나오는 참 정직한 과목 같으면서도, 한편으로는 타고난 머리 지능빨을 타니 불공평한 면모가 느껴지기도 하는 과목이다.
수학에는 '정석' 책 하나로 그야말로 억만장자가 되고 우리나라에서 최고로 성공한 사람이 있다. 물론 이분 역시 머리가 공부벌레 괴수급이었으며, 굳이 책 안 쓰고 학원과 과외 강사료만으로도 그 옛날에, 겨우 20대 나이로도 왕창 잘나갔을 정도로.. 비범했다.

그런 정석의 저자가 말하는 수학 잘하는 비결은.. 수학은 처음에 느리고 시간이 걸리더라도 직접 계산해 보고 손으로 일일이 쓰면서 감을 익혀야 한다는 것이다. 그런 감이 생겨 있지 않은 사람이 눈으로만 보고 넘어가서는, 그리고 덥석 해설과 풀이를 봐서는 진짜배기 수학 실력이 절대 늘 수 없다고.. 참 너무 원론적이고 당연한 조언을 한다. 그건 게임으로 치면 그냥 무한 맵에 치트키 쓰는 것이나 마찬가지니까.

그리고 저 말을 프로그래밍에다가 적용하자면.. 일일이 직접 코딩해 보고 돌려 봐야 실력이 는다는 말과 일맥상통한다. 그 점은 본인 역시 적극 동의한다.
아무 감도 없는 사람이라면 노가다 코딩이라도 해 봐야 된다. 그런 경험을 많이 해 봐야 노가다 코딩을 왜 '노가다'라고 부르는지 그것부터 좀 알게 된다.

개발자, 프로그래머로 먹고 살려면 솔까말 트리 구조 순회 같은 재귀호출을 스택 배열로 직접 구현하기, 포인터 조작으로 연결 리스트의 원소 배열을 역순으로 바꿔치기 정도는 머릿속에서 로직이 어느 정도 암산이 돼야 하고, 굳이 컴퓨터가 없이 화이트보드 앞에서도 의사코드를 쓱쓱 적을 수 있어야 하지 않는가?

사실, 유수의 IT 업체들이 학-석사 급의 엔지니어를 뽑을 때 코딩 면접도 딱 이 정도 수준의 난이도가 나온다. 무슨 "B+ 트리를 구현하시오, 동영상 압축 알고리즘의 모든 과정을 설명하시오"가 아니다. 그리고 크고 유명하고 재정 넉넉한 기업일수록 당장 현업에서 쓰이는 HTML5니 자바스크립트니 언어 문법 지식보다는 저런 미래의 잠재성과 응용력, 새로운 기술을 더 본다. 능력 함수에서 현재의 f(x) 값보다 도함수 f'(x)를 말이다.

다시 말해, 최신 자바스크립트나 HTML5 API 지식이 필요하지 않으니까 당장 그런 걸 모르는 사람도 OK 하고 뽑는 게 아니다.
오히려 그 반대로.. 하나도 모르는 상태로 입사했더라도 현업에서 그런 것쯤은 30분 만에 즉석에서 공부하고 숙달될 능력이 있으니까 뽑는다는 뜻이다. 요구 사항이 훨씬 더 고차원적이다.

컴공과 수학의 관계는 어떨까? 물론 완벽하게 동치는 아니다. 기하 알고리즘을 구현하고 있는데 삼각형 넓이나 세 점의 방향을 구하는 공식, 3차원 공간에서 두 벡터에 대한 나머지 기저를 구하는 세부적인 외적 공식 같은 거야 당연히 까먹을 수 있다. 하지만 기억이 안 나면 당장 검색이라도 할 수 있으면 아무 문제될 것 없다.

단지, 수학은 그렇게 문제를 쓱쓱 풀어 나갔던 경험, 단 한 가지 경우라도 놓쳐서는 안 되고 논리적으로 완벽해야 한다는 그 관념이 나중에 프로그램을 짜는 데 낯설지 않은 정신적 자산으로 작용할 수 있다고 본다.
물론 그런 관념이 오로지 반드시 학창 시절의 수학 문제 풀이를 통해서만 형성될 수 있다는 건 아니겠지만 말이다. 기본적인 머리가 있고 필요를 느끼면 결국은 나중에 다른 경로를 통해서라도 적응은 하게 돼 있다.

어휴.. 나도 말은 이렇게 써 놨지만.. 당장 어떻게 풀어야 할지 모르는 어려운 문제를 대면하면 이게 도대체 지금까지 수업 시간에 배웠던 기본 수학 공식이나 법칙과 무슨 관계가 있고 무엇부터 적용해야 할지 막막한 게 많다. 맨날 이런 기억과 경험만 쌓이다 보면 그 누구라도 수학이 싫어질 수밖에 없고 수학을 포기할 수밖에 없을 것이다.. -_-;; 세상에는 나랑 나이 차이도 별로 안 나던 시절에 그런 문제를 생각해 내고 '만든' 사람도 있구만.. 참 자괴감이 든다~!!

Posted by 사무엘

2017/10/22 19:35 2017/10/22 19:35
, , , ,
Response
No Trackback , 4 Comments
RSS :
http://moogi.new21.org/tc/rss/response/1419

Trackback URL : http://moogi.new21.org/tc/trackback/1419

Comments List

  1. boolsee 2017/10/23 09:11 # M/D Reply Permalink

    사무엘님께서 이런 글을 쓰실 줄이야! 조금 당황스럽습니다. :) 제 관점에서는 사무엘님도 대.단.하.신 네임드 중 한 분이십니다만....
    글 내용에는 많은 부분에서 공감합니다. 나이가 들어가면서 나만 정체되어 있다거나 특별한 성과가 없다고 느껴지거든요.사실이 그런가는 차치하고 내 스스로가 한없이 작아지는 느낌? :)
    사람 사는 생각이 비슷한가 봅니다.

    1. 사무엘 2017/10/23 11:00 # M/D Permalink

      제가 본문에서 언급된 다른 사람들만치 공부 잘하고 머리가 빨리 잘 돌아갔으면 지금 겨우 날개셋 정도의 프로그램은 10년 안에 10.0까지 다 만들고 학위도 다 마치고 현재는 딴 일을 하고 있지 싶습니다.. ^^;;
      저도 제 자신이 한없이 작다는 느낌을 늘 받습니다.

  2. 허국현 2017/10/28 17:25 # M/D Reply Permalink

    1. 전에 친척 분이 "IT는 매번 바뀌는데 도대체 어떻게 그걸 하는 거냐?"라는 질문을 하신 적이 있습니다. 구원 받으신 분이라 이렇게 답했습니다.

    "해 아래 새 것이 없다는 성경 구절처럼 기술은 바뀔 지 몰라도 사람은 바뀌지 않습니다. 사람에 집중하면 생각보다 어렵지 않습니다.

    또한 새로운 것이 계속 추가되는 것 같아 보여도, 기존에 있던 것을 개선하거나, 서로 베끼는 경우도 많습니다. 너무 새로울 경우 배울 게 많아져서 오히려 시장에서 죽어 버립니다."

    이해하시는 눈치는 아니었습니다.

    사실 이것처럼 프로그래밍에도 중복되는 것이 워낙 많다 보니 김상형님 책 수집하다 보면, 봤던 예제 또 나오고 또 나오고 합니다. 플랫폼과 언어만 바뀌어서...

    오히려 요즘 나오는 책들은 C언어나 Windows API 책들에서 보이는 "경험해 보지 않고서는 절대 적을 수 없는 조언들"이 별로 없어서 많이 아쉽습니다.

    김상형님이 그게 가능한 것은 프로그래밍 언어 습득 능력보다도 글을 쓰고 책을 쓰는 능력이 있기 때문이 아닐까 합니다.

    2.

    이 글의 요약본(?) 내지 시작이었던 페북 글에도 말씀 드렸던 것처럼, 지금보다 10배 정도 머리가 좋아진다고 해도, 후회하고 자신이 작다고 느껴지는 시점만 늦어질 뿐일 것입니다.

    지금 고민하는 거야 쉽겠지만, 더 어려운 것을 고민하고 있겠지요.

    솔로몬도 공부가 힘들다는데 내가 쉬우면 그게 공부인가? 그러면 내가 공부를 열심히 안 하고 있는 거겠지... 그게 제 생각입니다.

    1. 사무엘 2017/10/28 19:43 # M/D Permalink

      이 글보다 수 개월 이상 먼저 페북에 올라왔던 요약본(?)을 다 기억하고 있고, 김 상형 님 책을 그렇게 다 수집해서 반복 패턴을 파악하실 정도이니.. 허 국현 님의 학습 능력과 기억력도 정말 남다른 것 같습니다..! ㄷㄷㄷ
      요즘은 어떻게 지내시나 궁금하네요..!

Leave a comment

C/C++, 자바, 파이썬 등 프로그래밍 언어를 하나 배워서 초보 딱지를 뗄 정도가 되면, 프로그래밍을 할 줄 모르던 때보다 컴퓨터를 훨씬 더 유용하고 창의적으로 활용할 수 있게 된다. 초보 딱지를 뗐다는 건 한 변수로부터 복수 개 + 다중 계층 형태로 된 숫자나 문자열에 접근하는 '복합 자료형(composite type)'을 다룰 수 있고, 함수와 반복문과 재귀호출로 반복 절차를 구현할 수 있음을 의미한다. 거기에다 Windows API에 대한 약간의 지식이 필요하다.

뭐, C/C++보다 더 고수준 언어를 쓴다면 날포인터(raw pointer)를 써서 수동 메모리 관리까지 직접 다룰 일은 없겠지만, 거기는 거기 고유한 방식으로 리스트나 시퀀스처럼 복합 자료형을 제공하는 게 있을 것이다. 복합 자료형과 실행 시간 조건부 반복 및 분기가 튜링 완전한 계산 모델의 본질이며, 자연어로 치면 그냥 Hello world나 I am a boy를 넘어서 길고 복잡한 안은 문장과 이어진 문장을 자유자재로 구사하는 것과 같다.

모든 사람이 전산학과 코딩을 전공으로 삼아 생업 수준으로까지 할 필요는 전혀 없다. 굳이 번듯한 GUI 갖추고 제3자가 쓸 만한 번듯한 소프트웨어를 개발하는 경지에 이르지는 않아도 된다. 그냥 일상생활에서 내가 당면한 문제를 코딩으로 스스로 해결하는 '자가용' 프로그래밍 스킬만으로 충분하다. 원하는 웹사이트 내용을 크롤링 해서 텍스트를 추출하거나, 방대한 무슨 데이터 파일을 내 입맛에 맞게 변환· 가공하거나, 특정 시간대에나 주기적으로 컴퓨터로 하여금 특정 작업을 수행하게 하는 게 대표적인 예이다.

물론 프로그래밍을 공부하는 대신, 그런 일을 수행해 주는 유틸리티(특히 매크로 같은..)를 찾아서 사용법을 익히는 것도 방법이 될 수 있다. 그러나 본인의 경우는 간단한 건 그냥 직접 만들어 쓴다. 그게 더 빠르다.
옛날 직장에 다니던 시절엔 이튿날 아침 9시 3분 전에 회사 인트라넷에 접속해서 출근 도장을 자동으로 찍게 하는 프로그램을 짜 놓고 퇴근 후, 정작 나는 다음날 느긋하게 출근하기도 했었다. 이 정도 잔머리야 뭐 직업 프로그래머라면 완전 껌(piece of cake)일 것이고, 반대로 회사에서 작정하고 오토의 부정 사용을 단속하려 한다면 키보드 드라이버 차원의 보안 프로그램들로 직원들의 컴을 도배시켜 놓겠지만 말이다.

잡다한 서론이 좀 길어졌으니 본론으로 들어가도록 하겠다. 컴퓨터 프로그래밍에는 저렇게 고정된 입력에 대해서 언제나 고정된 답만 출력하는 작업 말고 의외로 재미있고 유용한 분야가 있는데, 바로 난수(random number) 생성을 이용한 시뮬레이션, 무작위 표본 추출 등이다.

이 글은 난수 생성 방법 자체에 대해 다루지는 않을 것이다. 그래도 말이 나왔으니 잠시 언급하자면, 난수란 그 정의상 등장 패턴을 예측할 수 없으면서(혹은, 몹시 어렵고) 각 숫자들의 등장 빈도에 치우침이 없어야 할 것이다. 파이나 자연상수 같은 유명한 무리수가 파면 팔수록 끝없이 생성하는 소수점들은 난수의 범주에 든다고 볼 수 있으려나 모르겠다.

품질 좋은 난수를 값싸고 빠르게 많이 생성하는 알고리즘에 대한 수요는 매우 많으며, 이건 정수와 관련된 응용 수학에서 매우 중요하게 다뤄지는 분야이다. 옛날에 CACM에서 Random numbers: good ones are hard to find라는 논문을 봤던 기억이 나는데... 거기는 그 정도 퀄리티의 논문이 그야말로 상상도 할 수 없을 정도로 옛날에(1988년!) 이미 게재되었다는 게 전율이 느껴진다.
시뮬레이션도 좋고 각종 게임도 좋지만 추첨 역시 단순 유흥이 아니라 그야말로 사람의 인생과 진로를 결정하는 매우 사무적이고 크리티컬한 분야에 쓰인다.

추첨의 가장 간단한 형태는 A명의 사람에게 B개의 물건을 무작위로 배분하거나(단, A>B) 그냥 B명을 무작위로 답정너 선발하는 것이다. 그리고 이를 일반화하면 단순히 "당첨 B개 vs 꽝 A-B개"라는 이분법적인 상태를 넘어서 3개 이상의 상태를 배분하는 것도 생각할 수 있다.
이런 추첨을 종이와 연필만으로 수행하는 대중적인 방법 중 하나는 사다리 게임이다. 이 정도 추첨이야 언제 어디서든 필요할 때 하라고 사다리를 무작위로 생성해 주는 스마트폰 앱도 진작에 나와 있다.

그러나 현실에서는 이보다 더 복잡한 조건을 주고 추첨을 해야 할 때도 있다. 조 추첨이 대표적인 예인데, 각 조별로 인원과 성별이 비록 조의 수로 나눠 떨어지지 않더라도 최대한 균일하게 유지돼야 하며, 그 밖에 구성원들별로 다른 내부 속성도 최대한 균일하게 유지돼야 한다.
본인은 고등학교 시절에 반 내지 학교 행사 때 테이블별 인원 추첨을 컴퓨터 프로그램을 짜서 실시한 적이 있다. 하긴, 반 편성 자체도 일단 컴퓨터가 뒤섞어 놓은 결과에다가 각 반 담임들이 보정을 해서 뽑는다고 들었다. 가령, 문제아들은 한 반에 몰리지 않고 최대한 서로 다른 반에 찢어지게 말이다.

그 뒤 본인은 최근에는 교회 청년부의 소그룹 기도 모임의 인원을 분기별로 새로 추첨해 주는 프로그램을 작성했다.
이 역시 기본적으로 조별 인원과 성별부터 균등하게 맞추지만, 거기에다가 모임에 활발히 참여하는 사람과 그렇지 않은 사람도 나눠서 특정 성향의 사람이 한 조에 너무 몰리지 않고 최대한 분산되게 하는 조건을 추가했다.
그리고 또 중요한 것으로, 동일 집안의 친형제· 친자매· 친남매는 같은 조에 결코 걸리지 않게 했다. 흥미롭지 않은가?

처음에 인원과 성별은 무조건 균등하게 나오게 틀을 먼저 짜서 했다. 그러나 나머지 필터링은 알고리즘으로 구현한 게 아니라 무식한 방법을 썼다. 추첨 결과가 조건을 전체 만족하는지 검사해서 안 그러면 그냥 빠꾸 시키고 될 때까지 추첨을 다시 한다. 그러니 이건 프로그램의 실행 종료와 성공 여부를 전적으로 난수 생성 알고리즘의 품질에다 맡기는 셈이다.

물론 이렇게만 해도 소규모 인원의 조편성 결과쯤이야 운이 나빠 봤자 몇십 번 정도 뺑뺑이 만에 답이 즉시 잘 튀어나온다. 허나, 진지한 프로그램이라면 추첨 결과에 anomaly가 존재하면 조의 인원을 무작위하게, 적절하게 교환하고 보정을 해서 그걸 해소해야 할 것이다. 난수 생성 결과와 무관하게 수행이 유한 시간 만에 끝난다는 게 보장되는 알고리즘으로 말이다.

더 나아가면 이렇게 추첨이라는 computation을 위한 범용적인 '로직 선언형 프로그래밍 언어'를 생각할 수 있을 것 같다. 어찌 보면 SQL처럼 select A from B where 같은 문법 구조를 가질 수도 있겠다. 10명의 인원에다 무엇을 배당하되 무엇과 무엇에는 무엇이 같아서는 안 되고..
마치 "A와 B의 사이에는 C가 있지 않다. C의 오른쪽에는 D가 있다." 이런 단서들 주고 나서 "A~D의 가능한 정렬 순서는 무엇인가?" 이런 문제를 풀듯이 추첨 조건을 쫙 명시할 수 있다.

모든 조건의 충족이 불가능하다면 무식하게 무한 루프에 빠지는 게 아니라 저 조건들만 분석해 보고는 일찌감치 "성립 불가능, 답 없음"이라고 에러가 깔끔하게 튀어나와야 한다.
조건들 중에는 일단 추첨 뒤에 사후 보정을 해야 하는 것도 있겠지만, 여러 가지 속성 변수들을 균등하게 분할하는 것은 변수의 개수만큼 n차원 공간을 만들어서 거기에다가 차곡차곡 무작위로 숫자들을 채워 넣는 선형대수학 같은 방법론을 동원해서 구현할 수도 있을 것 같다. 아무튼 추첨· 배분과 관련된 수학 패키지나 프로그래밍 언어 솔루션이 있는지 궁금하다.

그리고 다음으로.. 컴퓨터 추첨은 추첨 알고리즘에 인위적인 조작이 없다는 걸 어떻게 보장하느냐고 결과에 대한 불신이 있을 수 있다.
이걸 해소하기 위해서는 제3자 참관인을 두는 게 바람직할 듯하다. 그래서 1부터 N회 중 가추첨을 몇 번 할지를 결정하게 한 뒤, 그 횟수를 공언한다. 그리고 그 횟수만큼 그 사람이 실제로 추첨을 돌리고 N회째의 결과를 최종 결과물로 선택하는 것이 모두에게 공정할 것 같다.

프로그램을 개발하는 사람 입장에서는 몇 회째에 조작된 결과를 내놓아야 할지 알 수 없으며, 참관인은 자기가 원하는 추첨 결과가 나왔을 때가 아니라, 먼저 약속했던 횟수만큼만 가추첨을 돌리다가 최종 결과에는 승복해야 한다. 그리고 가추첨의 결과도 계속 공개되므로 각 가추첨의 결과가 충분히 무작위하지 않고 이상하다면 이의 제기가 가능하다.

빵 같은 걸 두 사람이 먹게 반으로 나눌 때, 한 사람은 칼로 빵을 나누고 다른 한 사람은 나눠진 결과물 중 원하는 것(= 더 큰 것)을 취사선택하게 한다면 그야말로 두 사람이 모두 만족하는 결과가 나올 수밖에 없을 것이다. 이와 비슷한 시스템을 구현하는 것으로 논란을 잠재우는 게 합리적이어 보인다.

Posted by 사무엘

2017/07/29 19:33 2017/07/29 19:33
, , ,
Response
No Trackback , 4 Comments
RSS :
http://moogi.new21.org/tc/rss/response/1387

Trackback URL : http://moogi.new21.org/tc/trackback/1387

Comments List

  1. 경헌 2017/07/30 05:05 # M/D Reply Permalink

    > 더 나아가면 이렇게 추첨이라는 computation을 위한 범용적인 '로직 선언형 프로그래밍 언어'를 생각할 수 있을 것 같다. 어찌 보면 SQL처럼 select A from B where 같은 문법 구조를 가질 수도 있겠다. 10명의 인원에다 무엇을 배당하되 무엇과 무엇에는 무엇이 같아서는 안 되고..
    > 마치 "A와 B의 사이에는 C가 있지 않다. C의 오른쪽에는 D가 있다." 이런 단서들 주고 나서 "A~D의 가능한 정렬 순서는 무엇인가?" 이런 문제를 풀듯이 추첨 조건을 쫙 명시할 수 있다.

    이거 프롤로그 언어가 딱일거 같은데요? ㅎㅎ

    흔히 아인슈타인 문제라고 하는 것 https://ko.wikipedia.org/wiki/%EC%95%84%EC%9D%B8%EC%8A%88%ED%83%80%EC%9D%B8%EC%9D%98_%ED%8D%BC%EC%A6%90

    이런걸 말 그대로 저 정보를 그대로 선언해서 풀 수 있으니까..
    조건을 몇 개 덜 주면 말씀하신대로 조건을 만족하는 모든 조합을 출력하는 식으로도 쓸 수 있을거 같네요.

    1. 사무엘 2017/07/30 14:44 # M/D Permalink

      네, 정확한 말씀이십니다. ^^ 프롤로그 언어 자체를 저렇게 추첨 내지 조합 나열식으로 활용할 수 있으려나 모르겠어요.
      답을 딱 구하는 건 방정식을 푸는 것이고, 조건을 덜 줘서 모든 조합 출력하는 건 부등식을 푸는 것과 비슷할 테니까요~
      아인슈타인의 퍼즐은 아마 아인슈타인 본인이 만든 문제는 아닌 것 같지만 그래도 유명하지요. 여기 홈페이지에도 제가 15년 넘게 전에 만들었던 백트래킹 문제 풀이 소스가 있습니다. http://moogi.new21.org/src4.htm

  2. 허국현 2017/07/30 15:42 # M/D Reply Permalink

    1. 폰 노이만은 이런 랜덤 관련 연구를 별로 안 좋아했다고 하네요. 도박의 느낌이 많아 나서인 것 같다는 평이 지배적입니다.

    2. 난수 관련 문제는 아니지만, 예전에 게임 개발에 한참 관심 있을 때, 그래픽 관련 논문들 출처 연도를 보다 보면 1970 같은 숫자도 나와서, "도대체 컬러 TV도 없을 것 같은 시절에 왜 그런 알고리즘에 관심을 가진 사람이 있었던 거지?"라는 생각을 해 본 기억이 납니다.

    3. Keyboard Hook을 쓰는 것보다는 훨씬 편하기 때문에 Python 등과는 별개로 Autohotkey는 배워 둘만 하다는 느낌이 들더라고요.

    1. 사무엘 2017/07/30 19:59 # M/D Permalink

      반갑습니다. ^^

      1. 폰 노이만은 인간 컴퓨터 괴수인 데다 순수 수학보다는 응용 수학의 달인이었는데.. 그러면 간단한 xor과 비트 rotation 연산만으로 아스트랄하게 펼쳐지는 암호화· 난수· 해쉬 함수 같은 바닥에서도 흥미를 갖고 펄펄 날았을 것 같은데 그건 좀 의외의 취향과 행적이네요. ^^
      하긴, 뉴턴도 직접 도박까지는 아니고 뭐 투자 잘못해서 돈 왕창 날리고 나서는 "과학 법칙은 복잡하더라도 분석과 파악이 되지만 사람 심리는 도저히 노답이다.." 학을 뗐다는 일화도 전해지죠.

      2. 3차원 그래픽 테크닉이라든가 Doom, Quake에서 사용하는 BSP 맵 자료구조 같은 것도 이론은 다 그 까마득한 옛날에 이미 연구된 것들이죠. 기계값이 서민들이 도저히 범접할 수 없을 정도로 비쌌던 그 시절에 그런 걸 연구한 사람들이 진정한 선구자들입니다.

      3. Windows 3.x 시절에 있었던 레코더 생각이 나네요. 개인적으로 키· 마우스 매크로 자동화는 마치 화면 캡처 기능만큼이나 운영체제 차원에서 유틸리티가 제공돼야 한다고 생각합니다만.. 오늘날 운영체제는 그런 기능이 빈약한 게 좀 아쉽습니다.

Leave a comment

란체스터의 법칙

A와 B라는 두 집단이 서로 패싸움을 시작했다. A는 전투원이 5명이고 B는 4명이다. 그런데 양 진영의 모든 전투원들은 체력· 정신력· 무장 등등이 완전히 동일하며, 기습 가능성이라든가 지형적인 유불리, 엄폐물 같은 것도 없이 탁 트인 개활지에서 순수하게 힘과 힘만이 충돌하는 형태로 싸우게 됐다고 치자. 싸움은 둘 중 한 진영의 전투원들이 몽땅 죽거나 중상을 입어서 전투력을 상실할 때까지 계속된다. 그렇다면 이 싸움의 결과는 어찌 될까?

마오 쩌둥이던가 스탈린이던가.. 인권 쌈싸먹은 독재자답게 "전쟁 나서 1억 인구가 죽는 것쯤은 별 일 아니다. 사람이야 또 낳으면 되니까. 적군이 병력이 1억이면 우리는 1억에다 한 명만 더 붙여서 이기면 된다" 그런 요지의 무지막지한 말을 한 적이 있었다. 정확하게 누가 언제 한 말인지 출처 확인이 잘 안 되네, 분명 본 기억은 있는데..

그런데 저건 병신 같지만 묘하게 설득력이 있는 말이다. 외적인 요인이 차이가 전혀 없고 완전히 동일하다면 상식적으로 생각했을 때 쪽수가 한 명이라도 더 많은 집단이 필승하고 부족한 집단은 필패할 것이다.
위의 경우라면 B가 지고 A가 이기는 것 자체는 따 놓은 당상이다. 단지 문제는 A가 B를 얼마나 너끈히 이기느냐, 어느 정도의 피해를 입고 승리하느냐로 귀착된다.

그 답은 A와 B가 어떤 방식으로 싸우느냐에 따라 달라진다.
조폭들 패싸움처럼 기껏해야 일대일로 근접해서 냉병기를 사용하는 싸움이라든가, 총이라 해도 18세기 전열보병 전술처럼 비현실적일 정도로 너무 신사적으로 일대일 턴제로 싸우는 거라면 말 그대로 일대일로 상쇄하고 남은 병력만이 생존자가 된다. B는 전멸이요, A는 A-B에 해당하는 인원이 남는다. 고로 5:4의 싸움이라면 한 명만 남는 거다. 이것을 일명 란체스터 제1법칙이라고 한다.

그러나 점 vs 점이 아니라 면 vs 면 단위로 실시간으로 부딪치는 현실의 전투에서는 다구리가 더 대규모로 가능하며 병력의 작은 차이가 훨씬 더 큰 차이를 야기한다. 설정상 한 집단의 전투력은 병력에 비례해서 나오게 돼 있는데 그 전투력 자체가 병력의 손실로 인해서 차츰 감소한다. 두 변수가 같이 변화하면서 비선형적인 구도를 만든다는 뜻이다. 그래서 처음부터 병력과 전투력이 열세였던 집단은 그 감소폭이 더욱 커지면서 전멸에 이르지만, 우세 집단이 받는 대미지는 시간이 흐를수록 더욱 작아진다. 전투력도 부익부 빈익빈으로 치닫는다!

그래서 답부터 말하자면, 이런 현실의 싸움에서 A와 B가 붙으면 B가 전멸한 뒤 A는 한 명만 남는 게 아니라 이론적으로 3명이나 생존해 있게 된다. B는 자기 진영 4명이 전멸하는 동안 A를 2명밖에 못 죽인다는 것이다. 공식으로 표현하면 단순한 A-B가 아니라 sqrt(A^2 - B^2)이다.
마치 직각삼각형 세 변의 길이와 같은 구도가 된다. 그렇다면 5명 vs 4명이 아니라 13명 vs 12명이 붙으면, 12명 팀은 전멸하고 13명 팀은 8명만 죽어서 5명이 남는다.

이것은 란체스터 제2법칙이라고 명명되어 있다. 영국의 항공 공학 엔지니어가 1차 세계 대전의 양상에서 착안하여 고안했다.
스타크 같은 전략 시뮬 게임에서 드라군, 마린, 히드라 같은 원거리 공격 유닛들을 서로 마주보게 해서 어택 땅으로 싸움을 붙여 보면 이 법칙이 의외로 굉장히 잘 적중한다고 한다. 란체스터의 법칙에 대해 소개해 놓은 타 블로그 글들을 검색해 보면 전략 시뮬 게임으로 실험을 해 봤는데 높은 적중률을 보고 놀랐다는 말이 많이 나온다. 1억 명에다가 딱 한 명만 더 보태서 이기면 된다는 말이 그저 허세만은 아닌 셈이다.

란체스터 제2법칙이 어째서 성립하는지를 엄밀하게 논하려면 삼라만상의 변화량을 기술하는 끝판왕 도구인 미분방정식을 동원해야 한다.
시각 t에 대해서 A 진영의 병력을 나타내는 함수 f(t), B 진영의 병력을 나타내는 함수 g(t)를 정의하자.
위의 예에서는 전투 전의 초기 상태 t=0에 대해 f(0)=5, g(0)=4가 될 것이다. 뭐, 일반화해서 f(0)=a, g(0)=b라고 잡아도 된다.

전투의 진행으로 인해 f(t), g(t) 모두 병력이 감소할 것이다. 그런데 그 감소하는 변화량이 바로 상대방 함수의 함수값과 같다. d f(t) / dt = -g(t) 요, d g(t) / dt = -f(t)라는 뜻이다.
그렇다면 이 f와 g는 도대체 어떻게 생겨먹은 함수일까? 0보다 큰 t에 대해서 g(t)=0이 되고(B 진영의 전멸) 그 정의상 동시에 f'(t)=0도 되는 지점이 있을 것이다. 그 t가 얼마인지는 중요하지 않겠지만, 이때 f(t)의 값을 a와 b에 대해서 구하면 란체스터 제2법칙을 유도할 수 있을 것이다.

f의 도함수가 -g이고 g의 도함수가 또 -f라니.. 일단 얘는 미분을 짝수 번 반복하면 도함수가 자기 자신으로 돌아오는 뭔가 골때리는 함수 형태가 될 듯하다. 즉, 4배수 주기로 제자리로 돌아오는 삼각함수보다는.. cosh, sinh 같은 쌍곡선함수 형태가 될 것 같다. 걔들은 미분을 하면 cosh, sinh, cosh ... 이렇게 반복되는데, 문제의 저 함수는 f, -g, f, ... 이렇게 반복된다.

그래서 답을 구해 보면.. a>b여서 f가 더 우세한 진영을 나타낸다는 걸 염두에 뒀을 때
2*f(x) = (a+b)/e^x + (a-b)*e^x 요, 2*g(x) = (a+b)/e^x - (a-b)*e^x 가 된다. (2를 곱한 게 저런 것이므로 전체를 2로 나눠 줄 것)
e^x와 e^x의 역수를 절반씩 적절히 더하거나 빼는 cosh / sinh 함수를 상수배/평행이동만 한 형태인 걸 알 수 있다. f는 cosh에 대응하고 g는 그냥 sinh가 아니라 -sinh가 된다.

cosh는 현수선을 나타내는 함수이기도 하다. 그 말인즉슨 A와 B가 싸울 때 A의 피해 양상은 빨랫줄이나 쇠사슬이 아래로 축 늘어진 것과 비슷한 양상으로 스무스하게 감소할 거라는 뜻이다. 실제로 그런지 확인해 보자.


사용자 삽입 이미지

사용자 삽입 이미지
바로 이것이 5명과 4명, 또는 엄밀히 말해 5:4 비율의 병력이 맞붙었을 때 란체스터 제2법칙에 따라 예상되는 병력의 변화 양상이다!
g(x)=0이 되는 시점은 x= ln( (a+b)/(a-b) )/2 가 되며, (a=5, b=4일 때는 저 값은 대략 1.1)
이때 f(x)를 구해 보면 (a+b)/sqrt( (a+b)/(a-b) )가 나오고 식을 정리하면 진짜로 sqrt(a^2 - b^2)가 나온다.
임계점 이후부터는 g는 음수가 나오고 f는 감소가 아니라 오히려 증가하기 시작하지만, 이건 현실에서는 아무 의미 없는 추세일 테니 제끼면 된다.

더 직관적인 비유로 설명하자면.. 5:4가 붙어서 곧이곧대로 1명만 남는 싸움, 즉 란체스터 제1법칙은 y=1이라는 상수 그래프를 떠올리면 된다. 여기서 x가 4부터 0까지 가는(B진영) 동일 면적(= 정적분)을 5에서부터(A진영) 시작한다면 1에 도달한다.

그러나 란체스터 제2법칙은 y=1이 아니라 y=x라는 가변적인 그래프에 대응한다. 여기서 x가 4부터 0까지 가는 B진영의 면적 8(밑변과 높이가 모두 4인 삼각형)을 5에서부터 시작한다면.. 1이 아니라 3에서 멈추게 된다. 윗변 3, 아랫변 5, 높이 2인 사다리꼴의 넓이가 8이 되니까 말이다.
이를 일반화하면, 0부터 B까지 y=x를 정적분한 값은 sqrt(A^2-B^2)에서부터 A까지 정적분한 값과 같다. 이렇게 이해해도 된다.

전쟁이라는 건 여기저기 가성비를 따지면서 지킬 것과 버릴 것을 가리고 작전을 잘 짜야 이길 수 있다. 즉, 경제· 경영과도 밀접한 관계가 있다. 그렇기 때문에 오늘날 란체스터의 법칙은 군사학보다는 경제학 쪽에서도 기초 이론으로 더 중요하게 다뤄진다. 포병 장교에다 수학 박사 출신인 지 만원 박사 같은 분이 아마 이런 분야의 최고 전문가가 아닐까 싶다.
이 법칙은 스플래시 데미지나 사이오닉 스톰-_- 같은 변수가 있지 않은 한, 왜 일반적으로는 "뭉치면 살고 흩어지면 죽는다"가 성립하는지를 무식하게 시행착오 겪을 필요 없이 수식만으로도 잘 설명해 준다. 5:4로만 붙여도 저 그래프와 같은 처참한 결과가 나오지 않던가?

더 나아가서 어지간히 절체절명의 위급한 상황이 아닌 이상, 스타에서 유닛이 생성되는 족족 적진으로 찔끔찔끔 축차투입을 해서는 절대 안 되며 캐리어 같은 유닛도 반드시 일정 기수 이상 모아야 제 성능이 발휘된다는 것을 보여준다.
또한 전쟁이 나면 전투 직전에야 양 진영이 모두 사기 진작이 매우 중요하기 때문에 "마지막 하나까지 결사항전" 운운하지만.. 대세를 도저히 뒤집을 수 없을 정도로 승부가 너무 기울고 100% 개죽음밖에 선택의 여지가 없을 때는 불가피하게 꼬리 내리고 항복도 하는 것이다.

이상. 란체스터 법칙 하나 갖고 미분방정식에, 쌍곡선함수에 별 얘기가 다 나왔다.
다만, 현실의 전장에서는 수학 숫자놀음 나부랭이보다 예측할 수 없는 외부 변수가 훨씬 더 많이 존재하기 때문에 란체스터 법칙이 절대적인 만능 장땡인 건 아니다. 겉으로 드러나는 병력 열세를 극복하고 B가 A를 이긴 사례도 역사엔 얼마든지 존재한다는 것도 생각할 필요가 있다.
그러니 성경에서 하나님께서 기드온에게 병사 수를 32000명에서 거의 1% 수준인 300명으로 일부러 줄여 버리고도 오히려 전투를 승리로 이끄신 것이 대단한 이야기인 것이다(삿 7). 진짜 300의 원조는 무슨 영화에 나오는 스파르타 군대가 아니라 저 군대였던 셈이다.

Posted by 사무엘

2017/02/18 08:32 2017/02/18 08:32
, ,
Response
No Trackback , 2 Comments
RSS :
http://moogi.new21.org/tc/rss/response/1328

Trackback URL : http://moogi.new21.org/tc/trackback/1328

Comments List

  1. spartan10 2017/02/18 22:01 # M/D Reply Permalink

    용묵님 오랜만에 들리네요~ 반갑습니다~ 간만에 왔는데도 용묵님은 여전히 활동 잘 하고 계시네요~ 글 대충 봤을때 미분에 싸인 코싸인 그런게 잔뜩 나와있길래 뭔가 했더니@.@ 읽다보니 역시 흥미진진한 내용이네요 ㅎㅎ 5:4병력싸움~ 스타 유닛얘기 나오고 ㅎㅎ 다만? 요새애들은 롤도 그렇고 얼마전에 오버워친가 나와서 게임하면 그 둘 얘기가 가장 많이 나오는걸로 알고 있는데~ 용묵님도 이제 연세?가 있으시다보니~ 스타 얘기가 ㅎㅎ 세월이 무상하군요 저도 가끔 피방가면 스타나 좀 몇판하지 롤같은건 통 뭔재민지도 모르겠고 할줄도 모르고 ㅠㅠ 아 아재여~.~ 잡소리 또 늘어놨네요 하여간 간만에 반갑습니다! 늦었지만 새해 복 많이 받으시고 2017년에도 건강하시고 화이팅하세요^^

    1. 사무엘 2017/02/19 02:33 # M/D Permalink

      그러게 말입니다. 스타 2도 아니고 1에서 시간이 정지했으니 저도 이제 영락없는 아재가 됐네요. ^__^
      저도 너무 용량 커지고 사양 높아지고 온라인 위주로만 돌아가는 요즘 게임들은 잘 안 하게 돼서.. 서든어택 2가 작년 여름에 하도 대형 흑역사 사고를 쳐서 망정이지, 안 그랬으면 저는 롤이니 오버워치니 같은 건 이름도 못 들어 봤을 가능성이 높습니다.
      저도 댓글, 방명록, 메일 등에다 답변을 분산해서 올렸습니다. ㅎㅎ

Leave a comment

* 옛날 2014년에 썼던 글을 관련 내용을 크게 보강하여 리메이크 한 것이다.

디지털 컴퓨터라는 게 0과 1, 2진법을 사용하다 보니, 2^n이라 하면 정보량과 관련해서 특히 컴퓨터쟁이들에게 아주 친근한 수이다.
그런데 2^n보다 1 더 크거나 작은 수가 소수라면 제각각 수학적으로 좀 독특한 의미를 갖게 된다.

1.
2^n-1 형태인 수를 메르센 수라고 한다. n층짜리 하노이의 탑의 원반을 옆으로 모두 옮기기 위해서는 이 메르센 수만치 지수함수적으로 증가하는 횟수만치 원반을 이동시켜야 한다. 그리고 메르센 수 중에서 소수인 놈을 메르센 소수라고 한다.
얘가 소수이려면 n도 반드시 소수여야 한다. n을 a와 b라는 두 자연수의 곱이라고 생각하고 2^ab - 1을 인수분해해 보면 그래야만 하는 구조적인 이유를 알 수 있다.

사용자 삽입 이미지

(2^ab는 (2^a)^b 와 같다. 2^(a+b)하고 혼동하지 말 것.)

n이 합성수여서 2 이상인 두 자연수 a, b의 곱으로 나타내어질 수 있다면 2^n-1은 빼도 박도 못하고 무조건 합성수가 돼 버린다. 전체 결과가 소수가 되려면 a는 1이고 b는 소수로 귀착되는 것밖에 가능성이 없다. 비록 이 조건이 만족된다고 해서 2^n-1이 언제나 반드시 소수가 된다는 보장은 없지만 말이다.
가장 작은 반례는 2^11-1이다. 11은 소수이지만 2047은 23*89로 소인수분해 되는 합성수이다.

메르센 수는 2^n에서 1이 부족한 형태라는 특성상 2진법으로 나타내면 모든 자리수가 1이다. 컴퓨터에서 취급이 간편하기도 하고, 또 n의 소수 여부를 판정한 뒤에 곧장 무려 2^n-1이라는 방대한 수를 취급할 수 있다는 특성상.. 컴퓨터로 가장 큰 소수를 찾는 프로젝트는 대개 메르센 수를 대상으로 진행되곤 한다. 물론 실제로는 메르센 수가 아닌 소수도 많이 있으며, 반대로 메르센 수 중에서도 메르센 소수는 매우 드물다는 점을 감안할 필요가 있다.

저런 거 찾는 건 거의 애니메이션 렌더링과 같은 급으로 상상을 초월하는 계산량으로 컴퓨터를 열받게 하고 혹사시키는 작업이다. 그나마 양만 많지 내부 과정 자체는 단순무식한 편이니 병렬화가 수월한 건 다행인 점이다.

메르센 소수는 짝수 완전수와 필요충분 관계로 정확히 대응하는 것으로 유명하다. (약수의 합이 자신과 같은 6, 28, 496 같은 수) 메르센 소수 2^n-1에다가 2^(n-1)을 곱하면 완전수가 나오기 때문이다. 괄호 순서에 유의할 것. 즉, 저기서 n에다 소수를 집어넣으면 된다. 천재 수학자 오일러가 모든 짝수 완전수는 이런 형태라는 것을 증명했다.
현재까지 메르센 소수는 약 50여 개가 알려져 있으나, 무한히 존재하는지는 불명이다.

2.
그럼, 다음으로 2^n+1의 경우를 생각해 보자. +1은 -1보다 더 자비심이 없다. n은 소수가 아니라 반드시 2의 거듭제곱 형태여야 그 값이 소수일 일말의 가능성이 생긴다. 이는 n의 소인수 중에 홀수가 절대로 존재해서는 안 됨을 의미한다. 아까 전과 비슷한 방식으로 2^ab + 1을 인수분해해 보면 그 이유를 알 수 있다.

사용자 삽입 이미지

n의 소인수에 홀수가 존재해서 그걸 b라고 설정하면 아까 -1일 때와는 부호만 미묘하게 다르게 저렇게 인수분해가 되며, 이 수는 100% 합성수임이 보장돼 버린다. (2^a - 1)이라면 a=1인 걸로 맞춰서 없앨 수라도 있지만, (2^a + 1)은 도저히 처분할 방법이 없다.

하긴, 고등학교 공통수학 수준의 인수분해 공식을 생각해 봐도, n이 홀수일 때에 한해서 (a^n + b^n)은 a+b로 나눠 떨어지며 인수분해가 된다. 나눠진 몫에 해당하는 항은 a^n에서 b^n으로 a와 b의 차수가 조금씩 늘고 줄고 부호가 교대로 바뀐다.
이를 일반화하면, n이 굳이 홀수가 아니더라도 6이나 10처럼 홀수 소인수가 포함돼 있으면(3, 5) (a^n + b^n)은 굳이 a+b가 아니더라도 (a^2+b^2) 같은 것으로라도 나눠 떨어지며 인수분해가 된다. 그렇지 않고 홀수 소인수가 전혀 없다면 +의 경우는 인수분해를 할 수 없다.

부연 설명 차원에서 인수분해된 식들이 전개되는 양상을 시각적으로 살펴보면 이러하다.
a^n - b^n은 n의 값과 관계없이 언제나 a-b로 나눠 떨어지며, 나눠진 몫의 항들은 부호가 모두 +가 유지된다. 전부 +인 항들이 한 칸 옆으로 물러간 채 -로 바뀌어서 전부 +/-가 상쇄돼 버리고 맨 앞의 +와 -만 남는다
++++
 ----
+...- (a-b)

하지만 a^n + b^n일 때는 +와 -가 교차하는 항들이 한 칸 옆으로 맞물려서 상쇄돼야 맨 앞과 뒤의 +가 남을 수 있다. 그러니 이때는 항이 홀수 개여서 양 끝이 +가 유지돼야 인수분해가 가능해지는 것이다.
+-+-+
 +-+-+
+....+ (a+b)

(쪼개고 쪼개도 분자 단위에서 계속 앞뒤로 + - 극을 갖는 자석 같아 보이기도 하고..;;)
이 두 경우를 모두 종합한 듯이 인상적인 상황은 (a^n - b^n)에서 n이 2의 거듭제곱 형태일 때이다. n=8인 경우를 예로 들어 보면, 이 식은 (a^4 + b^4)(a^2 + b^2)(a + b)(a - b)라고 아주 드라마틱하게 인수분해가 된다. n이 2의 거듭제곱이면 (a^n + b^n)은 -일 때와는 반대로 인수분해가 도저히 더 되지 않는 다항식계의 소수(?) 같은 존재가 된다.

그렇기에 2^n+1도 n이 반드시 2의 거듭제곱 형태여야만 구조적으로 인수분해가 되지 않고 소수일 가능성이 생기는 것이다. 그리고 2^(2^n)+1 형태인 수를 페르마 수라고 하며, 그 중 소수인 놈을 페르마 소수라고 한다. 간단하게 2^n-1로 정의되는 메르센 수와는 양상이 다르다.

그러니, 태생적으로 딱 봐도 페르마 소수는 메르센 소수보다도 더욱 드물 것 같이 생겼는데, 실제로 그러하다.
n에 비례해서 숫자가 넘사벽급으로 너무 폭발적으로 커지는 관계로, 페르마 소수는 n=0..4인 처음 겨우 5개밖에 알려져 있지 않다(3, 5, 17, 257, 65537). n이 아니라 2^n으로 계산한 것이다.

여기서 페르마란 "페르마의 마지막 정리" 내지 추측을 제시했던 17세기 프랑스의 그 엄친아 변호사 겸 아마추어 수학자를 가리키는 거 맞다..
페르마 자신은 저런 형태로 생성된 모든 수들이 소수일 거라고 1637년에 추측하였으나, 그로부터 100여 년 뒤인 1732년, 오일러가 n=5인 2^32+1은 소수가 아니라고 반증을 해 버렸다. 아까 그 메르센 소수와 완전수 관계를 증명한 그 오일러 말이다.
지금이야 그 정도 크기의 수는 컴퓨터로 소수 여부를 아주 간단히 판별할 수 있지만 오일러는 컴퓨터도 없던 시절에 저걸 도대체 어떻게 알아낸 걸까? 찰스 웨슬리가 찬송시 And can it be that I should gain을 쓰기도 전의 일이다(1738).

제곱근인 65536 이내의 모든 홀수들을 브루트 포스 식으로 일일이 주판 돌려서, 제자들까지 멀티코어로 동원해서 나눠 본 건 물론 아니고..
2^32 + 1의 소인수는 반드시 64k+1 의 형태라는 것을 어떤 계기로 알아내고는 찾았다고 한다. 범위를 많이 좁힌 것이다.
실제로 2^32 + 1은 641 * 6700417인데, 이는 (64*10+1)*(64*104694+1)이다.
그는 이를 일반화하여 페르마 수의 소인수는 반드시 "2의 거듭제곱의 a배 + 1"이라는 사실까지 정립했다.

n=5에 속하는 2^32+1에 이어 n=6 (2^64 + 1)의 경우도 합성수라는 게 추가로 밝혀진 건 오일러 이후로 또 100년이 넘게 지난 무려 1855년의 일이다(by Thomas Clausen). 나머지 페르마 수들도 대략 32까지 구해 보니 줄줄이 다 합성수라는 것이 계산을 통해 밝혀졌다. 페르마의 예상과는 정반대로 흘러간 셈이다.
그러니 65537을 끝으로 페르마 소수는 더 존재하지 않는 게 아닌가 추측되고 있으나, 이 역시 홀수 완전수의 존재 여부만큼이나 정식으로 증명된 것은 아니다.

메르센 소수가 짝수 완전수와 동치 관계이듯, 페르마 소수 역시 굉장히 의외의 곳에 큰 의미를 지니고 있다. 이것은 작도 가능한 정다각형의 특성과 관계가 있다. 변의 개수의 소인수가 2 and/or 페르마 소수들로만 이뤄진 정다각형은 눈금 없는 자와 컴퍼스를 이용해 작도 가능하다. 작도 가능한 수는 아무래도 사칙연산과 '제곱근'만으로 기술 가능한 수이니, 제곱근만을 연달아 적용하는 건 2의 거듭제곱만치 또 거듭제곱을 하는 것과 심상면에서 비슷해 보이긴 한다.

그렇기 때문에 작도 불가능한 최초의 정다각형은 정칠각형이며, 반대로 정17각형은 절차가 굉장히 복잡하고 까다롭긴 해도 작도 가능하다. 17은 페르마 소수이니까. 이걸 발견하여 증명한 사람은 오일러...는 아니고 18세기 독일의 천재 수학자인 가우스이며, 그것도 굉장히 어린 나이에 발견했다. sin 1도가 초월수가 아니라 대수적인 수이듯, cos 2*PI/17 역시 형태만 복잡할 뿐, 대수적인 수임을 의미한다.

사용자 삽입 이미지

(그림의 출처: 나무위키)
뭐, 이론적으로만 가능하다는 거지, 실제로 해 보면 누적되는 오차와 지저분한 보조선들 때문에 감당이 어려울 것이다. 하물며 정257각형과 심지어 정65537각형은? 이것도 이론에서나 작도 가능하다는 얘기다.

자, 지금까지 한 얘기들을 요약하면 다음과 같다.

  • a^n-b^n은 언제나 a-b로 나눠 떨어지며 2^n-1 역시 그런 꼴의 수이므로, 얘를 소수로 만들려면 a-b가 반드시 1인 상황을 만들어야 한다. 그리고 메르센 수에서 그 경우란 n이 소수인 경우밖에 없다.
  • 그리고 2^n+1의 일반형인 a^n+b^n은 아까처럼 한쪽 인수를 1로 만드는 게 불가능한 대신에, 인수분해 가능 여부가 n의 차수에 따라 조건부로 결정된다. 소수를 만들려면 물론 애초에 인수분해를 할 수 없는 상황을 만들어야 하며, n은 단순히 짝수인 정도를 넘어 소인수에 홀수가 전혀 없어야 한다. 그래서 n 자체가 2의 거듭제곱 형태인 것만 남는다.

그러고 보니 페르마뿐만 아니라 메르센도 17세기 동시대를 살았던 프랑스 사람이기 때문에 둘이 공통점이 있다. 메르센은 블레즈 파스칼의 스승이기도 했다. 프랑스, 독일 그쪽은 수학· 과학 쪽으로 그때로부터 지금까지 한가닥 하고 있는 대단한 동네이다.

* 소수 관련 여담

(1) 소수 자체가 안 그래도 수가 커질수록 (log n) / n 급의 스케일로 자연수에서 등장 빈도가 극도로 드물어진다. 그런데 그 소수들 중에서도 굉장히 까다로운 조건을 만족하는 메르센 내지 페르마 소수 같은 것들은 한계치 최대치가 존재한다 해도 이상할 게 없을 것이다. 굳이 수 자체가 특이한 게 아니더라도 2 간격으로 나란히 존재하는 쌍둥이 소수 쌍(5와 7, 11과 13, 17과 19..) 같은 것도 말이다. 그런데 한계치가 있다면 그 최대값이 알려져 있어야 할 텐데 그것이 수수께끼이다.

(2) 오일러의 업적 중에는 소수와 관련해서도 정말 살떨리는 것들이 많다. 자연수의 제곱의 역수의 무한합이 원주율과 관계 있는 수로 수렴한다는 것을 규명했을 뿐만 아니라 이건 소수의 분포와도 관계가 있기 때문에 임의의 두 수가 서로 소일 확률과 같다고 입증한 건 뭐.. 할 말을 잃게 만든다. 예전에 본인의 블로그에서 다룬 적이 있다.

(3) 또한 그는 소수의 개수가 무한한 건 말할 것도 없고, 소수의 역수의 무한합이 무한대로 발산한다는.. 거의 충격과 공포 안드로메다급의 명제도 증명했다. 물론 속도는 이중 로그(로그에다 또 로그) 급으로 끔찍하게 느리니 기대하지 말자. 그냥 자연수의 역수의 합만 해도 얼마나 느린데 하물며 소수의 역수는! 쉽게 말해 10에다 0을 10의 20승개만치 붙인 영역만치 소수의 역수를 더하면 합이 20이 될까말까 한다는 뜻이다. 쟤가 도대체 제곱의 역수의 무한합보다 뭐가 더 나은 구석이 있다고 발산을 하는 걸까?

단, 쌍둥이 소수들의 역수의 합은 유한으로 수렴한다고 한다. 쌍둥이 소수가 유한하다면 당연히 유한 수렴이겠지만, 무한하다 하더라도 얘는 발산하지 못한다고.. 구체적인 값은 모르겠지만 추세가 그렇게 된다는 큰 그림만 증명을 한 것이다. 어떻게 증명했는지는 나한테 묻지 마시길.

(4) 가우스, 오일러 등 인류 역사상 수많은 괴수 천재 수학자들이 초월적인 업적을 남기고 갔지만, 어떤 형태로든 소수 생성 규칙을 표방하는 모든 예측· 추측은 지금까지 하나도 완벽하게 적중한 게 없었다. 저 페르마의 추측처럼 말이다.
소수를 생성하는 규칙을 무슨 정보 검색이나 패턴 매칭에다가 비유해서 설명하자면, 정밀도와 재현율(precision & recall) 어느 것 하나라도 확실하게 잡는 규칙이 지금까지 발견된 적이 없다는 것이다. 정밀도가 100%라면 모든 소수를 커버하지는 못해도 일단 이 규칙이 생성하는 수는 다 소수임이 보장되는 것이고, 재현율이 100%라면 종종 소수가 아닌 놈(false alarm)이 섞여 있더라도 소수는 하나도 빠짐없이 커버한다는 뜻이다.

(5) partition number라는 게 있다. f(2)라면 1+1, 2 이렇게 2가지, f(3)이라면 1+1+1, 2+1, 3 이렇게 3가지, f(4)라면 1 1 1 1, 2 1 1, 2 2, 3 1, 4 이렇게 5... 뭔가 테트리스 조합처럼 올라가는데, 이 수열이 2 3 5 7 11 (15 22...) 이렇게 앞부분은 소수와 굉장히 비슷한 양상으로 시작한다. 무슨 파이의 그럴싸한 근사값을 보는 듯한 느낌이나, 얘는 실제로는 소수와는 수학적으로 아무런 관련이 없는 놈이다.

n에 대해서 f(n)의 값을 구하는 건 다이나믹 프로그래밍으로 해결 가능하다. 피보나치 수열 구하는 것보다는 어렵고 꽤 재미있는 프로그래밍 excercise이므로 관심 있으신 분은 도전해도 좋다. 참고로 점화식 함수 내지 테이블은 보기와는 달리 1변수로는 안 되고 2변수 형태로 짜야 한다.

Posted by 사무엘

2016/11/30 08:31 2016/11/30 08:31
, , , , ,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/1300

Trackback URL : http://moogi.new21.org/tc/trackback/1300

Leave a comment

간단한 곡선의 방정식

* 꽤 오래 전인 블로그 개설 초창기에 썼던 글을 리메이크 한 것이다.

옛날에 컴퓨터 학원에서 GWBASIC을 중급이나 고급까지 공부해 본 분이라면, 마지막 단원인 그래픽을 공부하면서 이런 비슷한 그림을 하나 그려 본 추억 정도는 있을 것이다.
그리는 방법은 간단하다. 세로줄을 하나 그은 뒤, 그 선의 윗점은 아래로 n만치 낮추고 아랫점은 오른쪽으로 동일한 n만치 옮겨서 선을 긋기를 반복하면 된다. 세로줄이 완전히 가로줄로 바뀔 때까지.

사용자 삽입 이미지

그 단순함에 비해서 생긴 결과물은 꽤 '컴퓨터그래픽스럽고' 뭔가 멋지다는 느낌이 들지 않는지?

그런데 여기서 의문이 생긴다.
저런 식으로 선을 한없이 많이 그어 나갈 때, 가장자리에 형성되는 저 둥그런 곡선은 수학적으로 어떤 의미를 갖는 곡선으로 수렴하게 될까? (그림에서 붉은 곡선) 편의상 선을 (0,0)-(0,1)에서 (0,0)-(1,0)까지 긋는 상황을 가정한다면 어떤 곡선이 그려질까? 이거 굉장히 재미있는 문제이다.

x축 (a, 0)와 y축 (0, b)를 지나는 직선의 그래프는 y = -(b/a)*x + b 이며 이건 중학교 수준으로도 알 수 있는 사실이다.
이 그림에서는 0~1 사이의 a에 대해서 (a, 0)과 (0, 1-a) 사이를 지나는 직선이 만들어지므로 방정식은 y = -((1-a)/a)*x + (1-a)가 된다. 이 식을 [1]이라고 설정하자.

그러면 이 a 지점에서 그어진 직선은 우리가 구하고자 하는 미지의 곡선에서는 어느 지점과 만나게 될까? 이걸 생각하는 게 문제를 푸는 열쇠이다.
a 지점에서 그어진 직선이 곡선의 표면에 닿는 지점은 바로.. 그 직선의 바로 극소량 떨어진 옆에 있는 또 다른 직선과의 교점일 것이다. 극한이라는 개념이 필요해진다.

a 지점에서 x축과 y축이 b만치 극미량 전진하여 (a+b, 0)과 (0, 1-a-b)를 지나는 직선의 방정식은 y = -((1-a-b)/(a+b))*x + (1-a-b) 가 된다. 이 식을 [2]라고 한다.
두 직선 [1]과 [2]의 교점을 구하려면 두 식을 연립해서 x, y에 대해서 방정식을 풀면 된다.
그럼 x=a*(a+b), y=(a-1)*(a-1+b)가 나온다.

b가 0에 한없이 가까워져서 두 직선이 근접하게 되면 교점은 결국 (a^2, (a-1)^2)라고 a에 대한 매개변수식으로 귀착된다. 곡선의 궤적이 이렇게 다 구해진 것이다. 게다가 문제 접근 방식의 특성상, x=a^2인 지점에서 곡선의 기울기도 -((1-a)/a)라고 딱 구해졌다.
x의 매개변수식이 a^2이니 (a-1)^2에다가 루트만 씌우면 끝나고, 그리고 기울기의 부정적분을 구해서 f(0)일 때 1이 나오는 상수 C를 덧붙여 줘도 게임 끝이다.

곡선의 방정식은 x-2*sqrt(x)+1, 또는 y = (1 - sqrt(x))^2 이 된다. 오옷~~~ 비슷한 4사분원의 방정식과 비교했을 때 근호와 제곱의 위치만 싹 맞바뀐 형태라는 게 흥미롭다.
이 정도 문제는 난이도가 고등학교 교과 수준이거나 좀 아슬아슬하게 넘는 수준일 것 같다.
임의의 지점에서 기울기가 저렇게 결정되는 곡선을 구한다는 특성상, 제일 확실하게 푸는 방법은 미분 방정식을 동원하는 것이겠지만.. 그 정도면 확실하게 고등학교 수준은 아니다.

곡선의 식이 정확하게 나왔으니 곡선의 성질도 다 알 수 있다. 저 선들이 차지하는 면적은 1/6이 된다(0부터 1까지 식을 적분한 값). 곡선과 y = x와의 교점, 다시 말해 곡선의 기울기가 정확하게 -1이 되는 지점이며 곡선 내부에 존재할 수 있는 가장 큰 정사각형의 한 변 길이는 1/4임을 알 수 있다.

그리고 또 하나 짚고 넘어갈 점이 있다.
위의 그림에서 빨간 곡선은 내가 손으로 그었을 리는 없고.. 어떻게 그린 걸까?
(a^2, (a-1)^2)라는 궤적은 베지어 곡선의 한 형태이다. 근사가 아니라 2차 베지어 곡선과 수학적으로 완벽하게 일치한다.

시작점 P0, 제어점 P1, 끝점 P2로 이뤄진 2차 베지어 곡선의 식은 (1-t)^2*P0 + 2*t*(1-t)*P1 + t^2*P2 (0<=t<=1)이다.
참고로 임의의 n차 곡선의 식은 각 항의 계수가 1, 3, 3, 1 등 이항정리 계수의 형태로 변하면서 t의 거듭제곱은 증가하고, (1-t)의 거듭제곱은 감소하는 형태로 생성된다.
저 식을 점들의 좌표가 아니라 t에 대해서 풀면 (P0 - 2*P1 +P2)*t^2 + (2*P1 - 2*P0)*t + P0 이 남는다.

문제의 곡선의 매개변수 식을 보면 x축은 a^2로, 2차항 t^2의 계수만 1이고 나머지는 0이다[1, 0, 0]. 따라서 P0은 답정너 0이 되어야 함. 일차항도 P0이 0으로 소거되고 없으면서 전체 계수가 0이 돼야 하므로 P1 역시 0이 된다.
한편, 이차항은 P0과 P1이 모두 0인 상태에서 계수가 1이 돼야 하므로 혼자 남은 P2는 0이 된다. P0, P1, P2의 x축 좌표는 각각 (0, 0, 1)로 정해졌다.

y축으로 가 보면, (a-1)^2는 a^2 - 2*a + 1이므로 맞춰야 하는 계수는 [1, -2, 1]이 됐다. 이로써 상수항 P0은 1부터 시작한다. 그 다음으로 2*P1 - 2*P0이 -2가 되어야 하는데 P0이 이미 1이라면.. P1은 0이 돼야 0-2 = -2가 될 수 있다.
P0도 값이 자동으로 정해진다. P0 - 2*P1 + P2 = 1이어야 하고, P0이 1이므로 P1뿐만 아니라 P2도 0으로 결정된다. P0, P1, P2의 y축 좌표는 각각 (1, 0, 0)이 된다.

이게 무슨 뜻인가? (a^2, (a-1)^2) 매개변수 곡선은 시작점 (0, 1), 제어점 (0, 0), 끝점 (1,0)인 아주 기초적인 2차 베지어 곡선과 동일하다는 얘기이다. 아니 그러고 보니, 베지어 곡선을 수식이 아니라 직관적으로 그리는 방법 중에도 한 선분을 저 그림과 비슷한 방식으로 다른 선분으로 점진적으로 변화시켜서 그 궤적을 연결하는 게 있었다. 심오함이 끝이 없구나..!

보통 그래픽 프로그램에서는 제어점을 2개를 둬서 2차보다는 더 범용적인 3차 베지어 곡선을 지원하는데, 3차 베지어 곡선의 표현력은 당연히 2차 곡선의 그것의 상위 호환이다.
3차 베지어 곡선의 방정식을 역시나 t 변수에 대해서 나타낸 뒤 2차 베지어 전개식과 계수가 일치하도록 방정식을 풀어 보면.. 시작점 P0과 P2는 동일하고 중간점이 P1일 때,
C1 = (2*P1+P0)/3 , C2 = (2*P1+P2)/3
이라는 식이 나온다. 이렇게 두 중간점을 잡아 주면, 3차 베지어 곡선으로 2차 베지어 곡선을 정확하게 나타낼 수 있다.

베지어 곡선으로 수학적으로 100% 완벽하게 표현할 수 없는 유명 요소가 두 가지가 있는데.. 하나는 원/원호이고 다른 하나는 다른 베지어 곡선과 굵기만 다르면서 평행한 파생 곡선이다. 쉽게 말해서 철도 선로의 한 곡선 궤조에 대응하는 다른쪽 궤조 말이다.
그에 반해 저렇게 직선을 찍찍 그어서 자연스럽게 만들어진 곡선 궤적은 매개변수로 표현하나 일변수 형태로 표현하나 식이 딱 구해지고 초월함수 그딴 거도 안 나오고 부정적분도 구해지고.. 마음대로 요리가 되는 게 좋다.

사이클로이드(최단 강하 궤적)라든가 현수선 같은 곡선 문제도 수학 해석적 관점에서 아주 재미있는 주제인데 이것도 나중에 다룰 기회가 있으면 좋겠다.
이 글은 5년 전에 썼던 오리지널에 비해 베지어 곡선 얘기도 들어가고 그림도 GDI가 아닌 GDI+의 앤티앨리어싱이 들어간 것으로 바꾸는 등 내용의 품질을 대폭 향상시켰다. ^^

Posted by 사무엘

2016/03/25 08:27 2016/03/25 08:27
,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/1207

Trackback URL : http://moogi.new21.org/tc/trackback/1207

Leave a comment

다차원 적분

※ 이 글의 내용은 예전에 썼던 <확률과 조합에서 발견한 자연대수 e>와 <원에 대한 적분 외>의 연장선상에 있다.

1차원 선에서 0부터 1까지의 선분의 길이는 두 말할 나위 없이 1이다.
2차원 공간에서 원점, (1,0), (0,1)을 지나는 이등변삼각형의 넓이는 1의 절반인 1/2이다.
이를 더 확장해서 3차원 공간에서 원점과 (1,0,0), (0,1,0), (0,0,1)을 꼭지점으로 갖는 사면체의 부피는 1/6이다.
이를 일반화해서 n차원 적분을 생각해 보면, 차원이 하나 올라갈 때마다 n차원 축을 한 칸씩만 점유하는 초입방체의 부피는 1/(n!)로 팩토리얼의 역수가 되고,  전체 초면체와의 비는 기하급수적으로 감소한다는 걸 알 수 있다. x^n의 부정적분은 (x^(n+1)) / (n+1) + C이다.

한편, 한 변의 길이가 2인 정사각형의 넓이는 4이고, 그 안에 들어가는 반지름이 1인 원의 넓이는 잘 알다시피 pi이다. 원과 사각형의 넓의 비는 pi/4, 즉 78.5% 정도 된다.
이를 공간으로 확장하면 한 변의 길이가 2인 정육면체의 부피는 8이고, 그 안에 들어가는 반지름이 1인 구의 부피는 4*pi/3이다. 구와 정육면체의 부피 비율은 pi/6 (약 52.3%)으로, 넓이일 때보다 비율이 더 작아진다. 이 비율 역시 차원이 증가할수록 더욱 작아진다는 것은 두 말할 나위가 없을 것이다.

그럼 혹시 4차원, 5차원, n차원 초구의 부피를 구할 수도 있지 않을까? 몰론 있다.
원의 방정식의 핵심이라 할 수 있는 f(x) = sqrt( r^2 - x^2 ) 라는 함수를 먼저 정의하자. 얘는 x가 0에서 r로 갈 때 임의의 구간에서 원의 높이를 나타내는, 즉 '둥긂'을 수학적으로 기술하는 함수이니까 말이다.

반지름이 r인 원의 넓이는 잘 알다시피 int( 2*f(x), x=-r..r) 로 나타내어지며 pi*r^2이라는 유명한 공식이 나온다.

그럼 반지름이 r인 구의 부피는 pi*r^2에서 r 대신 f(x)를 다시 집어넣어서 적분을 하면 된다.
int(pi*f(x)^2, x=-r..r) 가 (4/3)*pi*r^3이 된다.

4차원부터도 동일한 방식으로 적분을 계속하면 된다. 수많은 구들이 4차원에 있는 원 표면의 높이 변화량만치 연속적으로 쌓여 있는 것이므로.. 저 r 대신에 또 f(x)를 집어넣으면
int(4*pi*f(x)^3/3, x=-r..r) 은 드디어 파이까지도 제곱이 되어 4차원 초구의 부피는 (1/2)* pi^2 * r^4가 나온다. 한 변의 길이가 2인 4차원 초정육면체와의 부피 비율은 약 30.8%대로 곤두박질친다.

5차원 초구는? int( pi^2 * f(x)^4 / 2, x=-r..r)의 결과는 (8/15) * pi^2 * r^5 (약 16.4%)
6차원 초구는 pi^3 * r^6 / 6 (약 8%)가 된다. 사면체의 부피만큼이나 이것도 비율이 갈수록 곤두박질친다.
요렇게 비율이 한데 수렴하고 특히 짝수차일 때와 홀수차일 때 번갈아가며 무슨 특성이 발견되는 건 리만 제타 함수의 값하고도 비슷해 보인다. 게다가 리만 제타 함수도 n이 짝수일 때는 나름 pi^n의 유리수배가 되기도 하니, 반지름 길이가 1인 n차원 초구의 부피하고도 비록 수학적 의미는 딴판일지언정 좀 비슷해 보이는 구석이 있다.

수학 전공자 중에는 위의 적분들을 직접 손으로 푸는 용자도 있다. 그나마 짝수 승일 때는 루트가 없어지기 때문에 계산이 더 쉬워지는 편. 난 차마 손으로 풀어 볼 시간이나 자신은 없어서 그냥 수학 패키지를 돌려서 답을 구했다.
딱 보면 알겠지만 식에는 규칙성이 있다. 홀수승일 때와 짝수승일 때를 따로 생각해서 각각 차수가 2씩 증가할 때마다 pi에 붙는 제곱도 1씩 증가하고 계수는 2/n씩 증가한다고 보면 정확하다. 짝수승일 때는 1/2 (4차원), 1/24 (6차원)처럼 상수 계수가 1/n!으로 깔끔하게 증가하는 반면, 홀수승일 때는 계수가 좀 복잡하게 올라간다.

울트라 초천재가 아니고서야 4차원이 넘어가는 초구의 존재를 인간의 머리로 제대로 상상하고 실감하기는 거의 불가능할 것이다. '넘사벽'이라는 말이 괜히 있는 게 아니다~!
눈과 귀로 직감할 수 없는 차원이라는 게 신앙의 영역에 있다면, 이해가 안 되더라도 말 그대로 믿음으로 받아들일 수밖에 없을 것이다. 그러나 수학은 그런 게 아니라 고도의 논리와 이성의 영역에 있다.

아쉬운 대로 고차원 공간을 시뮬레이션 할 수 있는 방법은 프로그램을 작성하는 것이다. 다음 코드는 n차원 공간을 -1부터 1까지 점을 순서대로 마구 찍은 뒤, 원점으로부터 거리가 1 이내인 점의 개수를 세서 부피 비율을 구한다. 깔끔한 재귀호출 대신 사용자 정의 스택으로 구현했다.

double GetVolume(int dim, double delta)
{
    double buf[8], vl; int pos=0, i;
    double initv=-1.0-delta;
    __int64 x=0,y=0; buf[0]=initv;
    while(pos>=0) {
        if(pos==dim) {
            for(vl=0, i=0; i<dim; i++) {
                vl+=buf[i]*buf[i]; if(vl>1.0) break;
            }
            if(i==dim) ++x; ++y; --pos; //1 이내에 들면.
        }
        else {
            buf[pos+1]=initv;
            if( (buf[pos]+=delta) > 1.0) --pos; else pos++;
        }
    }
    return (double)x/y;
}

그래서 이렇게 찍으면 결과는 다음과 같이 나온다.

printf("%f\n", GetVolume(2, 0.01)); //0.785075
printf("%f\n", GetVolume(3, 0.01)); //0.523467
printf("%f\n", GetVolume(4, 0.03)); //0.302340
printf("%f\n", GetVolume(5, 0.05)); //0.164649

처음엔 -1부터 1까지 0.01씩 움직이니까 200등분을 했지만 4차원과 5차원으로 갈수록 66등분, 40등분으로 간격을 늘린 이유는.. 당연히 4승, 5승으로 급격히 증가하는 계산량을 감당할 수 없기 때문이다. 그래서 2차원과 3차원은 값이 상당히 정확히 나온 반면, 4차원과 5차원은 오차가 좀 큰 편이다.
그래도 계산이 워낙 단순무식하고 간단하므로 OpenMP 지시자를 집어넣거나 직접 손으로 코드 차원에서 스레드를 강제 분배하든가 해서 멀티코어+병렬화 최적화로 계산 속도를 몇 배 정도 끌어올릴 여지는 존재한다.

사실은 4차원 이상으로 갈 필요도 없이, 3차원 공간에 구가 여러 개 포개어져 있는 장면을 상상하는 것도 쉽지 않다.
학교 수학 시간에 집합 사이의 bool 관계를 구하는 문제에서 집합의 개수는 3개를 넘어간 적이 없었다. 왜냐하면 2차원 평면에서 집합들의 모든 소속 가짓수를 벤 다이어그램으로 그릴 수 있는 한계가 3개이고 2^3, 총 8가지 가짓수이기 때문이다.

그러나 3차원 공간에서 구를 4개 포개어서 입체 벤 다이어그램을 그리면 16가지 가능성을 모두 표현할 수 있다. 구 3개가 8가지 가짓수를 만들고, 거기에 위에다 4개의 구를 적당히 겹쳐 놓으면 8개에다가 넷째 구와 겹치는 놈 8가지가 또 추가되어서 16개가 되니까 말이다. 이 역시 코드로 작성해서 무식하게 확인하면 다음과 같다.

struct SPHERE { double x,y,z; };
const SPHERE fp[4]={
    {0,0,0},
    {0.4,0,0},
    {0.2,0.4,0},
    {0.2,0.2,1.5}
};
auto Square = [](double x) { return x*x; };
SPHERE d;
bool bitfl[16]={false,};
for(d.x=-1; d.x<=1.5; d.x+=0.02)
    for(d.y=-1; d.y<=1.5; d.y+=0.02)
        for(d.z=-1; d.z<=1.5; d.z+=0.02) {
            int bt=0;
            for(int i=0; i<4; i++)
                if( Square(fp[i].x-d.x)+Square(fp[i].y-d.y)+Square(fp[i].z-d.z) <=1) bt|=(1<<i);
            bitfl[bt] = true;
        }
for each(int n in bitfl)
    printf("%d ", n);

반지름은 모두 1이고, (0,0,0), (0.4,0,0), (0.2,0.4,0), (0.2,0.2,1.5)인 4개의 구를 설정한다. 그리고 -1부터 1.5까지 0.02 간격으로 뺑뺑이를 돌려서.. 각 점별로 자기가 속하는 구의 번호에 해당하는 2진수 비트들(8+4+2+1)의 합을 구한다. 그 뒤 그 합에 해당하는 플래그를 켠다.

나중에 플래그의 값을 출력해 보면 모든 비트들이 1로 바뀌었음을 알 수 있다. 즉, 어느 구에도 속하지 않은 놈, 모든 구에 속한 놈, 1, 3, 4번 구에만 속한 놈, 2, 3번 구에만 속한 놈 등등 16가지 가능성이 실제로 모두 존재한다는 뜻이다. 어찌 보면 당연한 얘기이다. 그 반면 구가 5개를 넘어가면 그 32, 64가지 가능성을 한꺼번에 3차원에서 표현할 수는 없게 된다.

사용자 삽입 이미지

반지름이 수십~수백 정도에 달하는 충분히 큰 구의 복셀의 표면을 보는 느낌은 어떨까 문득 궁금해진다.
수학 패키지 소프트웨어들은 3차원 음함수의 그래프를 아무래도 폴리곤+와이어프레임 형태로 근사해서 보여 줄 것이다. 하지만 곡선/곡면을 폴리곤이 아니라 아예 계단현상을 볼 수 있는 복셀로 근사해서 보면 또 느낌이 굉장히 이색적일 것 같다.

사용자 삽입 이미지

표면에는 역시나 원들 무늬가 그러져 있구나!
앞서 보다시피 5차원~6차원 이상으로 가면 단순무식하게 점을 때려박는 것도 계산이 너무 많아서 도저히 감당할 수 없다.
이럴 때 정확한 초구의 부피를 구할 수 있는 건 역시나 수학 해석적인 방법이라는 것을 알 수 있다.
미분 내지 역함수인 부정적분을 할 때 변수의 차수와 계수가 왜 저렇게 변하는지는 다항함수의 차이 극한값을 구해 보면 알 수 있다. 극한부터 시작해서 미분· 적분이라는 개념을 생각해 낸 건 정말 위대한 발견인 것 같다.

Posted by 사무엘

2015/10/15 08:39 2015/10/15 08:39
, , , ,
Response
No Trackback , 2 Comments
RSS :
http://moogi.new21.org/tc/rss/response/1149

Trackback URL : http://moogi.new21.org/tc/trackback/1149

Comments List

  1. 박한철 2015/10/17 16:05 # M/D Reply Permalink

    별 건 아니지만, 원점과 (1,0,0), (0,1,0), (0,0,1) 등으로 이루어지는 도형은 simplex 라고 하는데 초입방체는 hypercube에 해당하는 용어겠죠? simplex의 적절한 번역은 잘 모르겠습니다 -.-;

    1. 사무엘 2015/10/17 19:46 # M/D Permalink

      아하, 선형 계획법 문제를 푸는 알고리즘 중 하나가 '심플렉스'라고 이름이 붙은 것만 알고 있었는데..
      저 도형도 모양을 보아하니 심플렉스라고 하는지 대충 감이 옵니다. 보충 설명에 감사합니다. ^^

Leave a comment

1. 평행사변형의 넓이, 평행육면체의 부피

2*2 크기의
(a b)
(c d)

행렬이 있을 때, 이 행렬의 행렬식이라고 불리는 D 값은 a*d - b*c로 정의된다. ax+by = 얼마, cx+dy = 얼마 요런 방정식의 근을 구하는 식을 세워 보면 행렬식은 x, y의 분모에 들어가 있다. 그러니 이 값이 0이면 근은 부정이나 불능으로 빠지게 된다.

한편, 행렬식에는 기하학적인 의미가 있다. 원점에서 (a,b)를 잇는 선분이 가로변, 원점에서 (c,d)를 잇는 선분이 세로변인 평행사변형의 넓이를 나타내기 때문이다.

그도 그럴 것이 이 행렬은 한 변의 길이가 1인 (0,0), (1,0), (1,1), (0,1)이라는 정사각형을 (a,b), (a+c, b+d), (c,d)라는 평행사변형으로 옮긴다. (a+b)*(c+d)라는 전체 직사각형에다가 주변의 합동인 삼각형 두 쌍의 넓이를 빼면, 평행사변형의 넓이로 남는 것은 ad-bc뿐이다. 아래 그림을 보시라.

(a+c)(b+d) - b(a+c) - c(b+d) = d(a+c) - c(b+d) = ad + cd - bc - cd = ad-bc

사용자 삽입 이미지

이 평행사변형에서 대각선을 구성하는 (a,b)와 (c,d)를 연결하면 사각형을 반으로 쪼갤 수 있다. 다시 말해 원점과 (a,b), (c,d)를 꼭지점으로 하는 삼각형의 넓이는 ad-bc의 절반이 된다.

다음으로..
저렇게 두 점 A(ax, ay)와 B(bx, by)가 있을 때, A-원점-B 자취의 방향을 판단하는 공식이 있다(시계 방향인지 반시계 방향인지). bx*ay - by*ax이며, 여기에는 배후에 삼각함수 sin( alpha-beta )가 숨어 있다.

그런데 위의 두 점 (a,b), (c,d)도 코싸인/싸인 alpha와 코싸인/싸인 beta라는 극좌표 형태로 표현하면, 행렬식 a*d-b*c 역시 결국은 sin( alpha-beta )과 패턴이 동일함을 발견할 수 있다. 두 쌍의 숫자를 각각 서로 엇갈리게 곱해서 빼는 것 말이다.
이렇듯, 행렬식에 두 벡터의 사잇각에 대한 삼각함수 값이 들어있으니, 벡터의 길이만 정규화하면 각도를 구할 수 있다. 또한 두 변의 길이와 그 사이의 끼인각을 알고 있는 삼각형의 넓이는 A*B*sin(theta)/2로 간단하게 결정된다.

그리고 이 식을 확장하면 삼각형뿐만이 아니라 여러 삼각형들로 분해 가능한 단순다각형(선분들이 서로 만나지만 않으며 볼록하거나 오목할 수 있음) 넓이 내지 폴리곤 패스 방향을 구할 수도 있다. 넓이와 방향(넓이의 부호)이 같이 구해진다.

2차원에서는 이 정도로 분석이 되고, 3차원으로 가면 어떨까?
짐작했겠지만 3*3 행렬의 행렬식은 그 행렬을 구성하는 3개의 벡터들을 축 내지 기저로 삼는 평행육면체의 부피와 같다. 직교좌표에서 모든 점들의 최대치에 해당하는 직육면체의 부피에다가 또 모서리 주변의 온갖 사면체들의 부피를 빼야 하니 식이 굉장히 복잡할 것이다. 3*3 행렬의 행렬식이 항이 6개나 되고 2*2의 것보다 훨씬 더 복잡한 것은 이 때문이다.

하지만 3차원에서도 언제나 부피만 구하는 건 아니다.
차원만 2차원이 아닌 3차원으로 확장한 뒤, 원점에서 출발하는 두 벡터를 가로변 세로변 축으로 삼는 평행사변형의 넓이는 어떻게 구하면 좋을까? (삼각형의 넓이도 당연히 자동으로 포함) 즉, 3차원 공간 안에서의 2차원 평면인 것이다. 이건 2*2 행렬식보다는 어렵겠지만 3*3 행렬식보다는 쉬울 것이다.

그리고 이것이 바로 벡터의 '외적'(벡터곱) 연산이 하는 일이다. 아마 고등학교에서는 내적까지만 하지 외적은 안 배우지 싶다. 단, 내적부터 먼저 개념을 좀 복습해 보자.

2. 벡터의 내적

왜 각 성분을 차례대로 곱한 것을 더하면 내적이 나오는 걸까?
이 원리의 배후에는 코싸인 제2법칙이 있다.
아까 두 변의 길이(두 선분의 길이를 각각 A와 B라 하자)와 그 사이의 끼인각을 아는 삼각형의 넓이를 구했는데, 이 경우 삼각형이 유일하게 결정되었으므로 나머지 한 변의 '길이' C도 당연히 구할 수 있다. 그 삼각형의 모든 특성이 파악 가능한 것이다. C^2 = A^2 + B^2 - 2*A*B*cos(theta) 이다.

이건 피타고라스의 정리의 일반적인 경우이며, 증명하는 방법이 상당히 많다. 여기에서는 제일 직관적인 해석학적 방법 하나만 소개하고 넘어가겠다.
선분 A와 B가 원점을 지나고 선분 A는 x 축에 평행하다고 한다면 선분 A는 (0,0)과 (a,0)을 지나게 될 것이며, 0도인 선분 A로부터 theta도만치 떨어진 선분 B는 선분 B는 (0,0)과 (b*cos(theta), b*sin(theta))를 지난다. 임의의 차원의 임의의 위치에 있는 어떤 삼각형 ABC라도 변환을 통해 그렇게 2차원 평면에서의 일반화가 가능하기 때문이다.

그럼 선분 C의 길이는 저 (a,0)과 (b*cos(theta), b*sin(theta)) 사이의 거리와 같다. 그러므로 길이의 제곱은 (a - b*cos(theta)^2 + (b*sin(theta))^2 가 된다.
이 식을 풀면 a^2 - 2*a*b*cos(theta) + b^2*cos(theta)^2 + b^2*sin(theta)^2 가 된다.
b^2항은 cos(theta)^2 + sin(theta)^2 이므로 1로 약분돼 없어지고, 결국 코싸인 제2제곱 공식이 고스란히 나온다.

그럼, A, B, C를 이제 벡터라고 생각하고 2차원이 아니라 각 축별 좌표를 코싸인 제2제곱 공식에다 대입해 보자.
A=(a1,...,an), B=(b1,...,bn) 같은 식이다. C는 두 벡터의 차이 A-B와 같다.
벡터의 절대값의 제곱은 잘 알다시피 거리의 제곱과 같기 때문에 각 성분들의 제곱을 모두 더한 것과 같다. 그러므로

∑ [i=1..n] (ai^2 + bi^2 - 2*ai*bi) = ( ∑ [i=1..n] (ai^2 + bi^2) ) - 2*A*B*cos(theta) 로 식이 대충 떨어진다.

A와 B에서 각 성분들의 제곱을 합을 구하는 부분은 좌우변 공통이므로 소거되고.. 남는 것은
2*A*B*cos(theta) = ∑ [i=1..n] 2*ai*bi 이다. 여기서 양변을 2로 나눠 주면 내적 공식이 아주 깔끔하게 유도된다. 콜?

벡터의 내적은 그냥 숫자 하나(스칼라)만으로 답이 떨어지며, 벡터의 각 성분들을 차례대로 곱해서 더하기만 하면 된다. 내적에는 두 벡터의 사이각의 '코싸인' 값이 들어있기 때문에, 두 벡터가 서로 수직인지를 벡터의 길이와 무관하게(= 정규화 안 하고도) 간편하게 판별할 수 있다. 코싸인 90도는 0이므로!

내적은 계산이 딱히 어렵지 않을 뿐만 아니라, 2차원이고 3차원이고 어느 차원이든지간에 계산법이 동일하다는 것도 큰 장점이다. 두 벡터의 사이각을 구하는 용도로는 완전 딱이다. cos(alpha-beta) = cos(alpha) cos(beta) + sin(alpha) sin(beta) 인 것에도 2차원일 때의 내적 공식이 숨어 있다는 걸 발견할 수 있다.
또한, 생긴 모양 덕분에 벡터의 내적을 행벡터(행이 하나. 수평선-_-)와 열벡터(열이 하나. 수직선)의 곱으로 표기하기도 한다. (행과 열뿐만이 아니라 횡과 종도 어느 게 어느 건지 종종 헷갈릴 때가 있다만..;;)

3. 벡터의 외적

그에 반해 외적은 결과값도 벡터이다. 그리고 3차원일 때에만 정의된다. 계산값의 각 차원과 피연산자들이 일대일로 딱 밀착해 있는 관계로 3차원 말고는 선택의 여지가 없기 때문이다.

성분이 (a1,a2,a3)인 벡터 A와, 성분이 (b1,b2,b3)인 벡터 B의 외적은
(a2*b3-a3*b2, a3*b1-a1*b3, a1*b2-a2*b1)이라고 정의된다.
어 그런데 이거, 두 쌍의 숫자를 각각 서로 엇갈리게 곱해서 빼는 게 2*2 행렬식을 구하는 것과 비슷해 보인다. 맞다.
그래서 벡터 A, B가 동일 평면상에 있어서 a3와 b3 같은 게 동시에 0이기라도 하면, 해당 변수가 포함된 항은 모두 소거된다. 이 경우 외적은 그냥 2*2 행렬식과 동일해진다.

또 생각할 점은.. 3*3 행렬식을 구하는 것도 특정 row와 col을 제외한 2*2 행렬식을 구하는 것의 연속이라는 점이다. 그래서 외적 구하는 공식을
(i  j  k )
(a1 a2 a3)
(b1 b2 b3)

의 행렬식이라고 표현하기도 한다. 물론 여기서 i~k는 스칼라값이 아니라 각각 (1,0,0), (0,1,0), (0,0,1)에 해당하는 단위벡터이다. 그러니 스칼라와 벡터가 뒤섞여 있는 저 행렬은 대수적인 의미는 딱히 없다. 외적 구하는 공식을 좀 더 뽀대나게 표현하는 용도로만 쓰이는 셔틀일 뿐이다. 그래도 결국은 3*3 행렬식과 닮긴 닮았다.

행렬식을 구하는 공식에서 j에 해당하는 부분은 더하는 게 아니라 뺀다. 그렇기 때문에 외적 공식에서는 1,3이 아니라 3,1 순서로 쓴 뒤에 더하는 것으로.. 다시 말해 양수를 빼는 게 아니라 음수를 더한다고 표현을 달리 했다. 둘 다 동일한 의미이므로 부호에 주의하기 바란다.

벡터는 스칼라와는 달리 '크기'뿐만 아니라 '방향'이라는 정보가 추가로 들어있다.
외적 연산을 통해 구해진 벡터는 일단 크기는 두 벡터의 크기의 곱에다가 사잇각의 sin값을 곱한 것과 같다. 그러므로 3차원 공간에서 두 3차원 벡터가 만드는 평행사변형/삼각형의 넓이를 구할 수 있다.

외적 식을 전개해서 크기의 제곱을 해 보면, 각각의 두 벡터의 크기의 제곱을 곱하고 거기에다 벡터의 내적값(양 벡터의 각 성분들을 서로 곱해서 더함)의 제곱을 뺀 것과 같다고 식이 전개된다. A^2 - B^2 꼴이 되기 때문에 (A+B)(A-B)로 인수분해를 하고 싶은 충동이 느껴지지만 여기서는 식을 다른 형태로 바꿔야 된다.

내적에는 역시 두 벡터의 크기의 곱에다가 사잇각의 cos이 들어 있으니 이것의 제곱이라면 두 항이 결국 |A|^2 * |B|^2를 공통으로 갖고 있고 (1  - cos^2 )가 남는다. 그리고 이것이 sin^2과 같다는 건 두 말하면 잔소리이고.

외적의 크기에 벌써 이렇게 유용한 정보가 들어있는데, 방향은 더욱 흥미롭다.
짐작하겠지만 두 벡터의 외적의 방향은 두 벡터와 수직이다. 물론 위쪽도 수직이고 아래쪽도 수직인데, 해당 좌표계의 동일 부호가 향하는 쪽으로 방향이 결정된다. 두 기저 벡터에 대한 외적을 구하면 나머지 기저 벡터가 튀어나온다.

애초에 두 벡터의 외적은 그 두 벡터와의 내적이 모두 0인 벡터 중에 크기가 저렇게 AB sin(theta)로 나오는 놈을 구한 것이다. a1*c1 + a2*c2 + a3*c3 = 0과 b1*c1 + b2*c2 + b3*c3 = 0을 만족하는 (c1,c2,c3)을 직접 구해 보면 안다. 저것만으로는 식보다 미지수 개수가 더 많으니 (c1,c2,c3)가 하나로 딱 떨어지지 않고 c1과 c2가 c3의 배수인 것처럼 관계식만 나온다. 그런데 c3의 특정값일 때 c1,c2에 있던 분모가 싹 소거되고 c1~c3이 저렇게 아주 대칭적이고 깔끔하게 나오는데 그게 바로 외적값이다.

이런 유용함 때문에 외적이 3차원에서의 전유물이라고 여겨지는 것이다. 이항연산에 딱 최적화돼 있지 않은가.
물론, 외적은 수직이라는 게 위아래가 모두 존재한다는 특성상 교환 법칙이 성립하지 않고 A×B=-B×A이다. 뭐, 4차원 이상에서는 두 벡터와의 내적이 모두 0인 벡터는 3차원일 때처럼 일직선상의 형태로 유일하게 떨어지지가 않는다. 그러니 외적과 같은 접근 방식이 큰 의미가 없어져 버린다.

끝으로, 3차원에서 벡터의 내적과 외적은 삼중곱이라는 연산을 통해 한데 만난다. 3개의 벡터 A,B,C를 축으로 하는 평행육면체의 부피를 구하고 싶으면 아까처럼 벡터들을 3차원 행렬의 행렬식으로 표현해도 되지만, 밑면에 속하는 두 벡터 A×B의 외적을 구한 뒤 거기에다 C와 내적을 구하면 된다. (A×B)·C! 그게 결과적으로 행렬식을 구한 것과 같은 계산 결과가 도출된다. 왜 그런지는 아까 그 외적 구하는 행렬과 일반 행렬의 행렬식을 늘어놓고, 거기에다가 내적을 구하는 공식까지 적용한 뒤 서로 비교하며 생각해 보면 된다.

Posted by 사무엘

2015/08/23 08:25 2015/08/23 08:25
, , , , ,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/1130

Trackback URL : http://moogi.new21.org/tc/trackback/1130

Leave a comment

sin 1°의 정체

sin 1°는 어떤 무리수일까?

답부터 말하자면, sin 1도는 일반적인 통념과는 달리 초월수가 아니다. 이는 임의의 정수 각도도 마찬가지이다.
유한 번의 사칙연산과 거듭제곱/제곱근으로 표현 가능한 대수적 수라는 뜻이다. (사실, π나 e 같은 초월수도 사칙연산· 거듭제곱· 근호의 꼴로 나타낼 수 있다. 단지 그게 무한히 반복되는 급수의 형태가 될 뿐이지..)

삼각함수는 삼각형을 이루는 두 변의 각도가 이러할 때 변의 길이를 비율이 어떻게 되는지를 나타내는 함수이다. 기하학에서는 그야말로 필수 중의 필수 도구이지만, 대수적으로는 직관적이지 않은 굉장히 기괴한 특성을 많이 지닌다. 그래서 학교에서 수포자를 양산하는 원흉이기도 하다.

삼각함수에다 일반 자연수나 유리수를 집어넣으면, 지수나 로그함수와 마찬가지로 우리가 의미를 알 수 없는 괴랄한 초월수가 함수값으로 튀어나온다. 그러나 pi의 유리수 n배 내지 1/n배에 속하는 각도에 대해서는 꼭 그렇지만은 않다. 이미 입력값인 pi부터가 대수적이지 않은 괴랄한 수여서 그런 게 아닐까 싶다.

먼저, 특수한 각도에 대해서는 함수값이 깔끔한 수 내지 심지어 유리수 범위로 떨어질 때가 있다. 특히 15 내지 30도 간격인 0, 30, 45, 60, 90도일 때 sin 값은 각각 sqrt(n)/2 (n은 0 이상 4 이하)로 딱 떨어진다. 가장 단순한 형태다.

여기에서 파생된 각, 다시 말해 레퍼런스 각의 n배나 절반, 1/3 따위에 해당하는 각은 위대하신 삼각함수의 덧셈 정리를 통해 cos/sin 값을 구할 수 있다. 덧셈 정리라는 게 당연히 대수적인 조작들만 있으므로 대수적인 수에 대수적인 조작을 하면 그 수도 대수적인 것은 당연지사. 정수 계수 대수방정식의 근이 될 수 있다.

그리고 15도 단위 계열뿐만 아니라 18도 단위에 계열에 대해서도 삼각함수는 비교적 간단한 형태의 값이 나온다. 세배각 공식이어서 원래는 3차 방정식을 풀어야 하지만 이 각도는 그나마 1차식과 2차식으로 인수분해되는 경우이기 때문이다.

사용자 삽입 이미지

이를 이용하면, 18도와 15도의 차인 sin 3도까지도 약간 복잡하지만 답이 나온다. (그림: 영문 위키백과)

사용자 삽입 이미지

하지만 정수 도에서 그나마 해피한 결과가 나오는 정밀도의 한계는 여기까지.
sin 1도 정도가 되면 유한한 사칙과 거듭제곱, 근호만으로 정확한 값을 묘사하는 게 불가능하지는 않으나 의미가 없어진다.
반복되는 패턴에 대한 매크로 치환을 하고도 항이 열몇 개에 달할 정도로, 정말 미치도록 복잡한 형태가 되기 때문이다.

3도 간격의 수로부터 1도 단위의 삼각함수 값을 구하려면 아까 18도의 경우처럼 각을 3등분을 해야 하는데 이제는 인수분해가 되지 않는다
얄짤없이 3차 방정식이 되며(삼각함수의 3배각 공식은 3차식!), 작도 불가능한 것으로도 잘 알려져 있다. 복잡함이란 본질적으로 이런 데서 유래되는 게 아닌가 싶다. 그냥 내 감이 그렇다는 뜻.

3차 방정식의 근의 공식은... 2차 방정식의 그것하고는 비교조차 할 수 없을 정도로 머리 터지게 복잡하다. 그래서 3차 방정식의 근인 sin 1도의 값도 끔찍하게 복잡한 형태로 산출되는 것이다.

* 끝으로 보너스.
arctan 1 + arctan 2 + arctan 3 = pi 임을 증명하시오.

arctan 1이야 45도의 특성상 pi/4가 되는 게 잘 알려져 있다만, 저런 관계는 도대체 어떻게 성립하는 걸까?
세 각도의 합이 180도라는 뜻이므로, 기울기가 1, 2, 3인 세 각은 일정 비율의 닮은 삼각형을 결정하는 각이 될 수 있음을 보이면 되겠다.

삼각형의 두 꼭지점의 각의 기울기(=탄젠트)가 x, y라면, 나머지 꼭지점의 각도는 기울기가 1/x인 각과 1/y인 각 두 개의 합으로 표현된다. (나머지 꼭지점에서 맞은편 변으로 수선을 내려 보면 직관적으로 이해됨)

그런데 삼각함수의 덧셈법칙에 따라
tan(a+b) = (tan(a)+tan(b)) / (1 - tan(a)*tan(b))
이므로.. 이 공식으로 두 탄젠트를 합성하면, 나머지 꼭지점의 탄젠트는

(y+x)/(x*y-1)로 표현될 수 있다.

x,y에 1,2를 넣으면 저 값은 3이 되고, 2,3을 넣으면 값은 1이, 1,3을 넣으면 값은 2가 된다. 사실, 식의 특성상 (x,y)->z만 성립하면 (x,z)->y와 (y,z)->x는 일일이 체크하지 않아도 자동으로 성립하긴 한다.
따라서 어떤 경우든 기울기가 1, 2, 3인 세 각은 닮은 삼각형을 결정하는 각이며, 그 합은 삼각형의 내각의 합인 180도, 즉 pi임을 알 수 있다.
내가 생각하는 것보다 더 간단하게 증명하는 방법도 물론 있을 것이다.

Posted by 사무엘

2013/12/31 08:30 2013/12/31 08:30
,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/915

Trackback URL : http://moogi.new21.org/tc/trackback/915

Leave a comment

행렬 기초 이야기

a*x + b*y + M = 0
c*x + d*y + N = 0

이라는 두 개의 이원(x, y) 일차방정식이 있다고 치자. 흔히 연립방정식이라고도 불린다.
이 방정식을 풀려면 x, y 중 하나의 계수를 a나 c, 아니면 b나 d로 맞춰 줘서 한 변수를 소거해야 한다. 그래서 일원 일차방정식으로 바꿔서 반대편 변수의 근을 구한 뒤, 그 값을 대입하여 원래 변수의 근까지 구하면 된다.

이를 일반화하여 위의 방정식의 '근의 공식'을 구하면 다음과 같다. 뭔가 규칙성이 있는 것 같으면서도 미묘하게 잘 안 외워진다.

x = (N*b-M*d) / (a*d-b*c)
y = (N*a-M*c) / (a*d-b*c)

분모를 보니 생각나는 게 없는가?
그렇다. 이것은

[ a b ]
[ c d ]

라는 원소로 구성된 2*2 정방행렬의 행렬식을 구하는 공식이다.
이 행렬식의 값이 0이라는 건 a:b와 c:d의 비율이 동일하다는 뜻이다. 따라서 이 행렬을 구성하는 벡터들은 서로 일차(선형) 독립을 이루지 못하며, 상수항이 어떻냐에 따라서 이 방정식은 근이 무수히 많거나 근이 존재하지 않게 된다.

이런 행렬을 거친 일차변환은 2차원 평면을 1차원 선이나 점으로 찌그러뜨린다. 이런 행렬은 영벡터(모든 원소의 값이 0)가 아닌 벡터 중에서도 자신과의 곱을 영벡터로 만드는 물건이 무수히 존재하게 된다(Ax=O).
예를 들어 연립방정식 x+2*y = 0 과 3*x+5*y = 0의 근은 x와 y가 모두 0인 trivial solution 단 하나밖에 없으나, x+2*y = 0과 3*x+6*y = 0은 두 식이 동치나 마찬가지이기 때문에 x = -2*y이기만 하면(가령 2와 -1) 식이 성립한다. non-trivial solution들이 존재한다는 뜻이다. 결국, 근이 무수히 많을 수 있다는 말과 본질적으로 동일하다.

이들은 모두 필요충분조건 관계에 있으며, 이외에도 이런 행렬의 엄밀한 특성에 대해서는 선형대수학 시간에 많이 배우게 된다.

말이 길어졌는데, 그럼 변수가 세 개 이상이 되면 근을 구하는 양상이 어떻게 바뀔까?
그야말로 폭발적으로 복잡해진다.

변수가 2개일 때는 x, y 근에 최대 두 변수의 곱(최대 2차)으로 이뤄진 항이 분자와 분모에 2개씩 있었다.
그러나 3개일 때는 세 변수의 곱으로 이뤄진 항이 분자와 분모에 6개씩 들어간다.
그리고 이를 일반화하면, n원 1차 연립방정식의 근은 n개의 변수의 곱으로 이뤄진 항이 분자와 분모에 무려 n! (팩토리얼)개씩 들어간다!
이것이 '폭발적'이라는 단어의 의미이다. 예를 들어,

[ a b c ]
[ d e f ]
[ g h i ]

라는 3*3 정방행렬의 행렬식은 다음과 같다. 어떤 규칙성이 있는지, 어떻게 하면 잘 외울 수 있겠는지 한번 생각해 보시라.;;

a*e*i - a*f*h - b*d*i + b*f*g + c*d*h - c*e*g

a가 속한 행과 열을 제낀 2*2 행렬(e f / h i)의 행렬식에다가 a를 곱해서 더하고,
다음으로 b가 속한 행과 열을 제낀 2*2 행렬(d f / g i)의 행렬식에다가 b를 곱해서 빼고,
끝으로 c가 속한 행과 열을 제낀 2*2 행렬(d e / g h)의 행렬식에다가 c를 곱해서 더하면.. 이 행렬 전체의 행렬식이 나오긴 한다. 2*2 행렬식이 2개의 항으로 구성돼 있는데 그런 식이 3개가 늘어나니 총 6개가 되는 게 맞다.

이런 방식으로 행렬을 쪼개면 그 어떤 크기의 행렬의 행렬식도 구할 수는 있다. 하지만 크기가 3을 넘어가는 행렬에 대해 행렬식 내지 방정식을 푸는 일반적인 공식을 구하려는 생각은 포기하는 게 좋다. 머리 터진다..;;

참고로 1변수 n차 방정식의 경우를 생각해 보자. 2차 방정식은 잘 알다시피 비교적 외우기 쉬운 근의 공식이 존재하는 반면 3차와 4차는 근의 공식이 있기는 하나 인간의 머리로 도저히 외울 수 없을 수 없을 정도로 미치도록 복잡한 형태이다. 게다가 서로 인접한 차수끼리 규칙성 같은 것도 아예 존재하지 않는다. 5차 이상부터는 대수적인 방법만으론 깔끔하게 풀 수조차 없다.
그에 반해 n변수 1차 연립방정식은 비록 그 정도로 카오틱하게 복잡한 건 아니지만, 그래도 좀 다른 양상으로 복잡해진다는 게 오묘한 점이다.

그리고, 이건 일반적인 공식을 구하려 할 때 딸려 나오는 식이 지수함수 급으로 복잡해진다는 소리다. 일반적인 경우가 아니라 그때 그때 특정 숫자가 주어진 행렬의 행렬식을 구하는 알고리즘의 시간 복잡도가 지수함수라거나 NP 완전 문제 급이라는 뜻은 아니다. 둘은 서로 다른 개념이다.

변수가 3개를 넘어가는 방정식은 어떻게 풀어야 할까?
가령, 변수가 x, y, z라고 치면 일단 모든 방정식의 x의 계수를 1이든, 맨 위의 식의 계수로든 어쨌든 하나로 일치시켜야 한다. “등식에서 같은 수를 더하거나 빼도 등식은 성립한다.” / “등식에서 같은 수를 곱해도 등식은 성립한다” 라고.. 초등학교 산수 시간에 배우는 지극히 당연하고 기본적인 원리를 이용해서 방정식을 푸는 것이다.

그렇게 해서 x 변수를 없는 놈 취급할 수 있게 만든 뒤, 다음 방정식에 대해서 y 변수의 계수를 일치시킨다.
이런 절차를 반복하여 변수를 z만 남겨서 z 값을 구하고, 다음으로 y, x의 순으로 재귀적으로 근을 구하면 된다.
행렬이라는 물건 자체가 이런 연립방정식을 푸는 동작을 간략하게 모델링하는 과정에서 고안되었다.
앞서 말한 절차를 행렬 용어로 표현하자면, 가우스-조던 소거법으로 행렬을 대각화하는 것과 같다.

행렬이 대각화가 되고 나면 방정식을 다 푼 것이나 다름없을 뿐만 아니라, 행렬식의 값은 그 행렬의 대각선 원소들의 곱으로 쉽게 구할 수 있게 된다.
행렬을 대각화하는 데 드는 시간 복잡도는 일반적으로 O(n^3)으로, 행렬 곱셈의 비용과 같다.
이 작업을 숫자를 대상으로 곧장 곧장 업데이트하는 게 아니라, 기호를 이용해서 일반적인 경우를 다 고려하여 표현하려다 보면 항 개수가 아까 같은 팩토리얼 급으로 증가하게 되는 것일 뿐이다.

연립방정식 하니까 응용수학 내지 산업/경영공학 같은 데서 다루는 그 이름도 유명한 선형 계획법(LP)이 생각난다.
이런 데서 다루는 문제는 대체로 변수의 개수가 식의 개수보다 더 많고, 식도 등식이 아니라 부등식이다. 애초에 해 자체는 무한히 많을 수밖에 없는데 그래프의 능선을 따라다니면서 주어진 조건을 최대한 만족하는 영역을 찾는 게 목적이다. 이런 문제는 실용적인 가치도 무진장 높다.

이런 걸 푸는 제일 간단한 알고리즘으로는 simplex method가 있는데, 그 이상의 디테일은 본인도 비전공자인 관계로 잘 모른다. 변수의 차원이 최대 2차원 정도일 때나 그래프를 그려서 생각할 수 있지, 이 역시 3차원 이상으로 가면 머리에 쥐 난다. 고등학교에서 행렬을 2*2까지밖에 다루지 않는 것, 그리고 전산학에서 간단한 bool 대수 연산을 다룰 때 변수를 3개까지밖에 넣지 않는 게 다 이유가 있어서 그런 것이다.

Posted by 사무엘

2013/10/26 19:25 2013/10/26 19:25
,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/891

Trackback URL : http://moogi.new21.org/tc/trackback/891

Leave a comment

블로그 이미지

철도를 명절 때에나 떠오르는 4대 교통수단 중 하나로만 아는 것은, 예수님을 사대성인· 성인군자 중 하나로만 아는 것과 같다.

- 사무엘

Archives

Authors

  1. 사무엘

Calendar

«   2018/11   »
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30  

Site Stats

Total hits:
1055101
Today:
93
Yesterday:
580