SORTGAME C언어로 작성하는 부분 질문드립니다.

  • mhs4670
    mhs4670

    안녕하세요
    SORTGAME 문제를 책보면서 풀고있는데

    제가 c++언어는 익숙치 않아서,

    알고리즘 플로우만 보면서

    대강 해석하면서 c언어로 다시 짜보고 있습니다

    이 문제는 책에서

    1부터 8이하의 모든 n에서

    정렬된 배열에서 다른 모든 상태까지 도달하는데 필요한

    뒤집기 연산의 수를 모두 계산해 두고

    입력값을 받는 즉시, 뒤집는 연산의 값을 출력하는 알고리즘입니다.
    ((20,30,50)같은 배열이 나와도 결국 (2,3,5)를 정렬하는 것과
    cost는 같으므로)

    근데 이 정점들을 표현하기 위해서

    배열로 표현을 하는 것 같은데

    예를 들면

    4자리에서는 {3,4,1,2},{1,2,3,4} ~~~ 등등
    4!의 배열이 나오겠지요

    그럼 총 8자리까지 입력이 나오니까

    처음 배열을 선언할때(c언어로 구현하는 경우)

    int map[8!][8] 이렇게 선언을 해야하는 건가요?

    제가 처음 책을 안보고 짜려했을 때,

    이렇게 짜려고 생각은 했었는데..

    short로 짠다고 생각해도

    2바이트*8!*8=645120바이트 의 용량을 먹게되는데..

    약 64MB니까,, 이 방법을 포기했거든요..

    그래서 저는

    그냥 일차원배열로 선언하고

    숫자로 받아서 구현했습니다.

    그러다보니 reverse할때도 나누고빼고더하고지지고볶고하다보니

    4~5자리는 괜찮은데 8자리에서

    런타임에러가 나는것 같더라구요..

    혹시

    제가 잘못생각하고 있는건가요 ㅠㅠ..

    혹시 c언어로 구현하셨던 분 있으면 도움 부탁드립니다.

    이건 그냥 참고용으로

    제가 짠 코드를 올려드립니다

    #if 1

