G-SQL 재미있는 DB 이야기 ‘놀라운 마방진의 세계’

재미있는 DB 이야기 ‘놀라운 마방진의 세계’

성공과 실패의 경험을 나누자, 용기와 희망을 나누자

개발업무를 시작으로 IT계에 입문했던 필자가 10년 가까이 DB엔지니어로서 활동하면서 얻은 경험과 지식을 나누고자 한다. DB를 자주 접하는 SW 개발자뿐 아니라, DB 전문가를 꿈꾸는 대학생에서DB 분야에 입문한지 1~2년 된 기입문자가 쉽게 이해할 수 있도록 비유를 통해 쉽게 접근해볼 계획이다. 물론 전문가들이라도 다시 한번 개념을 정립하는 의미에서 필요한 내용이 될 수 있다.

전체적으로 DB의 기본 원리와 개념을 이해하고 테이블, 인덱스, 쿼리, 튜닝, 플랜 등 개발자들이 알아야 하는 DB 전분야에 대해 쉽게 이해하도록 설명하겠다. DB 기술서적이나 번역서보다는 조금 더 부드럽게 접근할 계획이다. 그렇다고 흔히 서점에서 만날 수 있는 개발자 위주의 SQL 소개서도 아니다. 이 연재는 시리즈로 나갈 것이다. 연재를 끝까지 읽는 독자라면 준전문가 수준의 DB 원리를 아는 것을 목표로 한다.

마방진의 유래

중국 하나라의 우왕 시대에 매년 황하가 범람하여 물이 흐르는 길을 고치는 공사를 했는데, 어느 해에 큰 거북이 나타나서 잡았는데 이 거북의 등에 신비한 무늬가 새겨져 있었다고 한다. 거북의 등에 새겨진 그림은 1부터 9까지의 숫자를 점의 개수로 나타낸 것이었고 자세히 살펴보니 놀랍게도 가로, 세로, 대각선의 합이 항상 15로 같았다고 한다. 이것이 바로 마방진의 시초라고 전해지는 이야기다. 당시 사람들은 이것을 아주 귀하게 여겨서 '낙서(洛書)'라고 이름을 지었다. 마방진이라는 명칭은 방진에 빠지면 마귀에게 홀린 듯 빠져 나올 수 없다고 하여 마귀 마(魔)자를 붙였다고 한다. 

거북의 등에 그려진 신기한 수의 배열에서 유래된 마방진에 대한 기본 규칙은 아래 [그림 1]과 같으며 1부터 n2까지의 연속된 자연수를 가로, 세로, 대각선의 합이 같도록 수를 배치 해야 한다.



[그림 1] 마방진의 기본 규칙

동양에서 마방진은 중국 송나라 때의 양휘산법이라는 책에서 최초로 소개 되었는데, 여기에서 8방진까지 설명하고 있다. 한국에서는 조선 숙종 때 영의정을 지낸 수학자 최석정이 절묘한 방진을 발견하여 그의 저서 『구수략』에 실었다. 유럽에서 마방진은 한때 점성술의 대상이 되기도 하였으며, 마방진을 새긴 부적 등이 만들어지기도 했으며 페르마, 오일러 등이 방진을 연구 하였다. 지금도 세계적으로 수많은 사람들이 새로운 마방진을 발견하고자 노력하고 있다. 마방진은 현재 진행형이다.

3차 마방진

마방진의 가장 기본인 3 x 3 마방진에 대해서 알아 보자. 1부터 9까지의 숫자를 한 번씩만 사용하며 가로, 세로, 대각선의 합이 같아야 한다. 



[그림 2] 3 x 3 마방진 구현 방법

3차 마방진 구현 방법은 위의 [그림 2]처럼 일정한 패턴이 있다. 이 방법은 3차, 5차, 7차 등 홀수 마방진에 동일하게 적용된다. 홀수 마방진은 쿼리로도 구현 가능한데, 검색 사이트에서 검색한 결과 다음과 같은 마방진 쿼리를 검색할 수 있었다.

SELECT TRIM(MAX(SYS_CONNECT_BY_PATH(LPAD(NO,LENGTH(POWER(:NUM,2)),'0'),' '))) AS BANGGIN FROM ( SELECT ((A.NO-1) * :NUM) + B.NO NO , CASE WHEN A.X - B.MV > 0 THEN A.X - B.MV ELSE :NUM + (A.X - B.MV) END AS X , CASE WHEN A.Y - B.MV > 0 THEN A.Y - B.MV ELSE :NUM + (A.Y - B.MV) END AS Y FROM ( SELECT LEVEL AS NO , MOD((:NUM + 1) / 2 + LEVEL - 2, :NUM) + 1 AS X , :NUM - MOD((:NUM + 1) / 2 + LEVEL - 1, :NUM) AS Y FROM DUAL CONNECT BY LEVEL < = :NUM ) A ,( SELECT LEVEL AS NO , LEVEL - 1 AS MV FROM DUAL CONNECT BY LEVEL < = :NUM ) B ) START WITH X = 1 CONNECT BY PRIOR X = X - 1 AND PRIOR Y = Y GROUP BY Y ORDER BY Y

