*기* 스토어

*기*

개인인증

팔로워0 팔로우

소개

등록된 소개글이 없습니다.

전문분야 등록된 전문분야가 없습니다.

판매자 정보

학교정보

입력된 정보가 없습니다.

직장정보

입력된 정보가 없습니다.

자격증

입력된 정보가 없습니다.

판매지수

판매중 자료수

12개
전체 판매량

39개
최근 3개월 판매량

0개
자료후기 점수

평균A
자료문의 응답률

-

전체자료 12개

[알고리즘]손전등퍼즐 백트래킹소스

알고리즘백트래킹손전등퍼즐Assignment #3Class Date : ~2008.06.04.Submission Date : 2008.06.05.# of pages : 9pages except for coverpage■ 다음 퍼즐을 backtracking으로 푸는 컴퓨터 프로그램을 구현하시오. 다음의 내용을 제시하시오.1. State space tree(골격만 개략적으로 나타내시오)2. 상세 알고리즘3. 프로그램 소스4. 실행결과네 사람이 다리를 건너는 데 각각 1, 2, 5, 10분이 걸립니다. 밤중이고 손전등이 하나뿐이라 기껏해야 두 사람이 같이 다리를 건널 수 있습니다. 다리의 한쪽에 있던 네 사람이 모두 건너가는데 최소의 시간으로 건너가려 합니다. 어떻게 건너가야 할까요? 그리고 그 최소 시간은 얼마일까요?[State space tree][1]시작좋은bound값마디로[1,2]AB=2분[1,3]AC=5분[1,4]AD=10분ㆍㆍㆍㆍㆍ유망하면 자식마디방문A=1분B=2분C=5분ㆍㆍㆍㆍ[1,2,3] [1,2,4] [1,2,5]ㆍ ㆍ ㆍ ㆍㆍ ㆍ ㆍ ㆍㆍ ㆍ ㆍ ㆍ[상세알고리즘]A = 1분B = 2분C = 5분D = 10분이라고 정하고, 조건은- 두사람만 건널수 있다.- 손전등은 한사람만 가지고 있을수 있다.A B C D ?C D ? A BA와B 가 도착지로 건너옴2분소요A C D BA가 다시 건너감1분소요A ? B C DC와D가 도착지로 건너옴10분소요A B C DB가 다시 건너감2분소요? A B C DA와B가 도착지로 건너옴2분소요총 17분의 시간이 소요된다.이번 문제에 대해선 분기한정법을 이용하여 구현해본다.분기한정법이란 되추적 알고리즘을 개선 한것이다. 0-1배낭 채우기 문제와 같은 경우 동적계획 알고리즘이나 되추적 알고리즘으로 풀수 있는데 두가지 모두 최악의 경우 지수시간 이므로, 어떤 경우 문제를 푸는데 수년이 걸리게 되므로 매우 비효율 적이다. 분기한정법은 상태공간트리를 사용한다는점에서 되추적 알고리즘과 매우 비슷하다. 하지만 분기한정법은 되추적 알고리즘과는 다르게 트리 횡단 방법에 구애 받지 않고, 최적화 문제를 푸는데만 쓰인다. 분기한정 알고리즘은 어떤 마디가 유망한지를 결정하기 위해서 그 마디에서 한계값을 계산한다. 이 한계값은 그 마디 아래로 확장하여 구할 수 있는 해답값의 한계(bound)를 나타낸다. 그 한계값이 그때까지 찾은 최고 해답보다 더 좋지않으면 그마디는 유망하지 않다. 그렇지 않으면 유망하다. 되추적 알고리즘과 마찬가지로 분기한정 알고리즘 또한 최악의 경우 보통 지수시간이지만 많은 큰 사례에 대해서는 매우 효율적일수 있다. 0-1배낭채우기 문제에서 분기한정 알고리즘은 유망한 마디들의 한계값들을 비교하여, 그 중에서 가장 좋은 한계값을 가진 마디의 자식마디를 방문한다. 이렇게 하면 미리 정한 순서대로 마디를 기계적으로 방문하는것보다 종종 더 빨리 최적 해에 도달할수 있다. 이 방법을 분기한정 가지치기 최우선검색 이라고 한다. 즉, 정리하자면 분기한정 알고리즘은 우선 가지를 먼저 펼친후 (branch), 각 가지의 한계값을 구한 다음(bound), 그 값을 비교하여 유망한지를 판단하는 알고리즘이다.분기한정 가지치기 최고우선검색을 하면 한계값은 잎마디가 아닌 마디에 기롣하는 반면, 일주여행경로의 길이는 잎마디에 기록한다. 트리를 구축하는 절차를 살펴보면 뿌리마디에는 해답후보가 없기 때문에 최고 해답의 값은 무한대로 초기화한다. 알고리즘에 의하면 상태공간 트리에서 잎마디 이후로는 확장하지 않기 때문에 잎마디에 대한 한계값은 계산하지 않는다. 마디를 참조하면 그 마디에 기록되어 있는 부분 일주여행경로를 참조하게 된다.외판원문제를 구현할때도 분기한정법을 사용하는경우가 있기에 외판원문제 알고리즘을 수정해서 다리건너기 알고리즘으로 변형해보았으나 생각대로 되지않았지만 분기한정법을 이해하기는 충분했다.[실행소스1]#include #include #include #include using namespace std;#define NMAX 6enum Boolean { FALSE, TRUE };class Graph {private:string _PointName[NMAX];int _length[NMAX][NMAX]; //인접 행렬과의 비용int _dist[NMAX]; //시작 정점에서의 최단 경로Boolean _s[NMAX]; //최단 경로를 찾으면 _s[?]는 TRUE//갱신된 정점의 비용 출력void DisplayValues( int u ) {char before;cout < right;for( int i = 0; i < NMAX; i++ ) {before = ' ';if( i == u )before = '[';else if( i-1 == u )before = ']';cout < before < setw(4);if( _dist[i] == INT_MAX )cout < "＋∞";elsecout < _dist[i];}if ( u == NMAX-1 )cout < ']';cout < endl;}public:Graph() {_PointName[0] = "AB = 2min";_PointName[1] = "Aback = 1min";_PointName[2] = "CD = 10min";_PointName[3] = "Bback = 2min";_PointName[4] = "AB = 2min";_PointName[5] = "complete";for( int i = 0; i < NMAX; i++ ) {for ( int j = 0; j < NMAX; j++ )_length[i][j] = INT_MAX;_length[i][j] = 0;}_length[0][1] = 2;_length[0][2] = 12;_length[1][0] = 15;_length[1][2] = 1;_length[1][3] = 11;_length[1][4] = 13;_length[2][0] = 14;_length[2][1] = 16;_length[4][1] = 6;_length[4][5] = 2;}//_dist[j](0

