문제 출처 : http://www.jungol.co.kr/prog/Hanal/hanalView.php?qs_code=1889


나의 답 : 아래 코드이다.. 하지만 N = 13일경우 1초내에 계산이 안되서 accepted되었다..ㅠㅠ 속도 향상할 수 있는 point를 찾아야 겠다..


#include 
#include 
#define DEBUG 0
#define MAX_QUEENS 14

int g_cols[MAX_QUEENS]; // represent of chess board
                        // g_cols[index] : column, index : row
int g_num_queens;
int g_num_possible_sequence;

void SetInputFromFile(const char* fileName);
void PrintAnswerToFile(const char* fileName);
void NQueen(int irow);
int isThreathen(int irow);
void Print_Queen();

int main() {

    SetInputFromFile("input.txt");
    g_num_possible_sequence = 0;
    NQueen(0);
    PrintAnswerToFile("output.txt");

    return 0;
}

void SetInputFromFile(const char* fileName) {
    FILE *input = fopen(fileName, "r");
    if (input == NULL) {
        fprintf(stderr, "Can NOT open file: \n", fileName);
        goto bail;
    }

    //TODO:
    fscanf(input, "%d", &g_num_queens);
    fclose(input);
    return;
bail:
    if (input != NULL) fclose(input);
}

void PrintAnswerToFile(const char* fileName) {
    FILE *output = fopen(fileName, "w");
    if (output == NULL) {
        fprintf(stderr, "Can NOT open file: \n", fileName);
        goto bail;
    }

    //TODO:
    fprintf(output, "%d\n", g_num_possible_sequence);
    fclose(output);
    return;
bail:
    if (output != NULL) fclose(output);
}

void NQueen(int irow) {
    int icol;
    if (DEBUG) {printf("nqueen(%d)\n", irow + 1); Print_Queen();}
    if (isThreathen(irow)) {
        if (DEBUG) {printf("irow(%d) is Threathen\n", irow);Print_Queen();}
        return;
    }
    if (irow == g_num_queens) {
        if (DEBUG) {printf("completed\n");Print_Queen();}
        g_num_possible_sequence++;
        return;
    }

    for (icol = 1; icol <= g_num_queens; icol++) {
        g_cols[irow + 1] = icol;
        NQueen(irow + 1);
    }
}

int isThreathen(int irow) {
    int k; // irow 보다 작은 row를 가리키는 index
           // TODO : rename k

    for (k = 1; k < irow; k++) {
        if (g_cols[irow] == g_cols[k]
            || abs(g_cols[irow] - g_cols[k]) == (irow - k)) {
            return 1;
        }
    }

    return 0;
}

void Print_Queen() {
    int i;
    for (i = 1; i <= g_num_queens; i++) {
        printf("%d ", g_cols[i]);
    }
    printf("\n");
}


저작자 표시
신고
by danguria 2012.11.20 10:17
출처 : http://www.jungol.co.kr/prog/Hanal/hanalView.php?qs_code=2499
 2011.KOI.전국.초등부

#include 
#define DEBUG 1
#define MAX_WEIGHTS 1000

void SetInputFromFile(const char* fileName, int *num_weights, int *weights);
void PrintAnswerToFile(const char* fileName, int min_umw /*minimum unmeasurable weight*/);
int GetMinUnmeasurableWeight(const int num_weights, int *weights);
void SortWeight(int num_weights, int* weights);

int main() {

    int num_weights;
    int weights[MAX_WEIGHTS];

    SetInputFromFile("input.txt", &num_weights, weights);
    PrintAnswerToFile("output.txt", GetMinUnmeasurableWeight(num_weights, weights));

    return 0;
}

void SetInputFromFile(const char* fileName, int *num_weights, int *weights) {
    int i;
    FILE *input = fopen(fileName, "r");
    if (input == NULL) {
        fprintf(stderr, "Can NOT open file: \n", fileName);
        goto bail;
    }

    //TODO:
    fscanf(input, "%d", num_weights);
    for (i = 0; i < *num_weights; i++) {
        fscanf(input, "%d", &(weights[i]));
    }
  
    fclose(input);
    return;
bail:
    if (input != NULL) fclose(input);
}

void PrintAnswerToFile(const char* fileName, int min_umw /*minimum unmeasurable weight*/) {
    FILE *output = fopen(fileName, "w");
    if (output == NULL) {
        fprintf(stderr, "Can NOT open file: \n", fileName);
        goto bail;
    }

    fprintf(output, "%d\n", min_umw);
    fclose(output);
    return;
bail:
    if (output != NULL) fclose(output);
}

