[프로그래밍 해설] Prime ring problem

Prime ring 문제라는게 있다..

http://coding-quiz.blogspot.com/2008/08/prime-ring-problem.html

n 개의 빈칸이 원형으로 배치되어 있는데, 여기에 1 ~ n 의 수를 넣어서, 접해 있는 2개의 수의 합이 소수(prime number)가 되도록 배치하라는 문제이다.. 이런 문제는 필연적으로 순열 ( permutation ) 문제가 된다.. 1~n 까지 나열할 수 있는 모든 경우를 다 돌면서 조건을 만족하는지 검색해야 한다.. 문제는 순열이다..

1 ~ n 의 자연수로 나타낼 수 있는 모든 순열을 다 출력하는 것만으로도 조금 골치 아프다.. 조금이라도 정신이 제대로 박혀 있는 사람이라면 for 문을 n 개 돌려 가며 일일이 체크하는 삽질은 하지 않아야 한다.. 이거야 말로 O (n^n) 이라는 극악한 시간 복잡도가 나온다.. 다행히도 기존의 챈재들이 순열을 하나씩 차례대로 뽑아주는 알고리즘을 개발해 뒀다.. 자세한 알고리즘은 아래 레퍼런스에서 찾아 보면 된다..

[1] Kenneth H. Rosen, Discrete Mathematics and Its Applications, 2nd edition (NY: McGraw-Hill, 1991) pp. 282-284.
[2] Donald Knuth, "The Art of Computer Programming," vol 4, fasicle 2, "Generating all Tuples and Permutations", pp.. 39-40.

위 책들에 나와 있다고 한다.. 관심 있으면 알아서 찾아 보시라..

저 책들이 없더라도,, 구글에 "next permutation" 이란 검색어로 훑어 보면 수많은 물고기들이 낚이는데,, 그중 쓸만한 월척을 뽑아 보았다..
http://www.merriampark.com/perm.htm

JAVA 로 작성된 코드인데, class 를 생성한 뒤, getNext() 를 한번씩 부를때마다, 다음 순열이 하나씩 튀어나온다.. 다만 완료 조건을 팩토리얼을 계산해서 처리하는 구조이다 보니,, n = 20 까지 밖에 처리 못한다.. 하지만,, 완료 조건만 수정해 주면,, 더 큰 순열에 대해서도 처리가 가능하다..

여튼 이 코드를 이용한다면,, prime ring 문제는 아주 쉽게 해결된다.. 루프 돌리면서,, 각 순열이 prime ring 조건이 되면 출력해 주면 끝난다.. next pemutation 함수가 O(n) 이고,, 총 순열수는 n! 이므로,, O(n!) 의 시간복잡도가 나온다.. 사실,, 순열 문제는 죽으나 사나 O(n!) 이다..

하지만,, 실제 코딩을 해보면,, 상당히 느리다.. 요즘 컴퓨터가 워낙 빠르다 보니 n = 10 정도도 금방 출력해 주지만,, n = 16 쯤 되어도 하세월이 걸린다.. 이는 무작정 루프를 돌면 불필요한 순열을 계속 검사하기 때문이다.. 예를 들어 n = 6 일때 1 3 2 4 5 6 의 순서가 되었을때, 1+3 = 4 이므로 소수가 아니고,, 1 3 2 4 5 6 은 prime ring 이 아니다.. 그리고, 1 3 으로 시작하는 다른 모든 순열 역시 prime ring 이 아니다.. 즉, 1 3 으로 시작되는 다른 순열은 더 이상 볼 필요가 없고,, 1 4 로 시작하는 순열로 넘어 가면 된다.. 1 3 2 4 5 6  ~ 1 3 6 5 4 2 까지 24 가지 경우는 그냥 뛰어 넘어도 상관 없다.. n=6 일때야 겨우 24개 뿐이지만,, n = 16 일때는 14! = 약 871억 가지 경우를 뛰어 넘을 수 있게 된다.. 이런 기법을 backtracking 이라고 하는데,, 여튼 불필요한 경우를 아낌없이 가지치기 해주는 것이다..

그래서,, 이 문제는 다음 순열을 가져 오는 getNext() 을 그대로 쓰면 안되고,, 실제로 prime ring 의 후보가 될만한 다음 순열로 점프하는 것이 아주 중요하다..

사실 이 문제에서 가장 중요한 이 부분은 숙제로 남겨둔다.. 날로 먹으면 안된다.. 힌트 주는것만 해도 어딘가?

- 이쁜왕자 -
- Valken the SEXy THief~~ ^_* -

ps1> 이 문제는 원순열이라,, 1로 시작하는 경우만 검색하면 된다..
ps2> 2 를 제외한 모든 소수는 홀수이기 때문에, 홀수+짝수 (or 짝수+홀수) 가 아니면 고려할 필요조차 없다.. 그러므로,, 홀짝홀짝 순서인 경우를 먼저 검사해도 되지만,, 특별히 검색시간이 줄어들것 같아 보이지는 않는다..
ps3> n=16 일때 prime ring 의 갯수는 81024 개이다..

---

* 추가 * 

이런 저런 기법을 이용해서 속도를 빠르게 튜닝해 보았지만 별로 진전이 없었다. 그런데, 구조상 이는 재귀 호출로 구현이 가능할 듯 싶었고, 실제로 구현을 해보니 재귀 호출을 이용한 brute force 방식이 100배쯤 더 빠른 결과를 내 주었다. 때로는 단순한게 제일 빠르다.