'language/알고리즘'에 해당되는 글 5건

#include <iostream>

#include <cstring>

using namespace std;

#define START 1

#define END 7

char *WEEK[8] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};

void End_MONTH(int x, int *y, int *z, int a);

void Calculate_INDEX(char* x, int *y);

int main() {

    int T, END_MON, MON, MON_BEFORE, THIS_DAY, DAYS,INDEX= 0;

    int WEEKDAY[8]={NULL};

    char DAY_CHAR[10]={NULL};

    cin>>T;

    while(T--){

        cin>>MON>>DAYS>>DAY_CHAR;

        End_MONTH(MON, &END_MON, &MON_BEFORE, DAYS);

        Calculate_INDEX(DAY_CHAR, &INDEX);

        // 인덱스를 기준으로 배열의 왼쪽을 채움

        THIS_DAY= DAYS;

        for(int i= INDEX; i>= START; i--) {

            WEEKDAY[i-1]= THIS_DAY;

            THIS_DAY--;

            if(THIS_DAY <1) THIS_DAY= MON_BEFORE;

        }

        // 인덱스를 기준으로 배열의 오른쪽을 채움

        THIS_DAY= DAYS;

        for(int i= INDEX; i<= END; i++) {

            WEEKDAY[i-1]= THIS_DAY;

            THIS_DAY++;

            if(THIS_DAY >END_MON) THIS_DAY= START;

        }

        for(int i= 0; i<6; i++) {

            cout<<WEEKDAY[i]<<" ";

        }

        cout<<WEEKDAY[6]<<endl;

    }

    system("pause");

}

// 현재 월, 지난 월의 마지막 일수를 계산해서 저장

// 다음 달의 경우, 1일부터 시작하므로 변수에 저장하지 않음

void End_MONTH(int x, int *y, int *z, int a) {

    // 일수가 31일인 달

    if(x == 1 || x == 3 || x == 5 || x == 7 || x == 8 || x == 10 || x == 12) {

        // 예외값 처리

        if(a <1 || a> 31) exit(1);

        //8월과 1월의 경우, 지난 달의 일수는 31일

        if(x == 8 || x == 1) {

            *y= 31; *z= 31;

            return;

        }

        // 3월의 경우, 지난 달의 일수는 28일

        if(x == 3) {

            *y= 31; *z= 28;

        }

        *y= 31; *z= 30;

        return;

    }

    // 일수가 28일인 2월

    else if(x == 2) {

        if(a <1 || a> 28) exit(1);

        *y= 28; *z= 31;

        return;

    }

    // 일수가 30일인 달

    else {

        if(a <1 || a> 30) exit(1);

        *y= 30; *z= 31;

        return;

    }

}

// 입력받은 문자열이 한 주의 몇 번째 일수에 위치하는지 인덱스 계산

void Calculate_INDEX(char* x, int *y) {

    int k= 0;

    for(int i=0; i<END; i++) {

        k =strcmp(x, WEEK[i]);

        if(k== 0) {

            *y= i+1;

            return;

        }

    }

    if(*y ==0)

        exit(1);

}

출력 결과만 보면 문제가 없는 것처럼 보이나, 답안 제출 시 오답 판정된다.

디버깅이 끝나면 해당 부분을 고쳐 수정할 계획이다.

#include <iostream>

#include <cstring>

using namespace std;

int main()

{

                  int T, i=1;

                  int count, length;

                  char str[81]={NULL};

                  cin>>T;

                  while(T--){

                                   cin>>count>>str;

                                   length=strlen(str);

                                   cout << i << " ";

                                   for(int j=count-1; j<=length-1; j++){

                                                     str[j]=str[j+1];

                                   }

                                   for(int j=0; j<=length-1; j++){

                                                     cout<<str[j];

                                   }

                                   cout<<endl;

                                   i++;

                  }

                  system("pause");

                  return 0;

}

#include <iostream>

#include <cstring>

using namespace std;

int main()

{

                  int T, i=1;

                  int count, length;

                  char str[81]={NULL};

                  cin>>T;

                  while(T--){

                                   cin>>count>>str;

                                   length=strlen(str);

                                   cout << i << " ";

                                   for(int j=count-1; j<=length-1; j++){

                                                     str[j]=str[j+1];

                                   }

                                   for(int j=0; j<=length-2; j++){

                                                     cout<<str[j];

                                   }

                                   cout<<endl;

                                   i++;

                  }

                  system("pause");

                  return 0;

}

위 두 코드들은 거의 같지만 단 한 글자만 다르다. 위는 오답, 아래는 정답으로 인정되었다.

length-1의 경우, 보이지 않는 NULL 문자열 또한 같이 출력되기 때문에 

화면 상으로는 보이지 않더라도 정답으로 인정하지 않는 것 같다.

1. 교환법칙 : A^B=B^A

2. 결합법칙: (A^B)^C = A^(B^C)

3. 항등원 존재 : A^0 = 0^A = A

4. 역원 존재 A^A⁻¹=0

위의 4가지는 모든경우의 수를 대입하면 증명할 수 있습니다.

1.교환법칙 증명

모든 경우의수 AB

00 >>>>> 같으므로 생략

01 >>>>>  0^1 = 1,  1^0 = 1  좌측, 우측 같음 

10 >>>>>  1^0 = 1,  0^1 = 1  좌측, 우측 같음

11 >>>>> 같으므로 생략

모든 경우 같으므로 증명됨

