9 Log

/*16진수 를 10진수로 변환하는 프로그렘*/ #include <stdio.h> #include <math.h> #include <windows.h> int main(){         char c[8];     //4byte int변수의 최대 표현 범위는 2^31-1이므로 8자리 (16^8-1) 이상으로 필요하지 않다.     int i,sum=0,d;     // 최대 8자리의 16진수를 입력하되 만약 8자리의 16진수는 7까지만 입력가능.         printf("자릿수를 입력(최대 8 자리) : ");     scanf("%d",&d);         printf("%d자리 16진수 입력(최대 7FFFFFFF) : ",d);         scanf("%s",c);     for(i=0;i<d;i++){                      if('A'<=c[i]&&c[i]<='F')c[i]+=10-'A';                      else c[i]-='0';           ...

"데카르트 : 정신지도를 위한 규칙들" 에서 데카르트는 사람들이 학문을 탐구할때 지켜야할 규칙들에 대해서 자신의 생각을 정리해 놓았다. 규칙 1. 모든 학문의 연구의 목표는 대상들에 대한 견고하고 참된 인식을 얻는 것이다. 데카르트는 학적탐구는 기예처럼 한가지 일만 잘할수 있는 것이 아니라 모든 학문에는 보편성이 있어서 모든 학문은 그 대상의 차이에도 불구하고 한가지 보편적인 목표를 가진다는 주장을 한다. 바로 그 대상들에 대한 참된( 거짓되지 않은) 인식을 얻는 것이다. 규칙 2. 명확하고 의심할 수 없는 인식을 얻을수 있는 대상에 대해서만 탐구해야 한다. 여기서 데카르트는 지식을 명증적이고 확실한 인식이라 정의한다. 명확하지 않고 개연적인 추측(그럴 가능성만 있는 것들)으로만 얻어지는 인식들은 그 자체로도 믿을 수 없는 것이지만, 그러한 인식들로 부터 이끌어낸 인식들 또한 교묘한 추측에 불과하게 되는 것이다. 데카르트는 이 규칙을 지키는 학문은 기하학과 수학밖에 없다고 하였는데, 이는 후에 설명하게될 수학과 기하학의 직관성에 있다. 기하학과 수학처럼 상상력을 배제한 순수한 오성으로 부터 확실하게 증명되는 명제들을 연역하는 학문은 당연 명증적일 수밖에 없다. 자연을 인식하는 학문인 자연과학처럼 우리의 감각으로 대상을 인식하는 학문들은 그 자체가 경험에 의존하기 때문에 항상 오류일 가능성(불확실성)을 지니고 있다. 데카르트는 이러한 것들이 지식이 될수 없다고 한다. 규칙 3.명증적으로 직관되거나 확실하게 연역되는 것들에 대해서만 고찰하여야 한다. 여기서 데카르트는 직관과 연역을 자신의 방식대로 정의하는데, 오성은 직관과 연역으로 나뉘는데, 직관은 평행선은 만나지않는다 처럼 순수한 정신으로 단번에 명증적으로 참임을 알아내는 것을 말한다. 연역은 명증적인 인식(참되게 인식된 원리)들로부터 필연적으로 이끌어 낼수 있는 것을 말한다. 연역은 연속적으로 쓰이며...

Hanoi Tower라는 유명한 문제가 있다. 하노이 사원에는 3개의 막대가 있고 그중 하나의 막대에 3게의 크기가 서로 다른 n개의 둥근 원반이 끼워져 있다. 한 막대에 n개의 원반이 전부 꽃아져있고 각각의 원반은 자신보다 작은 원반 위에 있을 수 없다고 할때 n개의 원반을 다른 막대로 옮기는데 거리는 횟수를 구하는 문제다. #include <iostream> #include <windows.h> #include <vector> using namespace std; int n,c; vector<int> a[3]; void print_stacks_state(); void movestack(int h, bool isRight,int i){      //i에 있는h높이의 탑을 오른쪽 또는 왼쪽으로 옮기는 것을      //h-1높이의 탑을 옮기는 것으로 표현.      //i칸에서 윗부분 h-1높이의 탑을 다른 칸으로 옯긴후 밑의 h번째 블락을 원하는      //칸으로 옮긴후 그 칸으로 다른곳이 임시로 옮겨놓은h-1높이의 칸을 다시 옮긴다.      //n 높이의탑을 옮길때 (n-1높이의 탑을 옮길때 움직인 횟수)*2+1만큼 든다.      //따라서, 높이 1의 탑을 옮길 때 1의 횟수가 필요하므로 n일때는      //2^(n-1)+2^(n-2)+...4+2+1이다      //=등비가 2인 n개의 등비수열의 합=1*(2^n-1)/(2-1)=(2^n)-1           if(h==1){     ...

