오늘 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. 이참에 물리과 복수전공을...?! ;;;