2.결합법칙 증명

모든 경우의 수 ABC

000 >>>>> 같으므로 생략

001 >>>>> (0^0)^1 = 1, 0^(0^1)= 1 좌측, 우측 같음

010 >>>>> (0^1)^0 = 1, 0^(1^0)= 1 좌측, 우측 같음

011 >>>>> (0^1)^1 = 0, 0^(1^1)= 0 좌측, 우측 같음

100 >>>>> (1^0)^0 = 1, 1^(0^0)= 1 좌측, 우측 같음

101 >>>>> (1^0)^1 = 0, 1^(0^1)= 0 좌측, 우측 같음

110 >>>>> (1^1)^0 = 0, 1^(1^0)= 0 좌측, 우측 같음

111 >>>>> 같으므로 생략

모든경우 같으므로 증명됨

3. 항등원 존재

모든 경우의 수  A

0 >>>>>  0^0 = 0^0 = 0,  같음

1 >>>>>  1^0 = 0^1 = 1, 같음

모든 경우 같으므로 항등원 0 존재 증명됨

4. 역원

모든 경우의 수  A

0 >>>>>  0^0 = 0, 

1 >>>>>  1^0 = 1 ,

항등원 0의 역원 A⁻¹  는 A 자신임

위의 사실을 바탕으로 XOR SWAP 알고리즘을 살펴보면

==============================================

순서대로 0, 1, 2, 3 살펴보면

0. 처음 상태 ----------------A----------------B----------------

1.     A=A^B---------------- A^B ------------- B----------------

2.     B=B^A ----------------A^B -----------B^(A^B)-------------

B^(A^B)      는

B^(B^A)  교환법칙 적용

(B^B)^A  결합 법칙 적용, 역원이 자기 자신이니 (B^B)= 0

0^A 항등원이 존재하므로

A 가 됩니다.

3. A=A^B ----------------(A^B)^A----------------A---------------

(A^B)^A  는

(B^A)^A 교환법칙

B^(A^A) 결합법칙 , 역원이 자기 자신이니 (A^A=0)

B^0 항등원이 존재하므로 이므로

B 가 됩니다.

     결과 ----------------B---------------- A----------------

스왑이 일어나는것을 확인 할 수 있습니다.

(출처: http://kin.naver.com/qna/detail.nhn?d1id=1&dirId=1040101&docId=230636611&qb=YysrIHhvcg==&enc=utf8&section=kin&rank=1&search_sort=0&spq=0&pid=SGwBNsoRR1dssvp6tX4sssssssG-168491&sid=kKuYgjVn5WDRDdonE69m3g%3D%3D)

ENDIANS

The two island nations Lilliput and Blefuscu are severe rivals. They dislike each other a lot, and the most important reason was that they break open boiled eggs in different ways.

People from Lilliput are called little-endians, since they open eggs at the small end. People from Blefuscuare called big-endians, since they open eggs at the big end.

This argument was not only about their breakfasts but about their computers, too. Lilliput and Blefuscu's computers differed in the way they store integers; they stored the bytes in different orders. Computers from Lilliput(*little-endians*) ordered it from the LSB(least significant byte) to the MSB(most significant byte), and computers from Blefuscu was exactly the opposite.

For example, a 32-bit unsigned integer 305,419,896 (0x12345678) would be saved in two different ways:

For example, a 32-bit unsigned integer 305,419,896 (0x12345678) would be saved in two different ways:

• 00010010 00110100 01010110 01111000 (in an Blefuscu computer)
• 01111000 01010110 00110100 00010010 (in an Lilliput computer)

Given some 32-bit unsigned integers retrieved in a wrong endian, write a program to do a conversion to find the correct value.

비트 연산은 자주 사용해보지 않아서 이해하고 구현하는데 약간의 시간이 걸렸다.

위와 같은 연산을 구현하기 위해서 다음과 같이 실험적인 코드 작성 및 컴파일을 수행했다.

#include <iostream>

#include <bitset>

using namespace std;

int main(){

                  //int cases;

                  unsigned int x=2018915346;

                  //cin >> cases;

                  unsigned int a, b, c, d, e;

                  a = (x>>24);

                  b = (x<<8)>>24<<8;

                  c = (x>>8)<<24>>8;

                  d = (x<<24);

                  cout<< bitset<32>(x) <<endl;

                  cout<< bitset<32>(a) <<endl;

                  cout<< a <<endl;

                  cout << bitset<32>(b) << endl;

                  cout<< b <<endl;

                  cout << bitset<32>(c) << endl;

                  cout<< c <<endl;

                  cout << bitset<32>(d) << endl;

                  cout<< d <<endl;

                                   //while(cases--){

                                                     e=a+b+c+d;

                                                     cout <<e <<endl;

                                   //}

                  getchar();

}

출력된 결과 화면

위 결과를 토대로 다음과 같이 간단한 코드로 변환했다.

#include <iostream>

using namespace std;

int main(){

                  int cases;

                  unsigned int x;

                  cin >> cases;

                  while(cases--){

                                   cin >> x;

                                   cout <<(x>>24)+((x<<8)>>24<<8)+((x>>8)<<24>>8)+(x<<24) <<endl;

                  }

}

간단한 코드임에도 실행 시간이 58ms 이었다. 

이보다 더 긴 코드임에도 불구하고 실행시간이 5ms인 경우도 있는걸 보니, 위 코드가 매우 효율적이지는 않은 것 같다.