헤밀턴 회로는 모든 정점을 꼭 한번씩 거쳐서 출발점으로 다시 돌아오는 경로이다. 책에서 헤밀턴 회로를 구하는 문제를 보았다. 이분은 헤밀턴회로를 DFS로 구현하였는데 각각의 노드에 도달할 때마다 이전에 방문한 정점을 방문하지 않으려고 방문한 정점과 방금 지나온 간선을 검색대상에서 제외하였다. for( i =0;i<n;i++){ if(a[vertex][i]&&!check[i]){ a[vertex][i]=a[i][vertex]=0; check[i]=true; hamiltonCircuit(i); a[vertex][i]=a[i][vertex]=0; check[i]=false; } } 이런 식이다. 그러나. 헤밀턴 회로의 정의를 보면 지나간 간선을 다시 사용할 수 없다는 말은 없다. 다만 사용할수 없는 건 이러한 관계가 성립하기 때문이다. 각각의 정점을 꼭 한번씩 지난다->각각의 간선을 한번씩만 지난다.(물론 오일러의 경우처럼 모든 간선을 꼭 사용한다는 뜻은 아니다. 간선이 남을 수도 있다) 각각의 정점을 한번씩만 지나는 경우를 생각해 보자, 정점C에서 3번간선을 지나 정점 A에 도달 했다고 하자, 그렇다면 다신 3번 간선을 사용할 수 가 없다. 왜냐하면 이미 정점 C를 거쳐왔기 때문이다. 반대로 각각의 간선을 한번씩만 지나는 경우를 생각해보자. 정점 B에서 5번간선를 지나 정점 G에 도달한 상황에서 G에서 또다른 간선들을 이용하여 충분히B에 도달할 수 있다. 이러한 논리를 일반화 시키면 위의 관계가 성립함을 알 수 있다. 그리고 이러한 이유로 굳이 지나간 간선을 검색에서 제외할 이유가 없다. 어짜피 지나온 정점들을 방문하지 않는다는 조건은 지나온 간선들을 다시 방문하지 않는다는 조건을 포함하고 있다. 따라서 나는 다음과 같이 사용하는게 더 합리적이라고 본다. for( i =0;i<n;i++){ if(a[vertex][i]&...

/*DFS를 이용해 하나의 헤밀턴 회로를 구하는 프로그렘 입력 ; 첫줄엔 정점의 갯수와 간선의 갯수. 한줄은 한게의 간선에 연결된 한쪽 정점과 다른쪽 정점을 나타낸다 */ #include <iostream> #include <windows.h> using namespace std; bool a[100][100],check[100]; int path[100],c; int n,m; bool hamilton(int vertex){      path[c]=vertex;      int i;                if(c==n-1&&a[vertex][path[0]]){                 for(i=0;i<n;i++)cout<<path[i]+1<<" ";                 cout<<path[0]+1<<endl;                 return true;      }           c++;      check[vertex]=true;           for(i=0...

/*     4   /   \ 5----3 | \   /| |  \ / | |  /\  | | /  \ | |/    \| 1----2 [산타집] 산타 할아버지의 집을 한붓 그리기로 그리는 모든 방법을 출력해 보아요! ---알고리즘 요약--- DFS를 이용해 모든 경우를 검색해 본다. */ #include <iostream> #include <windows.h> using namespace std; bool a[5][5]={{0,1,1,0,1},{1,0,1,0,1},{1,1,0,1,1},{0,0,1,0,1},{1,1,1,1,0}}; int path[9],n; void DFS(int vertex){      int i;           path[n]=vertex;      if(n==8){               for(i=0;i<9;i++)cout<<path[i]+1<<" ";               cout<<endl;               return;      }           for(i=0;i<5;i++){     ...

/* UVA302 존의 드라이빙 존은 친구들을 만나러 드라이빙을 계획중이다. 친구들은 마을에 있는 도로마다 한명씩 산다. 존은 드라이빙을 마친후 집으로 가장 최단 시간안에 돌아와야 한다. 가장 최단시간에 드라이빙을 마치려면 각각의 도로를 한번씩만 거쳐서 집으로 돌아와야한다. 마을에는 1<=n<1995 범위의 정수이름을 가지는 도로가 존재하며 각각의 도로의 이름은 겹치지 않는다. 도로는 딱 2개의 교차점과만 양끝으로 연결되어 있으며 교차점은 1<=m<44의 정수이름을 가진다. 만약 최적의 드라이브 코스가 여러개면 가장 번호가 낮은 도로를 출력한다. 존은 첫번째 도로에서 더 작은 숫자의 교차점에 산다. 이때 존의 드라이빙을 계획해보자. Input x y z// x: 도로 z의 한쪽 끝에 연결된 교차점의 이름, y: 도로 z의 반대쪽에 연결된 교차점 . . . 0 0//테스트 데이터의 끝. 또 다른 테스트 데이터 입력 가능 0 0 0 0//빈테스트 데이터로 입력 데이터의 끝  Output 1 2 4 5 3//방문하는 도로를 순서대로 출력. 테스트 데이터 1 결과 Round trip does not exist//테스트 데이터 2 결과. 적합한 코스 없음. <알고리즘 요약> 교차점을 정점으로 도로를 간선으로 하는 오일러 회로를 그리디 알고리즘을 통해 구한다. Greedy Euler Path 에서 했던것처럼 일단 어떤 경로로든 더이상 진행할 수 없는 끝점에 도달하고도 간선이 남아 있다면 중간에 지나지 않은 회로들이 존재하는 것이므로(남은 간선들이 모두 정점에 짝수개씩 연결되어 있으므로) 중간에 또다른 회로가 존재하는 정점으로 돌아가서 회로를 검색하고 그 회로를 경로에 중간에 추가해준다. 그러고도 남은 간선이 존재한다면 회로가 존재했던 정점을 다시 검색하고 계속 이전 정점으로 검색하면서 또다른 회로가 존재하면 또 추가해주고 검색하고를 반복하여 모든 간선을 소비할 때 까지 반복한다. 그러나 Greedy Euler Path...

/*finding an Euler path using Greedy Algorithm 그리디 알고리즘을 이용해 오일러 경로를 찾는 알고리즘   DFS와는 다르게 각각의 정점에서 아무 간선으로나 진행 *하여 최대한 빠르게 끝 정점 *에  도달하고 경로를 저장한다음 중간에 무시하고 지나간  회로* 들을 다시 탐색하여 경로 중간에  추가시켜주는 방법을 사용하여 훨신 빠르다.   * 어느 간선을 이용하던 끝정점에 도달하게끔 되어있다.  * 여기서 말하는   끝정점은 더이상 진행할 간선이 존재하지 않아 고립되게 되는 점이다. *지금 까지 남아있는 간선들만 보았을때 그 그래프는 차수가 짝수인 점들로 이루어진 그래프와 같아서 오일러 회로가 반드시 존재한다. 중간에 지나친 회로들을 찾는 방법 :  현재 저장된경로의 끝 정점부터 처음 정점까지* 하나하나 사용하지 않은 간선과 연결되있나 검사하면 된다. 그리고 중간에 회로가 추가되었을때 추가된 회로까지 포함하여 검사가 완료되지 않은 점들을 또 검사한다. *반대방향도 상관 없다. 그냥 경로내의 모든 정점에 사용하지 않는 간선이 존재하는지 여부만 확실히 하면 된다  이러한 과정을 통해 오일러 경로를 구할 수 있다. 여기서는 경로를 두개의 스택을 이용하여 추가를 하지만, 연결 리스트를 사용하건 뭘 사용하건 만든사람 마음이다. input: n m / n<=100: the number of vertex m<=1000: the number of line a b / a: one side of a line ,b: the other side of a line. repeat m-1 time. */ #include <iostream> #include <windows.h> #include <vector> usin...

그리디 알고리즘은 가장 트리에서 윗 레벨에서 아랫 레벨로 검색해갈때 각각의 레벨에서 모든 경우중 가장 최적이라고 생각되는 경우만 검색 하는 것이다. 따라서  결과적으로 구한 해가 최적의 해가 아닐 가능성이 존재 한다. 그리디 알고리즘으로 구한 해가 최적임을 보장하려면 각각의 레벨에서 최적의 경우를 구한것이 결과적으로도 최적의 해가 될수 있음을 수학적으로 증명하여야 한다. 예를 들어 보자 Greedy Euler Path 이란 예제가 있다. 그리디 알고리즘은 차수가 짝수인 정점들과 2개의 차수가 홀수인 정점들로 이루어진 그래프에서 오일러 경로를 다음과 같은 방식으로 찾는다. (모든 차수가 짝수여도 된다) 시작점은 가장 낮은 수를 가진 홀수 차수의 점이다. 0.현재 정점을 스택 1에 저장한다. 만약, (1).현재 정점과 연결된 정점중 가장 낮은 수를 가진 정점을 찾아간다.. (2).만약 도중에 간선을 다 소모하지 않고도 현재 정점과 연결된 정점이 없어서 진행하지 못하면 그점을 스택 1에서 제거하고 스택 2에 저장하고 전 정점으로 건너 뛴다. (3).모든 간선을 소모하여 더이상 진행할 수 없을때 종료된다. 종료한뒤 스택 2의 원소들을 나중에 들어온것 부터 스택1로 옮긴다. 각각의 레벨(현재 정점)에서 이러한 조건을 통해 특정 경우로 나아가는 것을 논리적으로 최적의 해를 보장하게 된다. 사실, 각각의 정점에서 가장 낮은 수를 찾아 가는 경우를 포함해서 사실 그냥 연결되있는 아무 정점을 찾아가도 보장이된다. 1번 규칙에 따라 꾸준히 축적되가던 경로가 어떤 특정한 점에서 간선을 전부 소모하지 않았음에도 더이상 진행할 수가 없다면, 모든 간선을 소모하기 전에 도착정점의 마지막 간선을 소모했다는 뜻이다. 따라서 이러한 정점들을 스택 2에다가 순서대로 저장해주면 도착정점에 도달할 최후의 정점이 채워지게 되는것이...

정점의 갯수와 간선의 갯수를 입력하고 각각의 간선을 입력한후 오일러경로 하나를 출력하는 프로그램을 만들어 보겠다. /* 백트랙킹 을 이용한 오일러 경로 탐색 프로그렘 오일러 경로가 존재하면 하나만 출력하고 없으면 "경로 없음"을 출력. 입력되는 정점은 100개 이하이며 1번부터 카운팅한다. 간선은 10000개 이하이다 모든 정점은 차수가 1이상이다*/ #include <iostream> #include <windows.h> using namespace std; bool odd[100];//홀수인 정점을 저장 int m, n;//정점의 수, 간선의 수 int a[100][100];//[출발 정점][도착정점]을 잊는 간선을 저장 int path[10000];//경로를 저장. bool EulerPath(int vertex, int idx){      int i;      path[idx]=vertex;//idx번째 정점을 저장.           if(idx==n){//도착지에 도달하면 출력하고 종료                 for( i=0 ;i<n;i++){                         cout<<path[i]+1<< "->";               ...

정점들과 각각의 정점들을 잇는 간선들이 존재한다고 하자.(간선이 연결되지 않은 정점은 고려하지 않는다, 모든 정점에는 적어도 하나 이상의 간선이 연결되어있어야 한다.) 경로 는 한 정점에서 출발해 다른 정점에 도달하거나 다시 출발 정점으로 돌아오는 방법이다. 회로 는 한 정점에서 출발해 다시 그 정점으로 돌아오는 방법이다. 오일러 경로와 회로는 모든 간선을 한번씩 방문하면서 원하는 정점까지 이동할 수 있는지에 관한 문제이다. 차수 는 한 정점에서 다른 정점으로 연결된 간선의 갯수 이다. 그렇다면, 오일러 회로를 존재하게 하는 필요충분 조건은 무엇있까?  모든 정점의 차수가 짝수 <->오일러 회로가 존재. 모든 정점의 차수가 짝수인 상황을 가정해보자. 시작점이 아닌 차수가 짝수인 정점은 그 정점과 연결된 간선을 모두 한번씩 지나가면 필연적으로 그 정점에서 끝을 맺을 수가 없다. 들어온 숫자 만큼 나가기 때문이다. 따라서 이용할수 있는 마지막 간선을 타고 또다른 정점에 도달하고. 또다른 정점도 아무리 많은 간선을 소모했다 하더라도 마지막 하나는 다른 정점으로 이어주게 된다. 따라서 어떤 간선을 먼저 이용하던간에 궁극적으로 다시 시작 정점에 돌아올 수 밖에 없다. 시작정점도 간선을 통해 나간 수만큼 들어와야 하기 때문이다. 따라서 모든 정점의 차수가 짝수일때는 오일러 회로가 존재하며, 그 어떤 정점도 회로의 시작점이 될 수 있다. 반대로 차수가 홀수인 정점이 존재한다고 해보자. 그렇다면, 모든 간선을 다 한번씩 이용 못하는 경우도 생길 수 있겠다. 또한 모든 간선을 반드시 한번씩 이용하는 경우를 가정했을때도 결국 중간에 껴있는 차수가 홀수인 정점에서 더이상 나아갈 간선이 없이 막혀버린다. 따라서 차수가 홀수인 정점이 존재할때는 반드시 오일러 회로는 존재하지 않는다. 그렇다면, 오일러 경...

enum  이름 {원소1, 원소2, ...}은 데이터형을 새로 정의하는대 사용한다. 그렇게 하면, 지정한 이름의 열거형이 새로 정의가 되고 원소 1을 0으로 시작하여 차례대로 값들이 부여된다. enum 이름 {원소 1, 원소2 = 4, 원소 3 ...} 이런식으로 정의를 한다면 원소 1을 0으로 시작하여 차례대호 값이 대응되지만, 중간에 원소2 에 4를 대응 시킴으로서 0, 4 ,5 ...와 같은 순서로 값이 부여된다. 원소 2= 4 원소 5=4 같은 식으로 정의하면 0,4,5,6,4,5...같은 식으로 부여할 수 있다. 그렇다면, 열거형의 원소들은 부여받은 정수값을 통해 int  상수처럼 사용할 수 있을까? 그렇다. 하나의 상수처럼 사용할 수 있으며 따라서 다음과 같은 코드도 문제없이 작용한다. enum music {pop, dance, hiphop, club, rock, classic, jazz}; int a = hiphop; a에는 2가 들어간다. 그럼 반대로 music m = 3; 이것은 불가능하다. music 열거형에 int를 집어넣을려면 music열거형으로 변환시켜줘야 한다. music m = music(3); 이러면 m은 club이 된다. 사실 그냥 왠만하면  정수를 쓰지 않고 직접 상수 이름을 입력해 주는게 안했갈리고 좋다 music m = club; 그리고 타자치기 귀찮아서 넘어갔지만 상수는 왠만하면 대문자로 선언해주자 enum music {POP, DANCE, HIPHOP, ROCK, CLASSIC, JAZZ};

/*N<=15을 입력받고 NxN크기의 달팽이 수열을 출력하는 프로그렘 왼쪽 위부터 시계방향으로 바깥 쪽에서 안쪽으로 자연수를 1부터 올림차순으로 출력 */ #include <iostream> #include <windows.h> using namespace std; int main(){     int n,i,j,c=0;     int a[15][15];         cin>>n;     //a번째 껍질에서 각 꼭지점으로부터 시계방향으로 n-2*(a-1)-1개씩 순서대로 입력     for(i=1;i<=n/2;i++){                         //4개의 꼭짓점에서 시작                      for(j=0;j<n-2*(i-1)-1;j++)a[i-1][i-1+j]=++c;                      for(j=0;j<n-2*(i-1)-1;j++)a[i-1+j][n-i]=++c;                 ...

로봇 연구소에서는 매장의 어느 지점에서 다른 지점까지 이동하는 로봇을 구상하고 있다. 로봇은 트랙을 따라 이동하며, 트랙은 직사각형 모양의 매장내부에 1미터 간격의 격자무늬로 배치되어 있다. 매장의 크기는 가로 n미터 세로 m미터이고 트랙은 가게의 꼭지점부터 1미터 간격으로 설치 되어있으며 가게 모서리로는 설치되어 있지 않다. 로봇의 모양은 밑면이 반지름  0,8미터인 원통형 이다. 매장 내부에는 1mx1m크기의 장애물 들이 존재하고 장애물들은 1미터 간격의 격자무늬 안으로 배열되어있어 1미터 단위의 격자 밖으로 삐져나올 일은 없다. 로봇은 벽이나 장애물에 걸리면 그 트렉을 지나갈 수 없다. 로봇은 트랙의 교차점에서만 회전을 할 수 있고 오직 전진만 가능하다. 로봇은 1초동안 다음과 같은 행동을 하나씩 할 수 있다. 1. 1m 전진 2. 2m 전진 3. 3m 전진 4. 오른쪽 90도 회전 5.왼쪽 90도 회전 이제 로봇이 매장의 한쪽 지점에서 다른쪽 지점으로 이동하는데 가장 짧게 걸리는 시간을 구하는 프로그램을 만들어 보자. ***입력은 다음과 같다*** 입력은 여러개의 테스트 데이터로 이루어진다. m n (매장의 크기 세로와 가로(m) m,n<=50) o o ... o . . . o o ... o(mxn크기의 매장지도 1mx1m공간을 단위로 나타내며, 1은 장애물의 위치를 나타낸다) d1 d2 e1 e2 direction (출발점의 좌표 :매장의 북서쪽 지점으로부터 e1m 남쪽 e2m 동쪽지점/ 도착점좌표 : 북서쪽으로부터 d1m남쪽 d2m동쪽지점 / direction 시작할때 로봇의 정면방향, e1,e2,d1,d2는 정수이며 direction은 방위의 영어 소문자이다(ex, south)) 이게 한개의 태스트 데이터이며 또 다른 테스트 데이터의 입력이 가능하다. 0 0이 입력되면 테스트 데이터의 끝이다...