int GetMinUnmeasurableWeight(const int num_weights, int *weights) {
    int pmr; // possible_measurement_range
    int nw;  // new_weight
    int i;

    SortWeight(num_weights, weights);

    pmr = 0;
    for (i = 0; i < num_weights; i++) {
        nw = weights[i];
        if (nw - 1 > pmr) {
            return pmr + 1;
        }
        pmr += nw;
    }
    return pmr + 1;
}

void SortWeight(int num_weights, int* weights) {
    int i, j, temp;

    for (i = 0; i < num_weights; i++) {
        for (j = i + 1; j < num_weights; j++) {
            if (weights[i] > weights[j]) {
                temp = weights[i];
                weights[i] = weights[j];
                weights[j] =  temp;
            }
        }
    }
}


저작자 표시
신고
by danguria 2012.11.19 23:27

출저 : 정올 (http://www.jungol.co.kr/prog/Hanal/hanalView.php?qs_code=1370)


#include <stdio.h>

#define DEBUG  1


typedef struct {

    int requested_order;

    int start_hour;

    int end_hour;

}MEETING;


MEETING g_requested_meetings[501];

int     g_num_requested_meetings;

MEETING g_scheduled_meeting[501];


int  ScheduleMeetings();

void SortRequestedMeetings();

void PrintRequestedMeetings();


// input output

void SetInputFfromFile(char* fileName);

void PrintAnwserToFile(char* fileName, int i_last_meeting);


int main() {      

    

SetInputFfromFile("input.txt");    

PrintAnwserToFile("output.txt", ScheduleMeetings());

    

return 0;

}


void PrintRequestedMeetings() {

    int im;

    for (im = 1; im <= g_num_requested_meetings; im++){

        printf("%d %d %d\n", g_requested_meetings[im].requested_order,

                g_requested_meetings[im].start_hour,

g_requested_meetings[im].end_hour);

    }

}


// sorting by end_hour

void SortRequestedMeetings() {

    int i, j;

    MEETING temp;

int end_hour_i;

int end_hour_j;


    for (i = 1; i <= g_num_requested_meetings; i++) {

        for (j = i + 1; j <= g_num_requested_meetings; j++) {


end_hour_i = g_requested_meetings[i].end_hour;

end_hour_j = g_requested_meetings[j].end_hour;


if (end_hour_i > end_hour_j) {

                temp = g_requested_meetings[i];

                g_requested_meetings[i] = g_requested_meetings[j];

                g_requested_meetings[j] = temp;

            }

        }

    }

}



int ScheduleMeetings() {

MEETING last_meeting, new_meeting;

    int il, in;  // index of last_meeting, index of new_meeting    

    SortRequestedMeetings();


    if (DEBUG) PrintRequestedMeetings();

    il = 1;

    g_scheduled_meeting[il] = g_requested_meetings[il];


for (in = 2; in <= g_num_requested_meetings; in++) {

last_meeting = g_scheduled_meeting[il];

new_meeting  = g_requested_meetings[in];


if (DEBUG) {

printf("%d : %d\n", last_meeting.end_hour, new_meeting.end_hour);

        }


if (last_meeting.end_hour <= new_meeting.start_hour) {

g_scheduled_meeting[++il] = new_meeting;

}

}


return il;

}



void SetInputFfromFile(char* fileName) {

int i;


FILE *input = NULL;

input = fopen(fileName, "r");

if (input == NULL) {

fprintf(stderr, "file open error : %s\n", fileName);

return;

}


fscanf(input, "%d", &g_num_requested_meetings);

    for (i = 1; i <= g_num_requested_meetings; i++) {

        fscanf(input, "%d %d %d", 

&(g_requested_meetings[i].requested_order), 

&(g_requested_meetings[i].start_hour), 

&(g_requested_meetings[i].end_hour));

    }


fclose(input);

}


void PrintAnwserToFile(char* fileName, int i_last_meeting) {

int i;

FILE *output = NULL;

output = fopen("output.txt", "w");

if (output == NULL) {

fprintf(stderr, "file open error : %s\n", fileName);

return;

}


fprintf(output, "%d\n", i_last_meeting);

    for (i = 1; i <= i_last_meeting; i++) {

        fprintf(output, "%d ", (g_scheduled_meeting[i]).requested_order);

    }

    fprintf(output, "\n");


fclose(output);

}


저작자 표시
신고
by danguria 2012.11.11 16:04
자료 구조 시간에 배운 그래프중에서 오일러 회로와 해밀턴 회로가 헷갈려서 정리를 해 보았습니다.
사실 고등학생인 사촌동생이 수열과 관련지어서 그래프 문제를 질문했는데 헷갈려서 부끄러워 책좀 찾아 봤습니다.

[출처 : 천재교육 이산 수학 자습서 ] - 혹시 문제가 된다면 삭제 하도록 하겠습니다.

오일러 회로와 해밀턴 회로를 쉽게 이해 하기 위해서 신문 배달원과, 신문 배송 담당자이야기만 기억 하면 되겠습니다.

[신문 배달원이 처한 문제]
신문 배달을 시작한 철이는 며칠 동안 신문을 돌리다 보니 지나갔던 길을 또 지나가는 경우가 있는 것을 알게 되었다.
다음 그림은 배달 지역의 지도인데 모든 깅을 반드시 지나가야만 할때, 철이는 지나갔던 길을 다시 지나가지 않고 신문 배달을 잘 마칠 수 있을까?

[신문 배송 담당자]
철이가 신문 배달 하는 길을 놓고 고민하는 모습을 본 신문 배송 담당자는 철이에게 다음과 같은 말을 하였다.
"나도 새벽에 신문사에서 신문을 받아 각 지역 지국으로 배송하여야 하는데 어떻게 하면 좋을까?"
철이가 생각해보니 신문 배송 담장자의 문제는 철이의 경우와 조금 다른 것 같았다. 
왜냐하면 철이의 경우는 지나갔던 길만 지나지 않으면 되는데 신문 배송 담장자의 경우는 한 번 들린 지국에는 다시 들릴 필요가 없기 때문이다. 
이 문제를 해결하기 위해서 모든 꼭지점들을 오직 한 번만 지나면서 출발점으로 돌아오는 방법을 찾는 것이다.
신고
by danguria 2010.04.30 19:48
하스켈로 알고리즘을 구현하는 것이 좀더 큰 목적이지만, 그렇다고 알고리즘 구현에 뛰어난 것이 아니기 때문에 복습도 해볼겸해서 정렬알고리즘을 하스켈로 구현하고 각각의 특징을 정리 해보려고 합니다. 
그 1탄으로 Insertion sort, Selection sort, Merge sort, Quick sort입니다.
오늘은 어려운 코드가 아니므로 알고리즘 구현에 대한 자세한 설명은 생략하는 것이 좋을 것 같습니다.
일단 코드 부터 보겠습니다. 기존에 C와 다른 코드 이므로 좀더 신중하게 보세요.. 
하스켈을 모르셔도 읽는데는 무리가 없을 것이라고 생각합니다. (필요한부분은 설명을 하도록 하겠습니다.)

-- this function is inserttion sort
insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys)
| x < y  = x : y : ys
| otherwise = y : insert x ys 
isort :: Ord a => [a] -> [a]
isort [] = []
isort (x:xs) = insert x (isort xs)