프로그램소스| 2008.12.01| 11페이지| 3,000원| 조회(399)

백트래킹

미리보기

닫기
[알고리즘]강건너기퍼즐소스

알고리즘강건너기 퍼즐 소스Assignment #2Class Date : ~2008.05.28.Submission Date : 2008.05.29.# of pages : 4page except for coverpage■ 다음 퍼즐을 backtracking으로 푸는 컴퓨터 프로그램을 구현하시오. 다음의 내용을 제시하시오.1. State space tree(골격만 개략적으로 나타내시오)2. 상세 알고리즘3. 프로그램 소스4. 실행결과아빠, 엄마, 아들 둘, 딸 둘, 하인, 그리고 개가 다 한척의 배를 써서 강을 건너야 합니다. 아빠, 엄마, 하인은 배를 저을 줄 알지만, 이 배는 두사람까지만 탈 수 있습니다. 그런데 엄마가 없으면 아빠가 딸을 잡아먹고, 아빠가 없으면 아들을 잡아먹고, 하인이 없으면 개가 사람을 잡아먹습니다. 완전 엽기다! 어떻게 강을 건너야 할까요?▲ 상태공간트리①아빠 ②엄마 ③아들1 ④아들2 ⑤딸1 ⑥딸2 ⑦하인 ⑧개start -> ① →→→→...⑭....① →→→→...⑮... , ① →→→→...⑩...①→②→→→→... ⑮...유망하지 않다면 되추적을 통해 처음루트 노드로 올라간다. 또 계속 탐색을 하여 유망할때까지 탐색을 계속한다.▲ 알고리즘조건 1) 개는 하인이 없으면 사람들을 잡아 먹는다.조건 2) 아빠는 엄마가 없으면 여자아이를 잡아 먹는다.조건 3) 엄마는 아빠가 없으면 남자아이를 잡아 먹는다.조건 4) 운전을 할 수 있는 자는 하인, 아빠, 엄마 뿐이다.조건 5) 한 번에 이동 가능한 인원은 2명 뿐이다.→ 이동순서1. 하인, 개 를 이동시킨다. (엄마, 아빠, 아들12, 딸12 ----- 하인, 개)2. 하인은 다시 돌아온다. (엄마, 아빠, 아들12, 딸12, 하인 ----- 개)3. 하인, 아들1 을 이동시킨다 (엄마, 아빠, 아들2, 딸12 ----- 하인, 개, 아들1)4. 하인, 개는 다시 돌아온다. (엄마, 아빠, 아들2, 딸12, 하인, 개 ----- 아들1)5. 아빠, 아들2를 이동시킨다. (엄마, 딸12, 하인, 개 ----- 아빠, 아들12)6. 아빠는 다시 돌아온다. (엄마, 아빠, 딸12, 하인, 개 ----- 아들12)7. 엄마, 아빠를 이동 시킨다. (딸12, 하인, 개 ----- 엄마, 아빠, 아들12)8. 엄마는 다시 돌아온다. (엄마, 딸12, 하인, 개 ---- 아빠, 아들12)9. 하인, 개를 이동 시킨다. (엄마, 딸12 ----- 아빠, 아들12, 하인, 개)10. 아빠는 다시 돌아온다. (아빠, 엄마, 딸12 ----- 아들12, 하인, 개)11. 엄마, 아빠를 이동시킨다. (딸12 ----- 엄마, 아빠, 아들12, 하인, 개)12. 엄마는 다시 돌아온다. (엄마, 딸12 ----- 아빠, 아들12, 하인, 개)13. 엄마, 딸1을 이동시킨다. (딸2 ----- 아빠, 엄마, 딸1, 아들12, 하인, 개)14. 하인, 개는 다시 돌아온다. (하인, 개, 딸2 ----- 아빠, 엄마, 딸1, 아들12, 하인, 개)15. 하인, 딸2를 이동시킨다. (개, ----- 아빠, 엄마, 딸12, 아들12, 하인)16. 하인은 다시 돌아온다. (하인, 개 ----- 아빠, 엄마, 딸12, 아들12)17. 하인, 개를 이동시킨다. ( ----- 아빠, 엄마, 딸12, 아들12, 하인, 개)▲ 프로그램 소스※ 우선 백트래킹이란 가능성이 있는 해를 전부 탐색한다라고 말할수 있습니다. 일반적으로 백트래킹은 N번의 선택을 반복하는 구조를 가지고 있습니다. 재귀호출을 사용해서 모든 노드를 들린다는 뜻입니다. 즉, 모든 가능성을 탐색하여 모든 솔루션을 찾아내는 일종의 탐색방법입니다. 원래는 이 백트래킹을 이용하여 소스를 짜야하는데 기본적인 틀만 알고 구현을 못했습니다. 기본 틀은 이렇습니다.#include #define FALSE 0#define TRUE 1#define MAXCANDIDATES 1000bool finished = FALSE; //모든 풀이를 찾았는 지의 여부struct data{int num; //간단한 내용만 넣음};data input[1000];/*완전한 풀이가 만들어 졌을 때 그 풀이를 출력하거나개수를 세거나 하는 식으로 답으로 내놓을 수 있는 것을 하는 함수때에 따라서는 input 배열의 주소등을 넘겨 줄 필요가 없을 때에는 고쳐서 사용한다.*/void process_solution(int a[],int k,data input);//배열의 a 번째 부터 k 번째 가지 의 원소가 주어진 문제의 풀이가 될 수 있는 지 판단하는 함수bool is_solution(int a[],int k,data input);/*첫번째 부터 k-1 번째 위치의 내용이 모두 주어졌을 때 k번째위치가 될 수 있는 모든 후보가 들어가는 배열 c 를 채워주는루틴 이 배열을 통해 리턴되는 후보의 개수는 nCandidates 로 지정한다.여기에서도 input 은 추가 정보를 넘겨주는 용도로 쓰이는 데 보통 원하는 풀이의 크기를 이 값을 통해 전달한다.*/int construct_candidates(int a[], int k,data input,int c[],int *nCandidates);void backTrack(int a[], int k, data input){int c[MAXCANDIDATES]; //다음 위치가 될 수 있는 후보 위치 - 간선 들어오는 것들int nCandidates; //다음 위치가 될 수 있는 후보 개수int i; //카운터if(is_solution(a,k,input))process_solution(a,k,input);else{k++;construct_candidates(a, k, input,c,&nCandidates);for(i=0;idata = (char*)malloc(1*strlen(buff)+1);temp->next = NULL; // temp의 다음은 NULL을 가리킨다if(*curr != NULL){temp->next = *curr;}*curr = temp;strcpy(temp->data, buff);}void pop(struct node** temp) //배에서 내리는 과정을 pop으로 구현{struct node* dummy;dummy = *temp;puts(dummy->data);*temp = dummy->next;free(dummy->data);free(dummy); //연결 리스트에서 노드를 삭제}void main(void){int num;char buff[1024];struct node* curr = NULL;int count=0;printf("------------------------ ------------------------n");printf(": : ㅁ_______ : :n");printf(": F M s ss d dd H dg : [_____/ : :n");