위의 쿼리를 보면 정말 놀랍다. 작성한 이가 누군진 몰라도 대단하다는 생각이 든다. 하지만 홀수 마방진에 국한되고 한 가지 패턴만 가능하다는 것이 문제다. 필자는 다른 방법으로 마방진 쿼리를 생각해 보았다. 



[그림 3] 3 x 3 마방진 쿼리 구현 원리

[그림 3] 처럼 3 x 3 마방진 각 위치를 A에서 I까지 변수로 치환하여 다음과 같은 쿼리로 작성하였다.

WITH TMP AS ( SELECT * FROM (SELECT LEVEL A FROM DUAL CONNECT BY LEVEL < = 9), -- 1행 1열 (SELECT LEVEL B FROM DUAL CONNECT BY LEVEL < = 9), -- 1행 2열 (SELECT LEVEL C FROM DUAL CONNECT BY LEVEL < = 9), -- 1행 3열 (SELECT LEVEL D FROM DUAL CONNECT BY LEVEL < = 9), -- 2행 1열 (SELECT LEVEL E FROM DUAL CONNECT BY LEVEL < = 9), -- 2행 2열 (SELECT LEVEL F FROM DUAL CONNECT BY LEVEL < = 9), -- 2행 3열 (SELECT LEVEL G FROM DUAL CONNECT BY LEVEL < = 9), -- 3행 1열 (SELECT LEVEL H FROM DUAL CONNECT BY LEVEL < = 9), -- 3행 2열 (SELECT LEVEL I FROM DUAL CONNECT BY LEVEL < = 9) -- 3행 3열 ) SELECT * FROM TMP WHERE A + B + C = 15 -- 가로 AND D + E + F = 15 -- 가로 AND G + H + I = 15 -- 가로 AND A + D + G = 15 -- 세로 AND B + E + H = 15 -- 세로 AND C + F + I = 15 -- 세로 AND A + E + I = 15 -- 대각선 AND C + E + G = 15 -- 대각선 AND A * B * C * D * E * F * G * H * I = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 AND ROUND(1/A + 1/B + 1/C + 1/D + 1/E + 1/F + 1/G + 1/H + 1/I, 5) = ROUND(1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9, 5)

구현한 쿼리를 간단히 설명하면 다음과 같다. 

1. 마방진 각각의 위치 값을 집합으로 정의한다. 
2. 가로, 세로, 대각선의 합이 15이다. 
3. 숫자는 1부터 9까지 한 번씩만 사용한다. 

쿼리를 실행하면 8개의 결과가 리턴되지만 동서남북 4방향으로의 회전에 따른 4개와 더불어 각각을 거울에 비친 반대의 경우도 있으므로 8로 나누어야 한다. 그러므로 실제 3 x 3 마방진의 패턴은 하나임을 알 수 있다. 또한 우리는 마방진 위치 값에 대한 집합의 크기에 대해서 알아야 할 필요가 있다. 

9 * 9 * 9 * 9 * 9 * 9 * 9 * 9 * 9 = 387,420,489

3억 건이 넘는 어마어마한 크기다. 하지만 실제 쿼리 수행 시간은 1초 미만이었다. 왜냐하면 FROM 절에서 엄청난 부하가 예상되었지만 실제로는 조인 전에 이미 조건절에 대한 필터가 먼저 발생했기 때문이다.

즉 조인절이 모두 끝난 후에 조건절이 실행된 것이 아니라, 조인절 진행 중간 중간에 조건절이 실행되었기 때문에 실제 작업 대상인 집합의 크기가 많이 줄었다.

4차 마방진

3차 마방진은 패턴이 한 가지인데 비해 4차 마방진은 수많은 패턴이 있다. 패턴에 의한 쿼리로 구현하기보다는 집합에 의한 쿼리로 구현해야만 4차 마방진을 만족하는 모든 패턴을 한 번에 구할 수 있다.

