God's algorithm

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

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

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

위키피디아 링크(큐브)

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

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

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

쨌든, 결론은 이거였다.

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

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

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

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