[논문]마방진 알고리즘

이상운

doi:10.7236/jiibc.2017.17.3.159

마방진 알고리즘
The Magic Square Algorithm 원문보기

The journal of the institute of internet, broadcasting and communication : JIIBC, v.17 no.3, 2017년, pp.159 - 166

초록
AI-Helper

본 논문은 홀수, 이중 짝수와 단일 짝수 마방진 알고리즘을 제안하였다. 홀수 마방진은 de la $Loub{\grave{e}}re$가 제안한 방법으로 $O(n^2)$회를 수행하는 단점이 있다. 이중 짝수 마방진은 2가지의 교차 알고리즘이 제안되었다. 단일 짝수 마방진은 ${\frac{n}{2}}{\times}{\frac{n}{2}}$의 홀수 마방진에 기반하여 여러 가지 방법이 제안되었지만 Strachey 알고리즘이 적용이 가장 쉽다. 본 논문에서는 홀수 마방진에 대해 3회 수행, 이중 짝수 마방진에 대해서는 4회 수행으로 마방진을 얻는 방법을 제안하였다. 또한, 단일 짝수 마방진에 대해서는 홀수 마방진에 기반을 두지 않고 직접 구하는 알고리즘을 제안하였다.

Abstract ▼ AI-Helper

This paper proposes an algorithm for odd, doubly even, and singly even magic squares. In constructing an odd magic square, de la $Loub{\grave{e}}re^{\prime}s$ method is widely known and used, but it has an inherent defect of executing $O(n^2)$ steps. 2 types of cross algorithms have been proposed to the double even magic square, and more to the singly even magic square based on the odd magic square of ${\frac{n}{2}}{\times}{\frac{n}{2}}$, the most popular and simple of which is one proposed by Strachey. The algorithm proposed in this paper successfully constructs odd and doubly even magic squares by undergoing 3 steps and 4 steps respectively. It also directly constructs a singly even magic square without having its basis on the odd magic square.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 홀수 마방진에 대해 de la Loubère[4-6]의 O(n2)을 3회로 단축시킨 알고리즘을 제안하였으며, 이중 짝수 마방진에 대해 3회로 단축시켜 Conway의 Lozenge 방법[2,3,7]과 유사한 복잡도를 나타냄을 알 수 있다.

제안 방법

결국, 모든 마방진을 얻기 위해서는 단일 짝수 마방진과 이중 짝수 마방진을 간단히 구하면 된다. 그러나 본 절에서는 단일 짝수 마방진을 홀수 마방진에 기반하여 만들지 않고 직접 만드는 방법을 제안한다. 여기서는 n=6을 대상으로 설명하며, 알고리즘을 적용한 결과는 그림 12에 제시되어 있다.
과 유사한 복잡도를 나타냄을 알 수 있다. 또한, 단일 짝수에 대해 홀수 마방진을 이용하지 않고 직접 구하는 알고리즘을 제안하였다. 결론적으로 마방진 게임에 대해 본 제안된 알고리즘의 규칙을 적용하면 쉽게 해를 구할 수 있는 장점이 있다.
본 논문은 홀수 마방진에 대해 3회 수행으로 마방진을 만드는 방법을, 이중 짝수 마방진에 대해 4회 수행으로 마방진을 만드는 방법을 제안한다. 또한, 단일 짝수에 대해 홀수 마방진을 적용하지 않고 직접 구하는 방법을 제안한다. 2장에서는 기존의 마방진을 만드는 알고리즘을 고찰한다.
본 논문은 홀수 마방진에 대해 3회 수행으로 마방진을 만드는 방법을, 이중 짝수 마방진에 대해 4회 수행으로 마방진을 만드는 방법을 제안한다. 또한, 단일 짝수에 대해 홀수 마방진을 적용하지 않고 직접 구하는 방법을 제안한다.

이론/모형

n이 단일 짝수인 6,10,14,⋯에 대한 알고리즘은 3개가 제안되어 있다. 첫 번째 방법은 Barink의 Madjig^[1]를 이용하는 알고리즘으로 다음과 같이 수행되며, n=6에 대한 마방진은 그림 4에 제시되어 있다.

성능/효과

또한, 단일 짝수에 대해 홀수 마방진을 이용하지 않고 직접 구하는 알고리즘을 제안하였다. 결론적으로 마방진 게임에 대해 본 제안된 알고리즘의 규칙을 적용하면 쉽게 해를 구할 수 있는 장점이 있다.

질의응답