WITH TMP AS ( SELECT * FROM (SELECT LEVEL A FROM DUAL CONNECT BY LEVEL < = 16), -- 1행 1열 (SELECT LEVEL B FROM DUAL CONNECT BY LEVEL < = 16), -- 1행 2열 (SELECT LEVEL C FROM DUAL CONNECT BY LEVEL < = 16), -- 1행 3열 (SELECT LEVEL D FROM DUAL CONNECT BY LEVEL < = 16), -- 1행 4열 (SELECT LEVEL E FROM DUAL CONNECT BY LEVEL < = 16), -- 2행 1열 (SELECT LEVEL F FROM DUAL CONNECT BY LEVEL < = 16), -- 2행 2열 (SELECT LEVEL G FROM DUAL CONNECT BY LEVEL < = 16), -- 2행 3열 (SELECT LEVEL H FROM DUAL CONNECT BY LEVEL < = 16), -- 2행 4열 (SELECT LEVEL I FROM DUAL CONNECT BY LEVEL < = 16), -- 3행 1열 (SELECT LEVEL J FROM DUAL CONNECT BY LEVEL < = 16), -- 3행 2열 (SELECT LEVEL K FROM DUAL CONNECT BY LEVEL < = 16), -- 3행 3열 (SELECT LEVEL L FROM DUAL CONNECT BY LEVEL < = 16), -- 3행 4열 (SELECT LEVEL M FROM DUAL CONNECT BY LEVEL < = 16), -- 4행 1열 (SELECT LEVEL N FROM DUAL CONNECT BY LEVEL < = 16), -- 4행 2열 (SELECT LEVEL O FROM DUAL CONNECT BY LEVEL < = 16), -- 4행 3열 (SELECT LEVEL P FROM DUAL CONNECT BY LEVEL < = 16) -- 4행 4열 ) SELECT * FROM TMP WHERE A + B + C + D = 34 -- 가로 AND E + F + G + H = 34 -- 가로 AND I + J + K + L = 34 -- 가로 AND M + N + O + P = 34 -- 가로 AND A + E + I + M = 34 -- 세로 AND B + F + J + N = 34 -- 세로 AND C + G + K + O = 34 -- 세로 AND D + H + L + P = 34 -- 세로 AND A + F + K + P = 34 -- 대각선 AND D + G + J + M = 34 -- 대각선 AND A*B*C*D*E*F*G*H*I*J*K*L*M*N*O*P = 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16 AND ROUND(1/A+1/B+1/C+1/D+1/E+1/F+1/G+1/H+1/I+1/J+1/K+1/L+1/M+1/N+1/O+1/P,5) = ROUND(1/1+1/2+1/3+1/4+1/5+1/6+1/7+1/8+1/9+1/10+1/11+1/12+1/13+1/14+1/15+1/16,5)

위의 쿼리를 실행한 결과 7,040개의 레코드가 리턴되었다. 동서남북 4방향으로의 회전에 따른 4개와 더불어 각각을 거울에 비친 반대의 경우도 있으므로 8로 나누어야 한다. 그러므로 실제 4 x 4 마방진은 880개의 패턴이 있음을 알 수 있다. 

16*16*16*16*16*16*16*16*16*16*16*16*16*16*16*16 = 18,446,744,073,709,551,616 

4 x 4 마방진 위치 값에 대한 집합의 크기가 1,844경으로 엄청나다. 그렇다면 쿼리 수행 시간은 얼마나 걸릴까? 필자가 실행한 결과 15시간이 걸렸다. ㅠㅠ 

컴퓨터가 존재하기 이전 옛날에는 4차 마방진 880개 모두를 구하기 위해서는 평생을 바쳐야 했지만 지금은 하루 만에 구할 수 있으므로 그나마 위안이 된다.

경축! 아무것도 안하여 에스천사게임즈가 새로운 모습으로 재오픈 하였습니다.
어린이용이며, 설치가 필요없는 브라우저 게임입니다.
https://s1004games.com

4차 슈퍼 마방진

4차 마방진은 가로 4줄, 세로 4줄, 대각선 2줄 포함하여 총 10가지 경우의 합만 같으면 되지만, 4차 슈퍼 마방진은 [그림 4]와 같이 총 56가지 경우의 합이 모두 같아야 한다. 쿼리를 작성하여 실행해 보면 48개의 레코드가 리턴 된다. 8로 나누면 결국 6개의 4 x 4 슈퍼 마방진 패턴이 존재함을 알 수 있다. 

16*16*16*16*16*16*16*16*16*16*16*16*16*16*16*16 = 18,446,744,073,709,551,616

4 x 4 슈퍼 마방진 위치 값에 대한 집합의 크기는 1,844경으로 4 x 4 마방진과 동일함을 우리는 안다. 그렇다면 쿼리 수행 시간은 얼마나 걸릴까? 필자가 실행한 결과 수초에 불과했다. 