프로그램소스| 2008.12.01| 7페이지| 3,000원| 조회(1,000)

강건너기

미리보기

닫기
[자바] 바코드 프로그램

JAVA바코드 프로그램△ 서론o 사용언어 : JAVAo 사용프로그램 : eclips SDK 3.3 jdk update2 ver.o OS환경 : Windows XP Professionnel△ 본론■ P8.10우편물을 보다 빨리 분류하기 위해 미우편서비스는 우편번호를 나타내는 바코드를 사용하여 양이 큰 우편물들을 발송하도록 독려하고있다. 바코드의 각 사이드에는 가장 긴 막대가 있다. 바코드화된 우편번호 뒤에는 체크번호가 붙게 되는데, 체크번호는 다음과 같이 계산된다. 모든 자리수를 더한 합을 10의 배수로 만드는 체크번호를 선택한다. 예를 들어 우폄번호 95014의 숫자들 합은 19일때, 합을 10의 배수인 20으로 만들려면 체크번호는 1이 되어야 한다.742*************1*************01**************************0011000우편번호의 각 숫자는 다음표에서 기초로 바코드화된다. 이는 2개의 전체 막대와 3개의 절반 막대의 조합으로 하나의 우편번호 숫자를 쉽게 계산할수 있다. 우편번호를 묻고 이를 바코드로 출력하는 프로그램을 작성하라. 절반 막대는 :으로 전체막대는 |으로 나타내라. 예를 들어 95014는 다음과 같이 된다.||:|:::|:|:||::::::||:|::|:::|||작성한 프로그램은 역변환도 가능해야 한다. 막대들을 해당 우편번호로 바꿀수 있어야 한다. 숫자하고 맞지 않거나, 입력 형식이 틀린 경우에는 해당 오류를 출력해야 한다.▲ 소스public class MyBarcode {private String num; // 바코드 넘버 매개변수private String valStick; // 바코드 막대 멤버변수private String valNum = ""; // 바코드 넘버 멤버변수public MyBarcode() { //생성자}public MyBarcode(String aNum) {num = aNum;}public String getStick() { // 바코드 막대를 반환하는 메소드int numTemp = 0;int valtemp = 0;valStick = "|"; //울타리 바코드 막대for (int i = 0; i < 5; i++) { // 바코드 넘버 검사해서 바코드 막대로 변환String temp = num.substring(i, i + 1);numTemp += Integer.parseInt(num.substring(i, i + 1));if (temp.equals("0")) {valStick = valStick + "||:::";} else if (temp.equals("1")) {valStick = valStick + ":::||";} else if (temp.equals("2")) {valStick = valStick + "::|:|";} else if (temp.equals("3")) {valStick = valStick + "::||:";} else if (temp.equals("4")) {valStick = valStick + ":|::|";} else if (temp.equals("5")) {valStick = valStick + ":|:|:";} else if (temp.equals("6")) {valStick = valStick + ":||::";} else if (temp.equals("7")) {valStick = valStick + "|:::|";} else if (temp.equals("8")) {valStick = valStick + "|::|:";} else if (temp.equals("9")) {valStick = valStick + "|:|::";}}valtemp = 10 - ((numTemp) % 10); // 바코트 체크넘버 확인 (10의배수 - 넘버합)//체크넘버를 막대로 변환if (valtemp == 0) {valStick = valStick + "||:::";} else if (valtemp == 1) {valStick = valStick + ":::||";} else if (valtemp == 2) {valStick = valStick + "::|:|";} else if (valtemp == 3) {valStick = valStick + "::||:";} else if (valtemp == 4) {valStick = valStick + ":|::|";} else if (valtemp == 5) {valStick = valStick + ":|:|:";} else if (valtemp == 6) {valStick = valStick + ":||::";} else if (valtemp == 7) {valStick = valStick + "|:::|";} else if (valtemp == 8) {valStick = valStick + "|::|:";} else if (valtemp == 9) {valStick = valStick + "|:|::";}valStick = valStick + "|"; //울타리 막대return valStick; // 바코드 막대 반환}// 바코드 막대를 받아와 다시 바코드 넘버로 반환public String getNum() {// 5자리가 하나의 넘버이기 때문에 5자리씩 뭉쳐서 검사for (int i = 1; i < 26; i += 5) {String temp2 = valStick.substring(i, i + 5);if (temp2.equals("||:::")) {valNum = valNum + "0";} else if (temp2.equals(":::||")) {valNum = valNum + "1";} else if (temp2.equals("::|:|")) {valNum = valNum + "2";} else if (temp2.equals("::||:")) {valNum = valNum + "3";} else if (temp2.equals(":|::|")) {valNum = valNum + "4";} else if (temp2.equals(":|:|:")) {valNum = valNum + "5";} else if (temp2.equals(":||::")) {valNum = valNum + "6";} else if (temp2.equals("|:::|")) {valNum = valNum + "7";} else if (temp2.equals("|::|:")) {valNum = valNum + "8";} else if (temp2.equals("|:|::")) {valNum = valNum + "9";}}// 체크바코드 막대 검사해서 넘버로 변환String temp3 = valStick.substring(26, 31);String checkNum = "";if (temp3.equals("||:::")) {checkNum = "0";} else if (temp3.equals(":::||")) {checkNum = "1";} else if (temp3.equals("::|:|")) {checkNum = "2";} else if (temp3.equals("::||:")) {checkNum = "3";} else if (temp3.equals(":|::|")) {checkNum = "4";} else if (temp3.equals(":|:|:")) {checkNum = "5";} else if (temp3.equals(":||::")) {checkNum = "6";} else if (temp3.equals("|:::|")) {checkNum = "7";} else if (temp3.equals("|::|:")) {checkNum = "8";} else if (temp3.equals("|:|::")) {checkNum = "9";}System.out.println(checkNum); //체크넘버 출력return valNum; //바코드 넘버 반환}}import java.util.Scanner;public class MyBarcodeTest {public static void main(String[] agrs){Scanner in = new Scanner(System.in);System.out.println("Enter number 5 index:");String n =in.next();MyBarcode code = new MyBarcode(n); // 바코드 넘버 입력한 객체 생성System.out.println("print Barcode:");System.out.println(code.getStick()); // 바코드 막대메소드 호출System.out.println("print check number & numberCode:");System.out.println(code.getNum()); //바코드 넘버 메소드 호출}}▲ 출력결과△결론→

프로그램소스| 2008.11.25| 7페이지| 3,000원| 조회(1,165)

바코드

미리보기

닫기
[IPTV]발표 자료

IPTV의 고속성장3년2년1년국가별 50만명 달성 기간 비교홍콩, 프랑스미국한국정의인터넷 IPTV의 차이점EASY convenienceIPTV가 바꿀 Game의 룰IPTV IPTV 서비스단점인터넷이 안되면 무용지물실시간,고화질 프로그램의 고르지 못한 화면TV 인터넷 동시사용으로 인한 속도 저하인터넷 사용의사 없어도 무조건 신청카우치 포테이토 증후군IPTV의 장점과 단점장점사용자 맞춤형인터넷이 제공하는 다양한 콘텐츠 및 부가서비스주요 IPTV 사업자 및 보안방안→ 콘텐츠 확보가 성공의 관건IPTV = 핫포테이토Sooooooo hot~~!!A지금부터 파급적 효과를 불러올 IPTV에 대해 설명하겠습니다. IPTV란 초고속 인터넷을 이용하여 정보 서비스, 동영상 콘텐츠 및 방송 등ㅇㄹ 텔레비전 수상기로 제공하는 서비스를 말합니다. 인테넷과 텔레비전의 융합이라고 볼수있습니다. 기존의 인터넷TV와 다른점은 이와 같이 컴퓨터 모니터 대신 텔레비전 수상기를 이용하고, 마우스 대신 리모콘을 사용한다는 점에 있습니다.

공학/기술| 2008.11.21| 15페이지| 3,000원| 조회(330)

IPTV, 초고속 인터넷

미리보기

닫기
[자바] 바코드 프로그램

자바 바코드 프로그램import java.util.Scanner;public class happyBarcode {private String code;private String barcode;public static final String NUM0 = "";public static final String NUM1 = "";public static final String NUM2 = "";public static final String NUM3 = "";public static final String NUM4 = "";public static final String NUM5 = "";public static final String NUM6 = "";public static final String NUM7 = "";public static final String NUM8 = "";public static final String NUM9 = "";public happyBarcode(String str) {code = str;}public String getCode() {int sum = 0;barcode = "";int digit;for (int i = 0; i < code.length(); i++) {digit = Integer.parseInt(code.substring(i, i + 1));sum += digit;barcode += digitCode(digit);}sum = 10 - sum % 10;barcode += digitCode(sum);return translate();}private String digitCode(int n) {String temp = "";switch (n) {case 0:temp = NUM0;break;case 1:temp = NUM1;break;case 2:temp = NUM2;break;case 3:temp = NUM3;break;case 4:temp = NUM4;break;case 5:temp = NUM5;break;case 6:temp = NUM6;break;case 7:temp = NUM7;break;case 8:temp = NUM8;break;case 9:temp = NUM9;break;}return temp;}private String translate(){String temp = "|";for(int i = 0; i

프로그램소스| 2008.11.19| 6페이지| 2,000원| 조회(1,843)

바코드

미리보기

닫기