핵심어	질문	논문에서 추출한 답변
	단일 짝수 마방진의 알고리즘으로 무엇이 있는가?	이중 짝수 마방진은 2가지의 교차(cross) 방법이 적용된다.[1-3] 단일 짝수 마방진은 Madjig를 이용하는 방법[1], Strachey[3,4] 방법과 Conway[2,3,7]의 LUX 방법이 있다. 이외에도 Kim과 Yoo[8]은 곱셈법을 적용하였으며, Jacob과 Murugan[9]은 이중 짝수 마방진을 구성하는 방법을, Chen et al.
	숫자 n의 마방진은 무엇인가?	숫자 n의 마방진(magic square)은 n×n= n2개의 셀로 이루어져 있으며, 가로, 세로와 대각선 방향의 합이 모두 이 되는 n×n 행렬 숫자 배열표이다. 일반적으로 마방진의 각 셀에는 1부터 n2까지 수가 한 개씩 들어간다.
	n이 홀수인 경우 de la Loubère의 마방진 알고리즘은 어떻게 수행 되는가?	(1) 첫 번째 행의 가운데 열에 1을 넣는다. (2) 그 다음 숫자를 원래 칸의 오른쪽 위에 넣는다. 2-1. 만약, 해당하는 칸이 마방진의 위쪽으로 벗어난 경우에는 가장 아래쪽의 칸으로, 마방진의 오른쪽으로 벗어나는 경우는 가장 왼쪽의 칸으로 이동한다. 2-2. 만약 마방진의 오른쪽 위인 경우에는 원래 위치에서 한 칸 아래로 이동한다.

참고문헌 (10)

Wikipedia, "Magic Square," http://en.wikipedia.org/wiki/Magic_square, Wikimedia Foundation Inc., 2015.
E. W. Weisstein, "Magic Square," http://mathworld.wolfram.com/MagicSquare.html, Wolfram Research. Inc., 2015.
P. Ballew, "Magic Squares Report," http://www.pballew.net/MagSqRpt.doc, 2015.
W. W. R. Ball, "Mathematical Recreations and Essays," London. Macmillan & Co Ltd, 1959.
de la Loubere, "A new historical relation of the Kingdom of Siam, Du Roykume de Siam, 1693.
M. Kraitchik, "Magic Squares," New York: Norton, pp. 142-192, 1942.
E. R. Berlekamp, J. H. Conway, and R. K. Guy, "Winning Ways for Your Mathematical Plays, Vol. 2: Games in Particular," Academic Press, London, 1982.
Y. K. Kim and J. C. Yoo, "An Algorithm for Constructing Magic Squares," Discrete Applied Mathematics, Vol. 156, No. 14, pp. 2804-2809, Jul. 2008. DOI: https://doi.org/10.1016/j.dam.2007.09.029

상세보기
G. Jacob and A. Murugan, "On the Construction of Doubly Even Order Magic Squares," Cornell University Library, arXiv:1402.3273, pp. 1-5, Feb. 2014.
J. Chen, T. S. Chen, Y. M. Hsu, and K. Wu, "A Heuristic Magic Square Algorithm for Optimization of Pixel Pair Modification," Electrical Engineering and Control, Lecture Notes in Electrical Engineering, Vol. 98, pp. 765-772, 2011. DOI: https://doi.org/10.1007/978-3-642-21765-4_95

저자의 다른 논문 :

원문 URL 링크

DOI : 10.7236/JIIBC.2017.17.3.159 [무료]
한국인터넷방송통신학회 : 저널
학술교육원 : 저널
AccessON : 저널

*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.

오픈액세스(OA) 유형

BRONZE

출판사/학술단체 등이 한시적으로 특별한 프로모션 또는 일정기간 경과 후 접근을 허용하여, 출판사/학술단체 등의 사이트에서 이용 가능한 논문

연관된 기능

이 논문과 함께 이용한 콘텐츠

저작권 관리 안내

내보내기 메뉴

내보내기 구분

파일저장
인쇄
메일전송

구성항목

기본정보
상세정보

관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관

저장형식

Text(ASCII format)
Excel format
RefWorks Direct Export
RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley

메일정보

받는사람 (필수): @
보내는사람 (선택): @
제목
내용: KISTI 검색결과 이메일 서비스

안내

총 건의 자료가 검색되었습니다.

다운받으실 자료의 인덱스를 입력하세요. (1-10,000)

검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다.

데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요)

다운로드 파일은 UTF-8 형태로 저장됩니다.
파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오.

Text(ASCII format)
Excel format

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

AI-Helper ※ AI-Helper는 을 사용합니다.

AI-Helper

안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

연합인증