In University ☆ In Bucket Place ☆ Hobby & Study Room ☆

홀수 마방진은 마방진을 만드는 것중에서 가장 간단한 형태이다. 위에서 파란원이 만들려고 하는 마방진이다.(크기 3짜리 3*3 마방진을 만든다.) 다음과 같은 과정을 따르며 마방진을 완성해간다. ⓐ 시작숫자 1을 첫번째 행, 가운데 열에 넣는다. ⓑ 숫자가 (3의 배수 + 1)일 경우는 바로 밑에 숫자를 적어준다. > 위의 경우 4또는 7이 이에 해당한다. ⓒ 다음 숫자를 오른쪽 대각선위에 적는다. > 만약, 숫자가 마방진크기를 벗어나게 되면 그 행 또는 열의 가장자리로 보낸다. (위의 경우 2의 경우 행에서 크기가 벗어나므로 맨 밑행으로 숫자를 이동시킨다.) (위의 경우 3의 경우 열이 크기에서 벗어나므로 맨 오른쪽행으로 숫자를 이동시킨다.) ⓓ 숫자가 size*size가 될때까지 숫자를 더해주면서 ⓒ의..

방학이 사작된지 1주... 그리고 다가오는 새해~ 일단... 이 글을 보시는 분 모두 새해복 많이 받으세요...(__)꾸벅~ 먼가 방학이 됬는데... 놀고만 있는 것 같아서... 글을 끄적이게 됬습니다... (역시 모든 것의 시작은 이 블러그 갔네요...) 음... 방학때의 계획은 다음과 같이 짧습니다. 공부한다. 잔다. 먹는다. 논다. =_=;; "세부적으로 어떻게 할건데~!!"라고들 하시겠죠...? 일단 "공부한다."부터 알아보면요... ⓐ 안드로이드를 한번 맘먹고 한달안에 2권정도 볼려고 합니다... - 만들고 싶은 프로그램이 있는데... 방학안에 좀 만들어 보고 싶어서 하는 일입니다~ ⓑ 영어 및 일본어 공부... - 영어 공부는 지난 여름방학때 보았던 토익 책을 한번더 보려고 합니다... - 일..