4 x 4 마방진 쿼리 수행 시간 : 15시간 
4 x 4 슈퍼 마방진 수행 시간 : 수초 

이와 같이 쿼리 수행 시간이 극단적으로 차이 나는 이유는 무엇일까? 4차 마방진의 조건절은 10개에 불과한데, 4차 슈퍼 마방진의 조건절은 56개로 훨씬 더 많기 때문이다. 또한 조인절 이전에 이미 조건절에 대한 필터가 먼저 발생했다. 즉 조인절 진행 중간 중간에 조건절이 먼저 실행되어서 집합의 규모가 크게 줄었기 때문이다. 이와 같은 사례는 배치 프로그램의 튜닝에서 자주 경험할 수 있다. 

아래 [그림 4]에서 4차 슈퍼 마방진의 실제 예를 살펴 볼 수 있다. 
 

[그림 4] 4 x 4 슈퍼 마방진의 규칙과 예시

3차 입체 마방진

마방진의 가장 기본인 3 x 3 마방진이 3층으로 쌓여진 3 x 3 x 3 입체 마방진에 대해서 알아 보자. 입체 마방진은 각 면 또는 단면에서 가로줄, 세로줄, 대각선, 그리고 입체대각선의 합이 같은 것을 의미한다. 지금까지 3차 입체 마방진은 아직 발견하지 못한 것으로 알려져 있었다. 



[그림 5] 3 x 3 x 3 입체 마방진

입체 마방진의 존재를 주장하는 사람들 혹은 지금도 입체 마방진을 찾으려고 노력하는 사람들이 실망할 지도 모르지만, 필자가 쿼리로 작성해서 확인한 결과 3차 입체 마방진은 존재하지 않았다. 단지, 위의 [그림 5]와 같이 대각선을 제외한 가로, 세로의 합이 같은 3차 입체 마방진은 존재함을 확인했다.

기타 각종 마방진

지금까지 3차 마방진, 4차 마방진, 4차 슈퍼 마방진, 3차 입체 마방진 등을 살펴 보았다. 마방진은 이외에도 무수히 많지만 몇 가지만 더 간단히 살펴보자.



[그림 6] 기타 각종 마방진

홀수 마방진: 홀수 1 ~ 17까지 숫자를 이용하여 가로, 세로, 대각선의 합이 같다.
짝수 마방진: 짝수 2 ~ 18까지 숫자를 이용하여 가로, 세로, 대각선의 합이 같다.
사토르 마방진: 가로로 읽으나 세로로 읽으나 똑같이 읽히는 다음절의 문장 
문자 마방진: 각각의 문자는 가로, 세로, 대각선에 오로지 하나만 존재한다.
색깔 마방진: 각각의 색깔은 가로, 세로, 대각선에 오로지 하나만 존재한다.
도형 마방진: 도형의 각 변의 숫자의 합은 같다.

이와 같이 수많은 종류의 마방진이 있으며, 각각의 마방진은 N차로 확장 가능하다. 

이번 연재에서는 마방진의 원리에 대해서 알아 보았고, 마방진을 구현하는 쿼리 작성 방법에 대해서도 이해하였다. 대부분의 마방진은 쿼리로 작성 가능하다. 다음 연재의 내용은 오라클 블록에 관한 것이다. 오라클 블록은 데이터가 저장되는 디스크의 공간을 의미하는데, 오라클 블록에 대해서 이해하고 블록과 오라클 성능을 연계해 설명한다. 블록은 튜닝에 있어서 중요한 한 부분이다.

[지난 문제의 정답과 풀이] 원리를 이해하고 논리로 풀어가는, 쉬어가는 DB 문제

지난 연재에 출제한 ‘원리를 이해하고 논리로 풀어가는, 쉬어가는 DB 문제’에 대한 정답과 해설은 아래와 같다. 문제를 풀면서 DB 원리를 하나씩 배우고 이해할 수 있다.

[이번 호 문제] 원리를 이해하고 논리로 풀어가는, 쉬어가는 DB 문제

각 연재의 말미에 간단하면서도 재미있고 생각해 보는 문제를 출제하려 한다. 모든 문제는 DB의 원리를 이해할 수 있는 문제로 출제할 예정이다. 문제를 풀면서 DB 원리를 하나씩 배우고 이해할 수 있다. 정답과 그에 대한 설명은 다음 연재에서 한다.


 

출처 : 한국데이터베이스진흥원

제공 : 데이터 전문가 지식포털 DBguide.net