#include<stdio.h>
#include<math.h>
#define MAX (40320) //8!
struct st{
    int val;
    int cnt;
};
int n; //length of array
int Queue[MAX];
struct st visited[MAX];
int arr[9];
int ori[9];
int ori_obj[9];
int cnt;
int wp, rp;
int visWp;
int tp[9];
void In_Queue(int num){
    Queue[wp++] = num;
}
int Out_Queue(void){
    return Queue[rp++];
}
void printArr(void){
    int i;
    for (i = 1; i <= n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
void sort(void){
    int i, j, temp;

    for (i = 1; i <= n; i++)
        arr[i] = ori[i];

    for (i = 1; i < n; i++){
        for (j = i; j < n ; j++){
            if (arr[j] > arr[j + 1]){
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    for (i = 1; i <= n; i++)
        ori_obj[i] = arr[i];
    for (i = 1; i <= n; i++){
        for (j = 1; j <= n; j++){
            if (ori_obj[i] == ori[j]){
                arr[i] = j;
            }
        }
    }
    //printArr();
}

void input(void){
    int i;
    scanf("%d", &n);
    for (i = 1; i <= n; i++){
        scanf("%d", &ori[i]);
    }
    sort();
}
int reverse(int len, int pos, int num){ 
    int i, j, temp;
    int ret=0;

    for (i = n; i>0; i--){
        tp[i] = num % 10;
        num /= 10;
    }
    for (i = pos; i < pos+(len / 2); i++){
        temp = tp[i];
        tp[i]=tp[i + len - 1];
        tp[i + len - 1] = temp;
    }
    ret += tp[n];
    for (i = n - 1; i > 0; i--){
        ret += tp[i] * (int)pow(10.0, (double)(n - i));
    }
    return ret;
}
int isVisited(int num){
    int i;
    for (i = 0; i < visWp; i++)
        if (visited[i].val == num) return 1;
    return 0;
}
void BFS(void){
    int i, j,k;
    int cur=0;
    int obj = 0;
    int rev;
    int out;
    int outP;
    if (n == 1) return;
    cur += arr[n];
    obj += n;
    for (i = n-1; i > 0;  i--){
        cur += (arr[i] * (int)pow(10.0 , (double)(n - i)));
        obj += i * (int)pow(10.0, (double)(n - i));
    }
    if (cur == obj) return;
    In_Queue(cur);
    visited[visWp].val = cur;
    visited[visWp++].cnt = 1;
    while (wp > rp){
        out = Out_Queue();
        if (out == obj) {
            for (k = 0; k < visWp; k++)
                if (visited[k].val == out) break;
            cnt = visited[k].cnt - 1;
            return;
        }
        for (i = 2; i <= n; i++){ // length of block for sort
            for (j = 1; j <= n - i + 1; j++){ // block start
                rev = reverse(i, j, out);
                if (isVisited(rev)) continue;
                visited[visWp].val = rev;
                for (k = 0; k < visWp; k++)
                    if (visited[k].val == out) break;
                visited[visWp++].cnt = visited[k].cnt + 1;
                In_Queue(rev);
            }
        }
    }
}
void init(void){
    int i, j;
    wp = rp = 0;
    visWp = 0;
    cnt = 0;
}
int main(void){

    int C, i;
    //input();
    scanf("%d", &C);
    for (i = 0; i < C; i++){
        input();
        BFS();
        printf("%d\n", cnt);
        init();
    }


    return 0;
}


#endif

    ..


    6년 전
1개의 댓글이 있습니다.
  • keith
    keith

    꽤 오래전의 질문이지만, 아무도 답변이 없어서 혹시나 도움이 될까 싶어서 적어봅니다.(이미 해결하셨기를 바래봅니다.)

    먼저 첫번째, 질문 : int map[8!][8] 이렇게 선언을 해야하는 건가요?

    C의 경우는 최근 나온(제가 아재라서^^ 저에게는 최신입니다.^^) C++이나, Java 등과 같은 고급언어들과는 다르게, 변수 선언을 할때 문법 자체가 동적 할당을 지원하지 않습니다.
    물론 동적 할당을 할 수 있습니다만, 그냥 C언어 자체에서 바로 지원하지는 않는다는 뜻입니다.
    예를들면, 아래와 같은 변수 선언은 불가능합니다.

    void test(int n) {
    int array[n]; // 컴파일 오류
    // ... 생략
}

    그 이유를 생각해보면 C와 같은 시스템 친화적(?)인 언어들은, 프로그램이 메모리상에 로드되면, 함수에 해당하는 메모리 영역 앞부분에 변수 스택 영역을 남겨두고, 그 뒷부분 부터 프로그램의 Binary 코드들이 들어갑니다.
    따라서, 변수 영역의 크기가 Fix되어야만 프로그램이 성립합니다.
    그런데, 만약 동적으로 배열의 크기를 필요한만큼 선언하고 싶다면 위의 프로그램을 아래와 같이 바꾸셔야 합니다.

    #include<stdlib.h>

void test(int n) {
    int *array;
    array = (int*)malloc(sizeof(int)*n);    // int 변수 사이즈 * n 만큼의 메모리 영역을 운영체제에게 할당 받고, 할당받은 주소값을 받아옵니다.
    // ... 생략, array[1] = 0; 같이 사용하셔도 무방합니다.
    free(array);
    // 만약 위에서 운영체제에게 할당을 1번만 받고 프로그램이 종료되면, 해당 프로그램이 종료되면서 할당받은 메모리는 모두 반환되게 되어있으니, free()를 안해주셔도 상관없으나, 여러번 호출되는 함수에서 사용된다면, 그 목적을 다한 변수는 메모리상에서 제거해 주셔야 합니다.

    두번째 질문 : 4~5자리는 괜찮은데 8자리에서 런타임에러가 나는것 같더라구요..

    문제는 short 형을 사용한다는데에 있습니다. short형은 16비트 부호형 정수로써, -32768~32767까지의 정수를 표현할 수 있습니다.
    만약

    short t;
scanf("%d", &t);

    위와 같이 코딩했을 경우, 입력값이 위에 제시한 값보다 크다면 access violation 에러가 날 수 있습니다. 왜냐하면, t라는 변수는 16비트 변수인데, scanf의 %d는 32비트 정수를 받습니다. t라는 변수는 2바이트의 공간을 차지하고 있는데, scanf가 4바이트를 쓰려고 하니, 넘치는 2바이트 부분이 변수 영역이 아니면, 에러가 나는겁니다.


    6년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.