calc_lex.l /* DEFINITION SECTION */ %{ #include "calc_yacc.h" #include extern double yylval; %} WHITE_SPACE [ \t]+ END_MARKER "$" DOUBLE_VAL ([0-9]+|([0-9]*\.[0-9]+)([eE][-+]?[0-9]+)?) %% /* RULE SECTION */ {DOUBLE_VAL} { yylval = atof(yytext); return NUMBER; } "+"{ return PLUS; } "-"{ return MINUS; } "*"{ return MULT; } "/"{ return DIV; } "abs"{ return ABS; } "sqrt"{ return SQRT; } "log"{ retur..

* 특징 - 되추적 기법과 같이 상태공간트리를 구축하여 문제를 해경한다. - 최적의 해를 구하는 문제에 적용할 수 있다.(되추적기법은 특정해를 구하는 문제에 적용) - 최적의 해를 구하기 위해서는 모든 해를 다 고려해 보아야 하므로 트리의 노드를 순회하는 방법에 구애받지 않는다. * 분기한정 알고리즘의 원리 - 각 노드를 검색할 때마다 그 노드가 유망한지의 여부를 결정하기 위해 한계치(bound)를 계산한다. - 그 한계치는 그 노드로부터 가지를 뻗어 나가서(Branch)를 얻을 수 있는 해답의 한계치를 나타낸다. - 만약 그 한계치가 지금까지 찾은 최적의 해답치 보다 좋지 않은 경우는 더 이상 가지를 뻗어 나가서 검색을 계속 할 필요가 없으므로 그 노드는 유망하지 않다고 할 수 있다. * 최적화 문제를..

import java.util.Scanner; public class hamiltonian { private boolean W[][]; private int nodeCount; private int vindex[]; hamiltonian(int n){ nodeCount = n; W = new boolean[nodeCount][nodeCount]; vindex = new int[nodeCount]; vindex[0] = 0; Scanner sc = new Scanner(System.in); char isTrue; for ( int i = 1 ; i

import java.util.*; public class mColoring { private int n; private int m; private int W[][]; private int vcolor[]; mColoring(int count, int colornumber){ int i, j; // for loop char isTrue; Scanner sc = new Scanner(System.in); n = count; m = colornumber; W = new int[n][n]; vcolor = new int[n]; vcolor[0] = 1; for ( i = 1 ; i

* 해밀토니안 회로 - 연결된 비방향성 그래프에서 어떤 한 정점에서 출발하여 그래프사으이 각 정점을 정확히 한번씩만 경유하여 다시 출발 정점으로 돌아오는 경로 ex) * 해밀토니안 회로문제 - 연결된 비방향성 그래프에서 해밀토니안 회로를 찾아라 - 상태공간트리 > 시작 정점을 트리의 수준(level) 0에 놓는다. > 수준 1에 시작 정점이 아닌 정점들을 놓는다. > 다른 수준에도 같은 방식으로 시작 정점이 아닌 정점들을 놓는다. > 마지막 수준에는 시작 정점을 놓는다. - 되추적 방법을 적용하기 위해서 다음 사항을 고려해야한다. > 경로상의 i번째 정점은 그 경로상의 (i-1)번째 정점과 반드시 인접해야한다.(인접하지 않으면 패스) > (n-1)번째 정점은 반드시 시작 정점과 인접해야한다.(마지막(n번..

* m - 색칠하기 문제 비방향 그래프에서 서로 인접한 종점들이 같은 색을 갖지 않도록 하면서 최대 m개의 다른 색으로 칠하는 모든 방법을 찾아라. * 평면그래프(Planar graph) - 평면 상에서 연결선들이 서로 교차하지 않는 그래프 옆 그래프는 연결선이 서로 교차하지 않으므로 평면 그래프라고 할 수 있다. 위 그래프에서 두개의 연결선 (v1,v5)와 (v2,v3)를 추가하면 연결 선중 일부는 교차하게 되고, 이에 따라 평면 그래프가 될 수 없다. * 지도와 평면 그래프 - 지도에서 각 지역을 그래프의 정점으로 하고, 한 지역이 어떤 다른 지역과 인접해 있으면 그 지역들을 나타내는 정점들 사이에 연결선을 그으면, 모든 지도는 그에 상응하는 평면 그래프로 표시할 수 있다. * m - 색칠하기 되추적..

* 상태 공간 트리(State Space Tree) - 미로 찾기에서 입구에서 출구까지 가는 경로를 찾기 위해서 선택할 수 있는 모든 경로를 트리로 만들 수 있다. 막다른 곳이나 출구가 종단 노드(leaf node)에 위치하게 된다. 이 트리가 상태공간 트리이다. - 상태 공간 트리를 깊이 우선 검색을 하여 해답 후보들 중에서 해답을 찾을 수 있다. > 상태 공간 트리를 깊이 우선 검색을 하여 해답 후보들을 모두 순회하면서 해답을 찾을 수 있다. 그러나 이방법은 해답이 될 가능성이 전혀 없는 노드의 후손 노드들도 모두 검색해야 하므로 비효율 적이다. * 되추적 기술 - 노드의 유망성 > 전혀 해답이 나올 가능성이 없는 노드는 유망하지 않다고 판단을 한다.(non-promising) 이와 반대로 가능성이 ..

* 되추적이란? - 미로에서 출구를 찾다보면 막다른 곳에 도달 할 수 있다. 이때 마지막 분기점으로 되돌아 가서 다른 길로 갈 수 있다. 이처럼 되추적은, 어떤 집합에서 특정 기준을 만족하면서 그 집합에 속한 대상의 순서를 손택하는 문제를 푸는데 사용한다. 되추적의 기본은 상태 공간 트리로 깊이 우선 검색과 밀접한 관련이 있다. 일단 깊이 우선 검색을 먼저 알아보도록 하자. * 깊이우선 검색 - 한 그래프의 정점들을 방문하는 하나의 방법 - 슈도코드 void DFSEARCH(v){ 정점 v를 "방문함"으로 표시한다. v에 인접한 모든 정점 w에 대해서 다음을 수행한다. > w가 방문하지 않은 상태면 DFSEARCH(w)를 수행 > w가 이미 방문했던 상태면 수행을 종료한다. } // 처음 모든 정점들은 ..