세상은 넓고 머리 좋은 사람은 많다
- Posted at 2006/11/14 16:36
- Filed under 살아가기, 생각하기
오늘 PS 수업 시간은 여느 때와 마찬가지로 진행되었다. 마지막에 시간이 좀 남아서, 전에 숙제로 풀었던 ACM ICPC 예선문제들을 어떻게 풀었는지 설명하는 시간을 만들었는데, 그 중 F번 금고 문제를 푸는 것에 대한 이야기가 오갔다. 가장 typical하게 푸는 해법은 대충 다들 알고 있는 분위기였다. 그러다가 전부터 두각(?)을 나타냈던 한 학생(아마도 한 살 많은 3학년인 것 같음)이 Linear Algebra(-_-)로 문제를 더 확장한 임의의 경우에 대하여 polynomial 시간 안에 푸는 방법을 제시했다.
그 분이 약 20여분 간 설명하면서, 물리학에서는 이런 테크닉을 일반적으로 쓰는데(물리과 복수전공임-_-) 이 문제에 적용하면 어떨까 했더니 order of n^6 안에 이런 류의 문제를 모두 풀 수 있을 것이라는 결론을 얻었고, 문제 특성을 이용한 최적화를 통해 n^2까지 줄였다면서 설명한 주요 골자는 금고 grid를 하나의 vector로 표현하고, 문제에서 금고 손잡이 돌리는 동작을 다시 하나의 vector로 표현해 n^2 x n^2 matrix를 만들어서 문제에서 제시된 현재 상태로부터 초기 상태까지 가는 operation을 어찌어찌 잘 하면 구할 수 있다는 것이었다. 그러면서 이런 방법이 Pattern reconginition 분야에서 많이 쓰이고 있으며, 필기 인식을 4x4 matrix 정도로도 상당한 정확도로 계산할 수 있다는 설명까지 덧붙였다. -_-;
다른 사람들은 그 설명을 보면서 다들 감동 or 관광(...)타는 분위기였고, 교수님도 extra point를 주라며 조교한테 얘기하셨다. (뭐, 이미 지금까지 해온 숙제들을 보면 A+이 아닌 게 이상하겠지만..)
역시 세상은 넓고 머리 좋은 사람은 많다. (우리들 사이에서는 '본좌'라고 부른다.) 검색엔진을 개발하시는 고감자님의 블로그를 보면서 선형대수학과 확률 통계의 중요성을 새삼 느끼고 있던 차였는데, 이런 문제도 선형대수학 테크닉을 활용해서 저렇게 멋지게 풀어낼 수 있는 걸 보니 정말 수학의 중요성을 절감할 수 있었다. 하아.. 그나저나 이번 선대개 재수강은...ㅠ_ㅠ
ps. 역시 polarnara님처럼 선대를 한 네 번은 들어야 하는 것일까. (....)
ps2. 이참에 물리과 복수전공을...?! ;;;
- Tag
- ACM ICPC, KAIST, PS, 선대, 선형대수학, 수학
- Response
- No trackback yet , 28 Comments
- RSS :
- http://daybreaker.info/blog/rss/response/541
Trackback URL : 이 글에는 트랙백을 보낼 수 없습니다
Comments List
-
코카스 2006/11/14 17:05 # M/D Reply Permalink
그거.. 물리과 윤모군, bluehope 쓰는 아저씨얘기인 거 같군요. 03 4학년입니다. :)
저한테 막 설명을 해주기도 했는데 당최 뭔 얘긴지 버스만 탔... 고요.
http://www.hellodd.com/Kr/DD_News/Article_View.asp?Mark=17174 이런것도 있고.. 이번 카포전 인공지능대회 카이스트 대표기도 했고 등등등... ㄱ--
daybreaker 2006/11/15 00:11 # M/D Permalink
헐.... (........)
-
-
trendon 2006/11/14 18:04 # M/D Reply Permalink
어려운 거 하시는 군요. 으으으
-
daybreaker 2006/11/15 00:11 # M/D Permalink
뭐 그래도 재미는 있습니다.;
-
-
진실's 2006/11/14 18:07 # M/D Reply Permalink
그래서 내가 PS 안듣자나 -_ -..
지금 대전 테트리스 짜고 있어.. 덜덜덜ㅠ-
daybreaker 2006/11/15 00:12 # M/D Permalink
그래도 들어보는 건 강력히(?) 추천.
숙제하다가 gg치는 한이 있어도 문제 해결을 위해 어떤 식으로 아이디어를 짜내고 접근할 수 있는가를 많이 얻을 수 있는 것 같아.
-
-
lshlj 2006/11/14 19:25 # M/D Reply Permalink
위에 리플다신 분이 쓰신 id로 보니 '윤홍기'라는 학생 같네요. 물리학과 학생들이 linear algebra에 친숙한 이유는 양자역학 때문일 것 같아요. :)
P.S. 물리학과 복수전공에 도전해 보세요~ Stewart 교수님의 강의를 소화하신 분이라면.. -.--
daybreaker 2006/11/15 00:14 # M/D Permalink
그렇군요...
스튜어트 교수님의 일반물리(도대체 어째서 일반물리인지는 모르겠지만) 수업 마지막 부분이 양자행렬역학(....)이었죠;
그나저나 저 그거 소화...못 했습니다.;;;; 학점은 그럭저럭 받았지만 양자역학 쪽은 머리에 남은 게 거의 없고, 그 꺽쇠 쓰는 notation만, 말 그대로 notation 자체만 기억이 나는군요. ㅠ_ㅠ
-
-
진실's 2006/11/15 02:20 # M/D Reply Permalink
결론 : 나는 학점을 그럭저럭 받았다.
니 블로그 댓글에서 본 유머인데. 재밌네 ^_^ㅋㅋ-
daybreaker 2006/11/15 02:23 # M/D Permalink
-_-
정말로 그럭저럭인데.; B대 맞았음..이라고 굳이 말해줘야...
-
-
Yuyudevil 2006/11/15 02:59 # M/D Reply Permalink
(여러분 B 가 '그럭저럭' 이랍니다! 저는 이번 학기 두과목 F 거의 확정인데 말이죠.)
날뷁옹이 물리학 복전 하시는건 제가 경제학 복전을 고려하는것 만큼이나 자연스러운건데 스튜어트한테 가서 '제 지도교수님이 되주세요!' 하면서 도전 해보시죠 =3 -
polarnara 2006/11/15 03:50 # M/D Reply Permalink
아니에요 아직은 세 번밖에 안 들었어요...(...)
-
daybreaker 2006/11/16 03:00 # M/D Permalink
...곧 4번이 되실 테니...=3==3
-
-
MSerenity 2006/11/16 00:28 # M/D Reply Permalink
......문제 풀이가 감도 안 잡히는걸요;; PS듣는거 다시 고려해야하나... 그나저나 저 분은 정말로 ㅚㅜ라는 부류의 인간이군요 OTL 물리과엔 천재가 많다는 말이 역시 사실인거 같아요.
-
daybreaker 2006/11/16 03:04 # M/D Permalink
저거 처음에 전혀 감도 안 잡혔는데 막상 풀이를 보면 매우 간단하더라는...-_- 선형대수학으로 푸는 풀이 말고 일반적인 풀이는 임의의 한 점을 돌렸을 때 그 점이 다시 원래대로 돌아오려면 그 점에 의해 영향받는 가로/세로 줄 중에서 몇 번을 돌려야 함을 어떻게 알 수 있겠는가 하는 문제부터 시작하지.; (그리고 문제에서 판의 변 크기가 짝수로 주어진다는 것이 문제 풀이의 결정적 조건으로 작용하는데, 홀수가 되면 해를 구할 수 없는 경우가 생김)
ps. 교수님께서 수업 때 말씀하시길, 원래 본선 문제로 넣으려고 했는데 중국애들이 저런 문제를 너무 잘 풀어서 우리가 불리할까봐(..) 일부러 인터넷 예선으로 끌어내렸다고 하는 뒷이야기가 있음-_-;
-
-
SCV 2006/11/16 11:56 # M/D Reply Permalink
(과 정해야 되는데..)
물리과에 대한 두려움은 커져만 가고.. -
Ego君 2006/11/17 03:07 # M/D Reply Permalink
선형대수학,확률 통계 정말 중요하더군요. 제 주위의 게임회사 병특했던 모 선배는 게임엔진을 개발해서 병특 따고 돈 많이 벌었다는 이야기가(선대수와 물리를 좀 알면 된다고 하던가). 이번학기때 확률을 들었어야 하는데 (F받기 싫어서 수강 포기...먼산)
-
daybreaker 2006/11/20 01:05 # M/D Permalink
게임엔진이라면 3D는 기본이고, 충돌 검사, 지형 엔진 등이 들어가는데 벡터가 아주 기본으로 들어가지요. 알고리즘 문제를 풀 때도 어떤 공간을 어떤 벡터를 기준으로 나눴을 때 조사하려는 대상이 어느 쪽에 속하는지 알아볼 때에 cross product를 쓰기도 하고.. 활용도가 높죠.
-
-
LifeFeel 2006/11/17 09:45 # M/D Reply Permalink
내친구 중에서 ACM을 준비하는애가 있는데 내가보기엔 그 친구도 참 잘하지만 자기가 생각하기엔 꼭 그렇지만도 않은가보더라구.
그친구의 말로는 컴퓨터는 쉬운데 수학이 어렵다나... ㅋ-
daybreaker 2006/11/20 01:06 # M/D Permalink
문제 푸는 아이디어를 짜내는 것도 어렵지만, 그 아이디어를 구현하는 게 더 어렵더군요. (특히 한참 동안 삽질해서 답은 맞게 나오는데 Time limit 걸려서 알고리즘 자체를 처음부터 다시 설계해야 하는 상황이 발생하면....ㅠㅠ)
-
-
진혁군 2006/11/19 16:56 # M/D Reply Permalink
알고보면 나도 물리과 윤모군인데.. ㅋㅋㅋ
-
daybreaker 2006/11/20 01:07 # M/D Permalink
음.. -.-;
-
-
LifeFeel 2006/11/20 15:50 # M/D Reply Permalink
응 맞아맞아.. ㅋㅋ 그얘기도 들었어.
어떻게든 답을 구할 수 있는데 Time limit가...
몇십억년 몇월 몇일의 요일을 구하라 이런거 ㅡㅡ;; ㅋ-
daybreaker 2006/11/27 02:51 # M/D Permalink
날짜 관련된 문제들은 O(1)에 계산할 수 있는 일종의 공식 같은 게 있다고 들어본 것 같습니다. 정수론을 잘 이용하면 어찌어찌 되었던 것 같은데...-_-;
-
bluehope 2007/01/21 01:05 # M/D Permalink
하하 안녕하세요 제가그 물리과 윤모군입니다.
혹시 이런것을 이야기하는 걸까요?
친구가 정리해놓은건데
http://sein.isloco.com/2299178
비슷한거 같아서 링크걸어봅니다.
@억년정도면 어느 정치가가 달력을 바꿔버릴듯하군요 :$
-