존 호프크로프트 / 로버트 타잔

“좋은 아침”

연구실 문을 활기차게 열며 존은 아침인사를 날렸다. 단촐하게 책상 두 개와 책장 몇 개가 놓인 작은 방 안에는 머리가 부스스한 상태의 밥이 꾀죄죄한 몰골로 앉아 있었다.

“어제 잠을 잘 못 잔 모양이네. 얼굴이 말이 아니야.” 존은 웃으며 말했지만 짠한 마음이 들었다.

“좀 설친 것 같네요.” 말을 마치기가 무섭게 밥은 늘어지게 하품했다.

“너무 조급해 하지 마. 무슨 일이든 시간이 필요한 거니까.” 존은 자신이 대학원생이던 시절을 떠올렸다. 채 10년도 안 되었지만 아득하게 느껴졌다.

존이 스탠퍼드 대학교에서 안식년을 보낸 지도 어느 새 1년이 다 되어 갔다. 이제 원래의 자리로 돌아갈 때가 다 되었다. 따뜻한 미 서부를 떠나 추운 미 동부로 돌아가려니 뭔가가 다리를 붙잡는 듯했지만 그래도 그는 코넬 대학교가 좋았다. 전기 기술자를 꿈꾸던 그가 컴퓨터 과학이라는 신세계에 깊숙히 빠질 수 있었던 것은 코넬 대학교 덕분이었다. 그가 스탠퍼드에서 박사 학위 심사를 마칠 때만해도 미 동부에서 컴퓨터 과학을 하고 있으니라고는 상상도 하지 못했다. 인생이란 참으로 변화무쌍하다는 생각을 하며, 존은 그의 눈 앞에 앉아 있는 밥의 미래가 어떠할 지 가늠조차 되지 않았다.

밥은 이제 스탠퍼드 컴퓨터 과학과 대학원 2년 차였다. 대학원 2년 차 학생이 코넬 대학교 교수와 같은 방을 쓰게 된 것은 순전히 도널드 커누스 교수 때문이었다. 커누스 교수는 밥이 그래프의 평면성^planarity에 관한 연구를 하고 있음을 알고 있었다. 그래서 존 호프크로프트 교수가 안식년을 위해 스탠퍼드 컴퓨터 과학과에 온다고 했을 때 두 사람을 같은 방에 배정했다. 호프크로프트 교수가 알고리듬에 관심이 많음도 알고 있었기 때문이었다.

아홉 살의 나이 차이가 있기는 했지만 두 사람은 호흡이 잘 맞았다. 평면성을 확인하기 위한 알고리듬은 호프크로프트 교수에게도 흥미로운 주제였다. 일 년 사이에 두 사람은 상당한 성과를 거두었다. 기존의 방법보다 상당히 개선된 알고리듬을 고안한 지는 이미 오래 전이었다. 하지만 호프크로프트 교수는 거기서 멈추고 싶지 않았다. 더 나은 답을 얻을 수 있을 듯 보였다. 그는 밥에게 멈추지 말 것을 주문했다. 그가 원하는 답이란, 입력 데이터의 개수가 아주 많을 때도 현실적으로 사용 가능한 알고리듬이었다. 입력 데이터가 100개일 때 걸리는 시간이 100초라면 입력 데이터가 10,000개일 때는 10,000초에 끝나는 것이 이상적이었다. 하지만 기존의 방식은 입력 데이터가 10,000개가 되면 100,000,000초가 걸렸고, 그들이 그나마 개선한 알고리듬을 쓰더라도 40,000초가 걸렸다.

“아무래도 자료구조에 답이 있는 것 같습니다.”

어느 틈에 따뜻한 김이 모락모락 피어나는 커피를 머그잔에 담아들고 나타난 밥이 말했다.

“알고리듬만으로는 한계가 있습니다. 자료구조와 함께 고민해야 돌파구가 생길 것 같아요.”

사실, 존도 그렇게 생각해오던 터였다.

“무슨 좋은 아이디어가 있나?”

“그게 말이죠. 스택을 두 개 써 보는 겁니다. 번갈아가면서 왔다갔다 데이터를 돌리면 어떨까요?”

“오, 그거 완전히 새로운 발상인데. 흥미로워. 여기 앉아서 좀 구체적으로 설명해줘.”

밥은 의자를 끌고 와서 존 옆에 앉았다. 커피의 카페인이 혈관을 한바퀴 돌며 뇌에 끼어 있는 노폐물을 쓸어버린 듯 머리가 맑아졌다. 공책의 새로운 페이지를 펼쳐 놓고 밥은 연필로 그래프를 하나 그리기 시작했다. 종이 위에 흑연이 쓸리는 소리가 경쾌했다.

1 2 3 4 5