위의 코드는 Insertion sort입니다. 보통 책에는 Iterative하게 구현했지만 함수형 언어의 특징을 살려 recursive함수로 구현했습니다. (참고로, 저도 아직 배우는 중이라서 비슷하게는 구현했지만 부족한 부분은 인터넷에 떠도는 멜버른 대학의 코드를 가져 왔습니다.)

-- this function is selection sort
myMin :: Ord a => [a] -> a
myMin [] = undefined 
myMin [x] = x 
myMin (x:xs) 
| x <= myMin(xs) = x
| otherwise = myMin(xs)
delete :: Eq a => a -> [a] -> [a]
delete x [] = []
delete x (y:ys)
| x == y = ys
| otherwise = y : (delete x ys)    
ssort :: Ord a => [a] -> [a]
ssort [] = []
ssort xs = [x] ++ ssort (delete x xs) 
where x = myMin (xs)

이번 코드는 Selection sort입니다. 개인적으로 이 코드를 구현하는게 좀더 쉬었네요...

-- this function is merge sort 
merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
| x <= y = x : (merge xs (y:ys))
| otherwise = y : (merge (x:xs) ys)
msort :: Ord a => [a] -> [a]
msort [] = []
msort [x] = [x]
msort xs = merge (msort top) (msort bottom)
where (top, bottom) = splitAt (length xs `div` 2) xs

이번 코드는 Merge sort입니다. 조심하셔야 하는 것은 종료 조건을 정확하게 기준해야 한다는 점입니다. 정렬 알고리즘을 재귀함수로 구현 하기 때문에 종료 조건이 특히 중요 합니다. 다른 언어보다 알고리즘을 표현하기 쉽기 때문에 이런 부분만 신경쓴다면 알고리즘 외의 부분에서는 오류 날일이 거의 없을 듯 합니다.

