Re: 마방진에 대한 추억 Aaram Yun <aaramMMMM@pantheon.yale.edu> Date : 5 Mar 1998 00:54:30 GMT Message-ID : <6dkt46$2hf$1@photon.hgs.yale.edu> Newsgroups : han.sci.math Aaram Yun <aaramMMMM@pantheon.yale.edu> wrote: : 이 이야기를 보니까 자꾸 생각나는 것은 전에 어떤 잡지에선가 읽은 Herbert Wilf : 라는 조합수학자의 'What is an answer?'라는 재미있는 제목의 글이었습니다. : 그의 글의 요지는, 어떤 문제를 풀었다고 할 때, 그 답이란 상당히 다양한 형태를 : 띨 수 있다는 것입니다. 이 사람이 생각하는 문제의 전형은 그러니까 어떤 : 조합수학적인 대상입니다. 마방진이라고 하면 좋겠지요. 그런 조합적 대상이 : 있으면 그에 대한 문제는 '그것들이 어떻게 생겨먹었냐?'라는 것이 될 것입니다. : 가장 좋은 답은 그 대상들을 체계적으로 모두 생성할 수 있는 방법을 보이고 : 그 갯수 및 그 대상들을 규정할 만한 다른 중요한 정보들을 제공하는 것입니다. : 식으로 쓸 수 있으면 좋을 것입니다. 급히 덧붙이자면 위에서 이야기한 '답 다움'의 리스트는 , 꼭 그 리스트의 뒷쪽에 나와 있다고 해서 나쁘다는 것은 아닙니다. 리스트의 위쪽에 있을 수록 좋은 것임은 분명하고, 그리고 리스트의 위쪽에 있는 답을 얻을 수 있는 상황에서 아래쪽에 있는 답 밖에 얻지 못했다면 문제가 있기는 할 것입니다. 하지만 문제에 따라서는 원래부터 그런 깨끗한 답이 나오지 않는 성격의 문제들이 있습니다. 아마도 이 리스트의 거의 맨 바닥에 있는 것이 최대로 기대할 수 있는 것일 그런 비관적인 상황도 있을 것입니다. 그런 경우에는 그런 답이라도 얻어낸다면 좋은 답으로 인정될 수 있습니다. 마방진의 경우 여태까지 알려진 모든 'n차 마방진의 총 갯수'가 컴퓨터를 돌려서 알려지거나 그런 데다가 n=5까지밖에 알려진 것이 없는 불쌍한 상황입니다. 짐작에 그 '답 다움'의 리스트에서 맨 위에 있는 것과 같은 깨끗한 답을 얻는 것이 원천적으로 불가능한 문제인지도 모릅니다. 그렇다면 아마도 이정구씨의 답 같은 형태의 답이 유일한 가능성인지도 모르지요. 이제 따져보아야 할 것은 그 답이 , 또는 답들이 얼마나 효율적인 알고리즘인가입니다. 계산은 어차피 n이 커지면 못하니까 계산에 치이지 말고 ...라고 말하더라도 알고리즘의 효율성을 따지는 것은 필수적입니다. 왜냐하면, 만일 알고리즘의 효율성을 따지지 않는다면 저도 사실은 n차 마방진을 완벽히 풀었기 때문입니다: n차 마방진이 모두 몇 개 있냐고요? n차 마방진을 모두 다 생성해 보십시오. 정확히 그 갯수만큼 있습니다. 어떻게 생성하냐고요? 하나 하나 숫자를 넣어 봅시다. 그 결과가 마방진이면 좋고, 아니면 다른 숫자를 넣으면 됩니다. 에헴. 근데 전산학 하시는 분들 혹시 이런 것에 대한 결과 모르십니까? 예를 들어 n차 마방진을 모두 생성하는 문제의 time complexity같은 것에 대해 나와있는 결과가 있는지요.