본문 바로가기

개발&컴퓨터/알고리즘

[알고리즘문제] 숫자 대응

반응형

이번에도 알고리즘 프로그래밍 문제입니다.


한 번 풀어보아용~



문제!!


N이 n이하인 양의 정수 집합 {1, 2, 3, ․․․, n}을 나타낸다고 하자. 우리는 다음 조건을 만족하는 일대일 대응 함수 F: N → N을 구하고자 한다.


조건: 각각의 i에 대해서 i+F(i) = 2k를 만족하는 정수 k, k≥1가 존재한다, 1≤F(i)≤n.


즉, N에 속한 모든 i에 대해 i와 그에 대응하는 함수값 F(i)를 더한 값이 2의 거듭제곱(power)인 형태의 값이 되어야 함을 말한다. 예를 들어 n=5인 경우에 위의 조건을 만족하는 일대일 대응 함수가 다음과 같이 존재한다.





위의 예에서 1+1 = 21, 2+2 = 22, 3+5 = 23, 4+4 = 23, 5+3 = 23이므로 이러한 대응이 위의 조건을 만족함을 알 수 있다.


n이 주어졌을 때, 위의 조건을 만족하는 일대일 대응 함수를 출력하는 프로그램을 작성하시오.





( 아닐수도..ㅎㅎㅎ)


- 소스 코드 -


#include <stdio.h>

#include <conio.h>


#define USABLE 0 // 사용가능한공간

#define UNUSABLE 1 // 사용된공간


int data[1001] = {0, }; // n인자까지의배열만을사용. 일대일대응을체크하기위해, 집합내에같은숫자가두개중복되는것을방지하기위해사용


int result[1001] = {0, }; // 결과값을저장하는배열

int n; // 입력받은값


void Calculate();

void InputFile();

void OutputFile();


void main()

{

        InputFile(); // 파일로부터데이터얻기

        Calculate(); // 결과값구하기

        OutputFile(); // 파일에결과쓰기


        getch();

}


void Calculate()

{

        int i, j, square = 2; // i,j : for문을위한임시변수, square : 기준이되는2의제곱수


        while(1) // 최대9번이상반복되지않음1000이하의2의제곱수중가장큰수는2^9이므로

        {

               if(square <= n) square *= 2; // 입력받은n값보다크면서가장가까운2의제곱수구하기

               else break; // 루프빠져나가기

        }


        for(i = n; i >= 1; i--) // 계산은큰수부터작은수로거꾸로구해나간다.

        {

               if(i < (square / 2)) square /= 2; // i가현재설정된2의제곱수보다작은값이라면square에현재설정된2의제곱수보다한단계낮은2의제곱수저장


               if(data[i] != USABLE) continue; // 이미사용된숫자라면


               for(j = 1; j <= n; j++) // i와함께2의제곱수에맞추기위한j를찾아낸다.

               {

                       if(data[j] != USABLE) continue; // 이미사용된숫자라면


                       if((i + j) == square) // ij의합을통해적절한2의제곱수가되었다면

                       {

                              data[i] = data[j] = UNUSABLE; // 사용된숫자이므로다시사용하지못하도록1로체크

                              result[i] = j, result[j] = i; // 결과배열에각각의적절한결과값저장

                       }

               }

        }


        printf("작업이완료되었습니다.\n");

}


void InputFile() // 파일로부터입력받기

{

        FILE *fp; // 파일포인터개체

        fp = fopen("Input.txt", "r"); // 파일열기

        fscanf(fp, "%d", &n); // n 값을입력받는다.

        fclose(fp); // 파일닫기

}


void OutputFile()

{

        FILE *fp; // 파일포인터개체

        fp = fopen("Output.txt", "w"); // Output.txt 파일을쓰기형식으로열기

        fprintf(fp, "%d\n", n); // 초기입력값출력


        for(int x = 1; x <= n; x++) // 결과출력

               fprintf(fp, "%d\n", result[x]);


        fclose(fp); // 파일닫기

}




테스트 (샘플)


* n 으로 8이 입력된 경우 결과 : 8 7 6 5 4 3 2 1 8


n = 8;

square = 16 (n 보다 크면서 가장 근접한 2의 제곱수를 얻어냄)


i ) 첫번째 외부 루프 실행 i = 8

 j = 1 (X), j = 2 (X) j = 8 (O, 8 + 8 = 16(2^4), square값과 동일)

data[8] = data[8] = UNUSABLE, result[8] = result[8] = 8


ii) 두번째 외부 루프 실행 i = 7

i 8(square/2) 보다 작은 값을 가지므로 square = square / 2 로 변경, square = 8

j = 1 (O, 7 + 1 = 8(2^3), square값과 동일)

data[7] = data[1] = UNUSABLE, result[7] = 1, result[1] = 7


iii) 세번째 외부 루프 실행 i = 6

j = 1(X, 1 UNUSABLE상태), j = 2(O, 6 + 2 = 8(2^3), square값과 동일)

data[6] = data[2] = UNUSABLE, result[6] = 2, result[2] = 6


iv) 네번째 외부 루프 실행 i = 5

j = 1(X, UNUSABLE), j = 2(X, UNUSABLE), j = 3(O, 5 + 3 = 8(2^3), square값과 동일)

data[5] = data[3] = UNUSABLE, result[5] = 3, result[3] = 5


v) 다섯번째 외부 루프 실행 i = 4

j = 1, j = 2, j = 3(모두X, 이미 UNUSABLE), j = 4(O, 4 + 4 = 8(2^3), square값과 동일)

data[4] = data[4] = UNUSABLE, result[4] = result[4] = 4


vi) 여섯번째 외부 루프 실행 i = 3

i 4(square/2) 보다 작은 값을 가지므로 square = square / 2 로 변경, square = 4

이미 i = 3은 네번째 루프를 돌 때 적절한 값을 얻었으므로 건너 뜀.


vii) 일곱번째 외부 루프 실행 i = 2

이미 i = 2는 세번째 루프를 돌 때 적절한 값을 얻었으므로 건너 뜀.


viii) 여덟번째 외부 루프 실행 i = 1

i 2(square/2) 보다 작은 값을 가지므로 square = square / 2 로 변경, square = 2

이미 i = 1은 두번째 루프를 돌 때 적절한 값을 얻었으므로 건너 뜀.


결과 값 (result배열 값 ) 출력 : 8 7 6 5 4 3 2 1 8



소스 코드 및 실행 파일 받기


mapping.zip




반응형