My Story, My Life

5hoon's Blog is powered by Tattertools

1 2 3 4 5  ... 10 
Traveling Salesman Problem, 외판원 문제.
이번학기에 X줄 타면서 한과제...
대략 3박 4일 걸렸다.. 순수 코딩시간만 해도 머리가 잘 안돌아서 40시간쯤은 했....
여튼...

위키피디아에서 말하기를..
Q: given a number of cities and the costs of traveling from any city to any other city, what is the least-cost round-trip route that visits each city exactly once and then returns to the starting city?

즉, 주어진 도시와 도시들 사이의 거리를 알때, 모든 도시를 한번씩 방문하여 제자리로 돌아 오는 최단 거리의 경로는 어떻게 될까?

두가지 방법으로 문제를 접근해 보았다.
1. Branch and Bound

Branch and Bound


2. Christofides Algorithm

more..


완성작.

more..


여튼.. 이수업.. 학점하난 잘받았다..-_-a
크리에이티브 커먼즈 라이센스
Creative Commons License
2008/12/24 14:51 2008/12/24 14:51

해리포터 6편 혼혈왕자의 영화 공식 예고편입니다.

고화질 다운로드 링크는 여기에
크리에이티브 커먼즈 라이센스
Creative Commons License
2008/11/23 14:44 2008/11/23 14:44
룸메이트가 자러 가지 않아서 혼자 불끄긴 싫어서 그냥 같이 깨어 있기에....
포스팅이나 하나더 ... -0-

예전에 수학교수가 내준 문제이다.

Q. 2,6,10 이 쓰여진 숫자 카드가 여러장 있다고 하자.
이중 7 개를 골라 더하거나 빼서 52 를 만들어라.
즉, ㅁ±ㅁ±ㅁ±ㅁ±ㅁ±ㅁ±ㅁ = 52

A.

기권하기..


크리에이티브 커먼즈 라이센스
Creative Commons License
2008/11/17 18:48 2008/11/17 18:48

수학문제 하나..

나 (Me)/수학 2008/11/17 18:17 by 5hoon
지식인 답변을 하나 작성 하다가 쓸데없이(?) 증명 까지 해버린 문제가 하나 있었다..
SAT수학을 가르치다가도 비슷한 문제가 있던 기억이 있기에 여기에 옮겨 본다.

Q: 어떤수 x 를 4로 나누면 2가 남고, 5로 나누면 3이 남고, 6으로 나누면 4가 남는다. x 를 만족하는 가장 작은 자연수를 구하여라.

A: 간단히 4,5,6 의 최소 공배수인 60 에 2 를 뺀 58 이 답이다.

여기서
4로 나누면 2가 남고 -> 4-2 = 2
5로 나누면 3이 남고 -> 5-2 = 3
6으로 나누면 4가 남고 -> 6-2 = 4
즉, 나누는 수와 나머지의 차가 2로 항상 일정 하다는걸 알수있다.

문제를 다시 쓰면,
어떤수 x 를 a 로 나누면 나머지가 a-k, b 로 나누면 b-k, c 로 나누면 c-k 인 가장 작은 자연수 x를 구하라고 하면,
여기서 l,m,n 을 임의의 자연수라고 하면
x = a*l + a-k = a(l+1) - k
  => x + k = a * l
x = b*m + b-k = b(m+1) - k
  => x + k = b * m
x = c*n + c-k = c(n+1) - k
  => x + k = c * n
(다른 알파벳 쓰기 싫어서 중간에 l=l+1, m = m+1, n=n+1이라 했다)

즉, x+k 는 a 의 배수이면서 b의 배수 이면서 c 의 배수 임을 알수 있다.
고로, x+k 는 a,b,c 의 공배수가 되고
x  는 a,b,c 의 공배수에서 k 를 빼면 되는것이다.

반대로, 어떤수 x 를 a 로 나누면 나머지가 k, b 로 나누면 k, c 로 나누면 k 인 가장 작은 자연수 x를 구하라고 하면 어떻게 될까?

마찬가지로 다시 x 를
x = al + k
=>  x - k = al
x = bn + k
=>  x - k = bn
x = cm + k
=>  x - k = cm

이번엔 x-k 가 a,b,c,의 공배수가 됨을 알수 있다
즉 x는 a,b,c 의 공배수 +k 가 되는것이다.

크리에이티브 커먼즈 라이센스
Creative Commons License
2008/11/17 18:17 2008/11/17 18:17

어디서 보게 된 영상..


아는 노래도 몇곡 있고..
그래서 여기 나오는 노래들을 모와 보았다..

1. 사회부정적인 내용


2. 저급한 단어 사용


3. 고작 이것때문에?



음악 플레이어 위치
듣기 버튼을 눌러주세요

가사보기

크리에이티브 커먼즈 라이센스
Creative Commons License
2008/11/11 20:37 2008/11/11 20:37

아름다운 이별

Entertainment/Music 2008/11/07 14:08 by 5hoon
오랫만에 라디오 스타를 보다가..

김건모가 부른 아름다운 이별을
옥주현이 리메이크 해서 불렀다길레..
검색해보니..

많은 가수 들이 불렀던...
그래서 다 모와서 ^^;
(가사는 맨 밑에 ^^)

김건모


옥주현


싸이 (feat. 이재훈)


태연


박혜경


가사보기



크리에이티브 커먼즈 라이센스
Creative Commons License
2008/11/07 14:08 2008/11/07 14:08
어젯밤 결과가 미대선 결과가 나오고 난후 두 후보의 연설입니다.

McCain - Phoenix

Transcript 보기



Obama - Chicago


Transcript 보기


다운받기


크리에이티브 커먼즈 라이센스
Creative Commons License
2008/11/06 09:41 2008/11/06 09:41