-- this function is quick sort
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort bigger
where smaller = [a | a <- xs, a <= x]
     bigger = [b | b <- xs, b > x]  

개인적으로 하스켈을 공부한지 한달 정도 되었는데, 이 코드가 가장 좋아 하는 코드 입니다. 너무너무나 Clear하죠^^(저희 학교에 어떤 교수님께서 잘 쓰시는 말을 인용했습니다.)
신고
by danguria 2010.02.27 16:05
오늘 파일처리 첫수업에서 교수님께서 갑자기 이산수학 이야기를 끄집어 내셔서 결국 파일처리가 어떤 과목인가 보다는 이산수학2 수업이 되어 버렸다. (어쩌면 오토마타2인가.. -_-;; 자료구조2?) 먼가 이 내용이 비둘기집의 원리에서부터 출발하였는데... 왜!!!!!! ;;;;;;;;;;; 당췌 모를일이다...



이번학기 첫번째 과제중의 대각선법에 대한 내용이다.


[증명] 실수의 집합은 비가산집합이다. (칸토어의 대각선법)


- 이때의 비가산집합이라는 것은 자연수의 성질 중 하나인 countable의 반대되는개념으로 비가산집합이라는 말을 쓴다. (countable은 무한 하지만 셀수있는 - 실제로 수직선상에 표현을 하자면 일정한 간격을 가지고 존재하므로 어떤 임의의 수를 선택한다면 그 수에 일정간격을 더하거나 빼었을때 그 자리에 항상 같은 집합에 속하는 수가 존재하게 된다.)
- 칸토어의 대각선법(Cantor's diagonal method)를 이용해 이것을 증명할 수 있다.
- 실수의 부분 집합인 단위 개구간 (0,1)사이의 모든 실수의 집합이 비가산임을 보여, 정체 실수의 집합 또한 비가산임을 증명한다.
(수업시간에는 폐구간 [0, 1] 사이의 모든 실수의 집합이 비가산임을 보이고 폐구간 [0, 100] 또한 비가산임을 증명하였다.)

0과 1 사이의 모든 실수의 집합이 가산이라고 가정하자. (countable)
그러면 이러한 수둘의 10진법 표현은 다음과 같은 리스트로 나타낼 수 있다.
사용자 삽입 이미지
양의 정수 쌍 i와 j에 대하여, 이 리스트에서 i번째 수의 j번째 10진수는 Aij이다. 즉 첫 번째 수의 첫 번째 10진 숫자는 A11이고, 두번째 10진수는 A22등이다. 예를 들면 0과 1 사이의 실수 리스트가 다음과 같이 시작한다고 가정하자.

사용자 삽입 이미지
대각선에 위치한 원소들을 붉은색으로 표시하였는데
이 대각선에 있는 원소들을 하나씩 보면서 각각 원래의 숫자가 아닌 다른 숫자로 된 새로운 십진수 B를 만들 수 있다. 예를 든다면 0.23712.. 이던가 0.12313.. 이런 수를 만들 수 있을 것이다. 여기에서 B=0.23712..으로 잡는다면 위의 리스트에 나와있는 수와 비교를 했을 때 반드시 n번째 리스트에 있는 실수는 소수점이하 n번째 자리에서 B와 다른 수를 가지므로 B는 리스트에 포함되지 않는 수임을 알 수 있다. 그러나 B는 역시 0과 1 사이의 수이면서 리스트에 빠져있기때문에 가산이라는 가정에 모순이 생긴다.

따라서, 0과 1 사이의 모든 실수는 비가산이다.

오토마타시간에 배운 내용은 아마 이진법으로 되어있던 n*n행렬이었던것 같은데...............? -_-;;;
기억이... 기억이..... 학교가서 다시 책을 찾아봐야겠다.. 그때는 0 또는 1로 되어 있어서 matrix의 대각선을 0은 1로 1은 0으로 바꾸어서 만든 수였나..;;
사실 대각선법 그러니깐... 그게 머야 배웠더냐 라는 생각이었는데.. 음... 다시 보니 기억이 나는군 비가산이 머지... 이런생각 한 3.4초쯤 해주고..  아하! 이래 떠올라서 다행이넵 ㅋㅋ


-> 기본 내용은 http://blog.naver.com/pupleshiner 에서 퍼온 내용입니다.


두번째 문제를 푸는데에 있어서 중요한 단서가 되는 내용이라고 하니 일단은 생각을 해둬야겠습니다. ㅋㅋㅋ 난 x와 y의 일대일대응의 관계에만 치우쳐 생각을 했지만.. 이제 대각선법을~!!!

이래봤자 머 모르겠노..ㅠ

신고
by danguria 2008.03.03 22:44

n개중에서 r개를 뽑는 경우는 nCr이라는 공식을 이용하여 풀수 있다.

nCr =  n! / r! x (n-r)! 이다

하지만 이것을 컴퓨터에게 그대로 적용시켜 계산하게 되면 오버 플로우가 일어날 수 있다.

n!의 경우 n값이 조금만 크더라도 n!값이 엄청 커진다.

이를 방지 하기 위해서 점화식을 이용해서 풀면 된다.

nCr = (n - r + 1) / r * nCr-1
nC0 = 1( r = 0일때)

이런식으로 점화식을 이용해서 풀면 오버 플로우를 막을 수 있다.

double combination( int n, int r )
{

    int i;

    double sum;

    sum = 1;

    for( int i =1; i <= r; i++ )

        sum = sum * (( n - i + 1 ) / (double) i );

   return sum;
}

신고
by danguria 2008.02.27 11:10

멤버십 알고리즘 테스트에 나온 문제다.

ACM에 나왔던 문제라는데 아직 100명정도만 풀었다는데...

지금 풀고 있는데 과연 풀어 낼까?ㅎㅎ

신고
by danguria 2008.02.23 11:38

치과에 갔다고 기다리는 동안 신문에난 문제이길래 풀다가 재밌어서.....^^;;
어린이용이었던거 같던데...나름 괜찮았다^^;;
어린이용이니까 후딱 풀어야 겠지?ㅎㅎ
<문제>
1~8까지 번호가 매겨진 구슬이 있다. 이 구슬 중 두개는 가짜 구슬이다. 가짜구슬과 진짜구슬은 각각 무게가 같다.
아래 그림은 무게를 제어 본 결과이다.

아래 그림을 보고 몇번이 가짜 구슬인지 알아맞혀 보시오. 또한 가짜구슬이 더 무거운지..
아님 진짜 구슬이 더 무거운지 알아보시오..

<해답>
일단 두번째 그림을 보면 .. 2,3,4와 5,6,7이 무게같다. 즉 모두 진짜 구슬이거나, 양쪽에 가짜 구슬이 하나씩 들어가 있다는 것을 알게 된다
모두 진짜라면, 즉 2,3,4,5,6,7이 진짜라고 가정하면 세번째 그림에 의해서 거짓이라는 것을 알 수 있다.결국 2,3,4와 5,6,7에 가짜가 각각 하나씩 들어가 있다.
다음으로....첫번째 그림은 두번째 그림에서 왼쪽에 1을 넣고 4를 오른쪽으로 옮기고 7을 뺀 모양이다.
1은 진짜이고....4와 7의 진짜 가짜여부에 의해 무게가 결정된다..4와 7이 될수 있는 경우는
(진,진)(진,가)(가,진)(가,가)인데 첫번째 그림에 의해서 (진,진)은 될 수 없다.나머지는 다 될 수 있다.(4,7중 적어도 하나는 가짜가 있다)
여기까지 해두고...다시 세번째 그림을 보자...
4,7에 적어도 하나는 가짜가 있으므로...
(가,가)이면 가짜가 무겁고
(가,진)이면 2는 무조건 진짜이고, 6번은 가짜이거나 진짜이다. 그렇지만 가짜면 무게가 같아야 하므로 6도 진짜이다
(진,가)이면 6은 무조건 진짜이고, 2번은 가짜이거나 진짜이다. 그렇지만 가짜면 무게가 같아야 하므로 2도 진짜이다.
가짜가 무게가 더 무겁고, 2,6은 진짜이다, 또한 3,5중에서 적어도 하나는 가짜인것을 알게 되었다.
이결과를 가지고 다시 첫번째 그림을 보자
4,7중에 적어도 하나는 가짜, 3,5중에 적어도 하나는 가짜이므로 모든 경우는 다음과 같다
4 - 7 - 3 - 5
가  가  진  진(1)
가  진  진  가(2)
가  진  가  진(3)
진  가  가  진(4)
진  가  진  가(5)
진  진  가  가(6)
이 경우들을 첫번째 그림과 매치 시켜 보면 결국  4번째 경우, 즉 7번과 3번 구슬이 가짜라는 것이 된다.
 
신고
by danguria 2008.01.16 20:43
| 1 |

티스토리 툴바