Toolofv 님의 블로그

문제외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한..

사람은 누구나 약하다. 혼자서 개인으로 감당하기 힘든 시련들이 살다보면 주어지기도 한다. 출구없어보이는 그 교착을 타개하는 데에는 제 3의 무언가를 변수로 추가하여 의존하게 된다. 인류에게 그게 '신'이었다. 사람이 사회를 이루고 살아가는 것은 종교의 등장과 관련이 깊다. 종교는 사람의 본성 중 일부인 것이다. 그 종교가 무슨 종교이든지 이 '종교'가 인간이 살아가는 데에 그래도 하루를 살 수 있는 힘을 주고 있는 것은 사실이다. 진실인지 알 수는 없지만, 아니 진실은 분명히 아니지만 종교는 그래도 에너지를 주고 있다. 사람을 묶어주고 있다.  갈릴레이와 뉴턴의 등장으로 인해 서구의 과학혁명시대를 거치며, 점성술은 삿된 것이 추려지고 천문학으로 남았고 연금술도 삿된 것이 추려져서 화학으로 남았다. 사람들..

문제지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수..

훈족의 등장  유목민의 역사는 무언가 짙은 안개가 드리워져 있는 것처럼 보인다. 훈족은 문자체계가 없었다고 하며, 당연히 기록을 남기지 않았다. 흉노족이 활동하던 현재의 카자흐스탄 발하슈호 지역에서부터 유라시아 스텝지대를 거쳐, 흑해연안에서 고트족의 이동을 강제하며 유럽에 등장하기까지 도대체 무슨 일이 있었던 것일까?  현재 고고학과 유전자계통분석 연구결과에 따르면, 훈족은 흉노족과 스키타이인과의 혼혈이라는 설이 유력하다고 한다.사실 유목민족의 혈통은 워낙 여타 유전자와 섞일 가능성이 높다고 보기에, 워낙 잡탕이고 DNA의 유사성으로 판단하는 관점은 핵심적인 증거가 될 수는 없는 것 같다. 생활양식과 문화, 조직체계 등을 종합적으로 봐야하는데, 학계에 관련 연구자료가 부족한 듯 싶다. 여타 유럽과 중국에..