[자료구조]C++ 마방진 생성과 시간복잡도

1. 문제개요

C++을 이용하여서 Magic Square(마방진)을 생성하는 프로그램을 작성 하고난 후 완성된 프로그램의 시간 복잡도를

측정하여 직접 기술 해볼 수 있도록 한다. 알고리즘은 교재의 것을 사용하되 교재에 수록되어있는 소스코드는 참고치

아니하고 작성하도록 한다.

2. 문제분석

- 마방진이란 무엇인가

▷ n X n 형식의 정방형의 공간에 가로, 세로, 대각선 각각의 원소의 합이 모두 같은 형식의 행렬.(아래예시)

	열	0	1	2
행
0		6	1	8
1		7	5	3
2		2	9	4

- 마방진의 구현방법

▷ 정수형 변수 n을 입력받은 후에 n² 만큼의 배열을 생성한다.

▷ 생성된 배열의 (0, (n-1)/2)부터 1을 입력하고, 마방진 알고리즘에 의해 프로그램을 구동.

▷ 해당 배열위치에 입력이 끝나면 각 행과열의 값을 1씩 감소한다.

▷ 감소된 행과열의 값이 -1 이라면 입력받은 n만큼 증가시킨다.

- 시간복잡도의 계산

▷ 프로그램이 작동할 때 알고리즘을 구성하는 명령어들의 실행횟수와 소요시간의 곱.

▷ 소요시간은 하드웨어나 개발언어에 따라 달라지므로 명령어의 실행횟수만 계산한다.

▷ 시간복잡도 계산시 사용자의 입력은 첫 번째 입력에서 성공한다고 가정한다.

▷ 실질적인 작업이 수행되는 실행부의 각 함수별로 복잡도를 계산하도록 한다.

▷ 함수별로 계산된 복잡도를 합산하여 전체 복잡도를 구한 후 Big OH 정리에 입각하여 기술한다.

3. 결 과

- 소스부분

▷ 메인부

#include "MagicSquare.h"

int main()

{

MagicSquare MS; // 마방진객체선언

MS.InputSize(); // 마방진의크기입력호출

MS.MakeArray(); // 입력된크기만큼배열생성호출

MS.AccessMS(); // 마방진연산호출

MS.PrintMS();// 완성된마방진출력호출

return 0;

}

▷ 헤더부

#ifndef _MAGIC_H_ // 재정의오류방지

#define _MAGIC_H_

class MagicSquare{

public:

MagicSquare(); // 생성자

void InputSize(); // 마방진크기입력함수

void MakeArray(); // 마방진저장배열설정함수

void AccessMS(); // 마방진생성함수

void PrintMS(); // 마방진출력함수

~MagicSquare(); // 소멸자

private:

int size; // 마방진의크기저장변수

int h, w; // 마방진행렬의행(height:h) 과열(width:w)

int **MSArray; // 마방진2차원배열동적할당

};

#endif

▷ 실행부

#include <iostream>

using std::cout;

using std::cin;

using std::endl;

#include <iomanip>

using std::setw;

#include "MagicSquare.h"

MagicSquare::MagicSquare(){ // 생성자

h = 0; // 행과열의값0으로초기화

w = 0;

}

void MagicSquare::InputSize(){ // 마방진의크기를입력받는다

while(true){ // 알맞은입력이올때까지입력대기

cout << "Input MagicSquare Size.(1-51 AND ODD Num)" << endl;

cout << "Input : "

cin >> size; // 마방진의크기입력

If(size%2 == 1 && size <= 51 && size >0){ // 1-51 사이의홀수만입력받음

cout << "You input correct number" << endl;

break // 제대로된입력값이면while문빠져나감

}

else if(cin.fail()){ // 문자열이나특수기호이면

cin.clear(); // 입력초기화

cin.ignore(512, '\n'); // 입력값삭제

cout << endl << "Wrong input.(Only 1-51 ODD Num)" << endl; // 메시지출력후재입력대기

}

else{ // 그외다른경우(짝수입력일때)

cout << endl << "Wrong input.(Only 1-51 ODD Num)" << endl; // 메시지출력후재입력대기

}

}

w = (size-1)/2; // 마방진에서의열의시작지점을지정

}

void MagicSquare::MakeArray(){ // 마방진2차원배열을동적할당한다

MSArray = new int *[size]; // 행을동적할당

for(int i=0; i<size; i++){ // 동적할당된행을돌아가면서

MSArray[i]= new int [size]; // 열을동적할당

}

for(int j=0; j<size; j++){ // 생성된배열값을0으로초기화

for(int k=0; k<size; k++){

MSArray[j][k] =0;

}

}

}

void MagicSquare::AccessMS(){ // 마방진을계산하고배열에저장한다

int i=0; // 반복문변수초기화

do{ // do-while 문시작

if(h == -1 && w == -1){ // 행과열이모두마이너스값이면

h = 1; // 행을1로수정

w = 0; // 열을0으로수정

}

else if(h == -1){ // 행이마이너스값이면

h+=size; // 행의마지막으로이동

}

else if(w == -1){ // 열이마이너스면

w+=size; // 열의마지막으로이동

}

else if(MSArray[h][w] != 0){ // 배열에이미마방진값이저장되어있다면

h += 2; // 행과열을재설정

w += 1;

}

if(MSArray[h][w] == 0){ // 마방진값이비어있는배열에만

MSArray[h][w] = i+1; // 값을입력

}

h--; // 행 감소

w--; // 열 감소

i++; // 반복문 증가

}while(i < (size*size)); // 마방진배열이모두찰때까지계속한다

}

void MagicSquare::PrintMS(){ // 저장된마방진을출력한다

cout << endl << "Now Print Magic Square" << endl << endl; // 마방진출력알림

for(int i=0; i<size; i++){ // 마방진출력

for(int j=0; j<size; j++){

cout << setw(3) << MSArray[i][j] << setw(8); // 마방진정렬하여출력

}

cout << endl; // 한행이 끝나면 줄바꿈

}

cout << endl << "Print magic Square is done" << endl; // 출력종료알림

}

MagicSquare::~MagicSquare(){ // 소멸자

for(int i=0; i<size; i++){ // 동적할당된마방진배열을반대로해제한다

delete []MSArray[i]; // 열의 동적할당해제

}

delete []MSArray; // 행의 동적할당해제

}