Somnipathy

Rubik's Cube는 Erno Rubik이라는 아저씨가 처음 발명했다. 일반적인 형태는 3x3x3 정육면체 모양이고, 6면의 색깔을 모두 맞추는게 퍼즐의 목표다.

어릴 때 외삼촌이 가지고 온 큐브를 만진 적이 있지만, 본격적으로 큐브를 시작했던건 2004년이다. 엄마 졸라서 비싼거 사서 놀았었다. (지금은 큐브들 다 주변 사람들 나눠주고 하나도 없다 ㅠㅠ)

25주년 기념 큐브도 있었는데... ㅠㅠ

어쨌든 요즘 알고리즘 생각 -> 큐브 맞추는 알고리즘 -> 큐브 로 생각이 넘어오면서 간만에 추억에 잠겨 결국 큐브를 지르고야 말았다!! 무려 인터넷 판매샵에서 18900원에 파는;; 예전에 길들인 좋은 큐브들이 다 사라진 마당에 입문용 일반 큐브를 샀다간 마음에 들지 않을 것 같아서 요즘 제일 잘나간다는 큐브로 질러버렸다.

어쩐지 당분간은 큐브에 빠져서 살 것 같다. 더불어 나는 CS전공자니까 알고리즘을 이용해서 일반적으로 사람들이 많이 쓰는 프리드리히 해법 같은, 사람들이 보고 배울 수 있는 큐브 해법을 체계적으로 알고리즘을 통해 만들어 봐야겠다!

-- 여담 --

우리나라의 최초의 큐브 동호회가 있었다. 현재는 카페가 망하고 다른 카페가 활동이 많은 것 같지만, 우리나라의 한 중학교였나? 그곳의 수학선생님이 카페를 만들었었는데 나는 처음 그곳에서 큐브를 배웠었다. 우리나라에서 아마 어느정도 규모로 큰 동호회 중에 최초로 생긴 동호회일 듯?

그리고 나는 예전에 대구에서 살았는데, 대구 정기모임이 처음 생기던 날 그 정기모임에 내가 있었다! 하하하<del>아무도 안물었어</del>

어쨌든 그냥 그렇다고..

오늘 저녁을 먹고 집으로 돌아오는 길에, 갑자기 불현듯이 뭔가가 떠올랐는데 큐브의 해법, 정확히는 큐브를 최소 회전으로 맞추는 해법을 찾아주는 알고리즘을 짜보는 게 어떨까? 하는 생각이 들었다. 일단 요즘 머리를 너무 안쓰면서 사는 것 같기도 하고(...) 요즘 의욕에 넘쳐서 무언갈 막 하고 싶은데, 막상 할 줄 아는 것도 별로 없고, 몇천줄짜리 코딩을 미친듯이 해보고 싶지만 마땅히 코딩할만한 소재도 없고 해서 재미없던 참이어서 갑자기 떠오른 저 생각이 반가웠다.

그래서 스스로 고민해서 해법을 찾아보자! 하고 집에 돌아오는 길에 고민을 해봤는데, 아무리 생각해도 너무 어려워서..ㅋㅋ

큐브가 뭔지는 다음의 링크에서 확인.

위키피디아 링크(큐브)

일단 일반적으로 많이 알려진 해법이 있는지 검색을 해보았다.

딱 눈에 띄던게 바로 God's Algorithm 이었다. 알고리즘이 어떤건진 다음의 링크를 참조하시길.

위키피디아 링크 (God's algorithm)

쨌든, 결론은 이거였다.

큐브의 해법을 찾는건 NP문제이고(...) 내가 고민해봤자 효율적인 알고리즘은 못짬(...)

아무튼 NP문제라면 일반적인 방식말고, 휴리스틱으로 접근해서 문제 해결을 해야할텐데 고민을 좀 해봐야겠다. God's algorithm 이라길래 구체적인 알고리즘이 있는 줄 알았는데, 결국 뒤숭숭하게 그냥 이야기 였음..;

어쨌든 덧붙여서 algorithm 카테고리가 mathematics 카테고리 아래에 있으니 수학적인 이야기도 하자면, 일반적인 n^3 크기의 큐브를 맞추는 데 필요한 최대 회전수는 n^2/log(n) 에 비례한다고 한다. 그리고 3x3x3 큐브에 한정해보면, 3x3x3 큐브의 모든 경우에 대해 20회전 이내의 회전으로 맞출 수 있다는 것이 2010년에 증명되었다고 한다.

세상엔 참 똑똑한 사람들이 많은 듯...