RevoLutioNist, RevomAN ::

거품 정렬(Bubble Sort)

Programming/알고리즘 / 2010/04/15 08:10

거품 정렬은 인접한 배열의 요소를 비교 교환하여 전체적으로 정렬을 해나가면서, 최대값을 배열의 제일뒤고 보내는 것을 반복한다.

* 안정성 : 있음
* 성능 : O(N^2)

Posted by revoman

TAG 알고리즘

트랙백 0, | 댓글 0

Google code jam - Qualification Round 2009 - C. Welcome to Code Jam

Programming/알고리즘 / 2010/04/12 17:50

Problem

So you've registered. We sent you a welcoming email, to welcome you to code jam. But it's possible that you still don't feel welcomed to code jam. That's why we decided to name a problem "welcome to code jam." After solving this problem, we hope that you'll feel very welcome. Very welcome, that is, to code jam.

If you read the previous paragraph, you're probably wondering why it's there. But if you read it very carefully, you might notice that we have written the words "welcome to code jam" several times: 400263727 times in total. After all, it's easy to look through the paragraph and find a 'w'; then find an 'e' later in the paragraph; then find an 'l' after that, and so on. Your task is to write a program that can take any text and print out how many times that text contains the phrase "welcome to code jam".

To be more precise, given a text string, you are to determine how many times the string "welcome to code jam" appears as a sub-sequence of that string. In other words, find a sequence s of increasing indices into the input string such that the concatenation of input[s[0]], input[s[1]], ..., input[s[18]] is the string "welcome to code jam".

The result of your calculation might be huge, so for convenience we would only like you to find the last 4 digits.

Input

The first line of input gives the number of test cases, N. The next N lines of input contain one test case each. Each test case is a single line of text, containing only lower-case letters and spaces. No line will start with a space, and no line will end with a space.

Output

For each test case, "Case #x: dddd", where x is the case number, and dddd is the last four digits of the answer. If the answer has fewer than 4 digits, please add zeroes at the front of your answer to make it exactly 4 digits long.

Limits

1 ≤ N ≤ 100

Small dataset

Each line will be no longer than 30 characters.

Large dataset

Each line will be no longer than 500 characters.

Sample

Input	Output
`3 elcomew elcome to code jam wweellccoommee to code qps jam welcome to codejam`	`Case #1: 0001 Case #2: 0256 Case #3: 0000`

[문제설명]
주어진 Input 문자열에서 'welcome to code jam' 문자열이 존재하는 횟수를 구하는 문제이다.
예를 들어서 다음 문자열은 N 개의 경우의 수를 가진다.

문제 : wellcome to code jamm
답    : wel come to code jam
       : we lcome to code jam
       : wel come to code ja m
       : we lcome to code ja m

[조건]
검색할 문자열의 개수는 100개 이하이다.
경우의 수가 10000개 이상일 경우 네자리만 출력한다. (예를 들어 15002 이면 답은 5002이다.)

[나의풀이]
문제를 푸는 방법이 크게 두가지가 있다.
첫번째는 노가다 정공법! input 문자열을 순회하면서, recurisve 하게 find 문자열과 비교해가는 방법이다.
이 방법으로 small input 의 경우에는 쉽게 문제를 풀었으나, large input 의 경우에는 시간 오바...
엄청나게 비효율적인 알고리즘임을 증명하였다.

결국 다른 사람들이 푼 답안을 확인하였고,
Dynamic Programming 기법을 사용하여, 쉽게 풀이가 가능하다는 것을 알았다. OTL

[소스코드]

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

char * str= "welcome to code jam";
int    count = 0;
char line[4096];
void find_str(int s, int l, int slen, int llen);
void find_str2(int slen, int llen);

#define MAX_LINE_LEN    512
#define MAX_STR_LEN        32
int    dp[MAX_LINE_LEN][MAX_STR_LEN];

int main(int argc, char **argv)
{
    FILE *    fp;
    int        i, N;

    size_t    len;
    size_t str_len = strlen(str);

    if(argc!=2) {
        printf("usage: %s input_file\n", argv[0]);
        exit (1);
    }

    /* build database from file*/
    if((fp = fopen(argv[1], "r")) == NULL) {
        printf("fopen() fail\n");
        exit (1);
    }

    if(fgets(line, sizeof(line), fp) == NULL) {
        printf("fgets() fail\n");
        exit (1);
    }
    if(sscanf(line, "%d", &N)!=1) {
        printf("invalid format\n");
        exit (1);
    }
#ifdef DEBUG
    printf("N=%d\n", N);
#endif

    for(i=0;i<N;i++) {
        if(fgets(line, sizeof(line), fp) == NULL) {
            printf("fgets() fail\n");
            exit (1);
        }
        count = 0;
        len = strlen(line);
        if(line[len-1]=='\n') {
            line[len-1] = '\0';
            len--;
        }
#ifdef DEBUG
        printf("line=[%d]%s\n", i+1, line);
#endif
#ifdef RECS /* recursive function */
        find_str(0, 0, str_len, len);

#else /* nonrecursive function */
        memset(dp, 0x00, sizeof(int)*MAX_STR_LEN*MAX_LINE_LEN);
        find_str2(str_len, len);
#endif

        /* print result */
        printf("Case #%d: %04d\n", i+1, count);
    }

    fclose(fp);
    return 0;
}

void find_str(int s, int l, int slen, int llen)
{
    int m;

    for(m=l;m<llen;m++) {
        if(str[s]==line[m]) {
            if(s+1==slen) {
                count++;
                count %= 10000;
            }
            find_str(s+1, m+1, slen, llen);
        }
    }
    return;
}

void find_str2(int slen, int llen)
{
    int m, n;

    for(m=0;m<llen;m++) {
        for(n=0;n<slen;n++) {
            if(m>0) {
                dp[m][n] = dp[m-1][n];
            }
            if(str[n]==line[m]) {
                if(n==0) {
                    dp[m][n]++;
                }
                else if(n>0 && m>0) {
                    dp[m][n] += dp[m-1][n-1];
                }
            }
            dp[m][n] %= 10000;
        }
    }
    count = dp[llen-1][slen-1];
}

Posted by revoman

TAG 알고리즘

트랙백 0, | 댓글 0

Google code jam - Qualification Round 2009 - B. Watersheds

Programming/알고리즘 / 2010/04/12 17:14

원문 : http://code.google.com/codejam/contest/dashboard?c=90101#s=p1

Problem

Geologists sometimes divide an area of land into different regions based on where rainfall flows down to. These regions are called drainage basins.

Given an elevation map (a 2-dimensional array of altitudes), label the map such that locations in the same drainage basin have the same label, subject to the following rules.

From each cell, water flows down to at most one of its 4 neighboring cells.
For each cell, if none of its 4 neighboring cells has a lower altitude than the current cell's, then the water does not flow, and the current cell is called a sink.
Otherwise, water flows from the current cell to the neighbor with the lowest altitude.
In case of a tie, water will choose the first direction with the lowest altitude from this list: North, West, East, South.

Every cell that drains directly or indirectly to the same sink is part of the same drainage basin. Each basin is labeled by a unique lower-case letter, in such a way that, when the rows of the map are concatenated from top to bottom, the resulting string is lexicographically smallest. (In particular, the basin of the most North-Western cell is always labeled 'a'.)

Input

The first line of the input file will contain the number of maps, T. T maps will follow, each starting with two integers on a line -- H and W -- the height and width of the map, in cells. The next H lines will each contain a row of the map, from north to south, each containing W integers, from west to east, specifying the altitudes of the cells.

Output

For each test case, output 1+H lines. The first line must be of the form

Case #X:

where X is the test case number, starting from 1. The next H lines must list the basin labels for each of the cells, in the same order as they appear in the input.

Limits

T ≤ 100;

Small dataset

1 ≤ H, W ≤ 10;
0 ≤ altitudes < 10.
There will be at most two basins.

Large dataset

1 ≤ H, W ≤ 100;
0 ≤ altitudes < 10,000.
There will be at most 26 basins.

Sample

Input	Output
`5 3 3 9 6 3 5 9 6 3 5 9 1 10 0 1 2 3 4 5 6 7 8 7 2 3 7 6 7 7 6 7 5 5 1 2 3 4 5 2 9 3 9 6 3 3 0 8 7 4 9 8 9 8 5 6 7 8 9 2 13 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8`	`Case #1: a b b a a b a a a Case #2: a a a a a a a a a b Case #3: a a a b b b Case #4: a a a a a a a b b a a b b b a a b b b a a a a a a Case #5: a b c d e f g h i j k l m n o p q r s t u v w x y z`

Notes

In Case #1, the upper-right and lower-left corners are sinks. Water from the diagonal flows towards the lower-left because of the lower altitude (5 versus 6).

[문제설명]
일종의 길찾기 게임이다.
메트릭스 형태의 지형이 있을 때, 물이 흐르는 경로를 같은 문자로 채운다.
물은 높은곳에서 낮은 곳으로 흐르며, 더이상 흘러가지 못하는 곳을 웅덩이라고 지칭한다.

[조건]
[0][0] 위치는 항상 'a'이다.
물은 동서남북으로 흐르며, 인접한 곳의 높이 같을 경우, 북,서,동,남 우선 순위를 따른다.

[나의풀이]
배열의 각각의 원소는 마지막까지 가는 웅덩이까지 search를 수행한다.
위 행위를 배열의 끝까지 반복한다.

[소스코드]

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

#define GO_STOP     0
#define GO_NORTH    1
#define GO_WEST     2
#define GO_EAST     3
#define GO_SOUTH    4

int     **alt;
char    **res;
char    ch;
int where_am_i_go(int cent, int north, int west, int east, int south);
void print_result(int idx, int H, int W);
char go_my_way(int m, int n, int H, int W);

int main(int argc, char **argv)
{
    FILE * fp;
    char    line[4096] = {0};
    int     i, m, n;
    int     T, H, W;

    if(argc!=2) {
        printf("usage: %s input_file\n", argv[0]);
        exit (1);
    }

    /* build database from file*/
    if((fp = fopen(argv[1], "r")) == NULL) {
        printf("fopen() fail\n");
        exit (1);
    }

    if(fgets(line, sizeof(line), fp) == NULL) {
        printf("fgets() fail\n");
        exit (1);
    }
    if(sscanf(line, "%d", &T)!=1) {
        printf("invalid format\n");
        exit (1);
    }
#ifdef DEBUG
    printf("T=%d\n", T);
#endif

    for(i=0;i<T;i++) {
        if(fgets(line, sizeof(line), fp) == NULL) {
            printf("fgets() fail\n");
            exit (1);
        }

        if(sscanf(line, "%d %d", &H, &W)!=2) {
            printf("invalid format\n");
            exit (1);
        }
#ifdef DEBUG
        printf("[%d] H=%d, W=%d\n", i, H, W);
#endif
        /* memory alloc and init */
        alt = calloc(H, sizeof(int *));
        if(alt==NULL) {
            printf("calloc() fail\n");
            exit (1);
        }
        res = calloc(H, sizeof(char *));
        if(res==NULL) {
            printf("calloc() fail\n");
            exit (1);
        }
        for(m=0;m<H;m++) {
            alt[m] = calloc(W, sizeof(int));
            if(alt[m]==NULL) {
                printf("calloc() fail\n");
                exit (1);
            }
            res[m] = calloc(W, sizeof(char));
            if(res[m]==NULL) {
                printf("calloc() fail\n");
                exit (1);
            }
        }

        /* copy data in memory */
        for(m=0;m<H;m++) {
            for(n=0;n<W;n++) {
                fscanf(fp, "%d", &alt[m][n]);
                res[m][n] = '-';
#ifdef DEBUG
                printf("%d ", alt[m][n]);
#endif
            }
#ifdef DEBUG
            printf("\n");
#endif
        }

        /* remove '\n' */
        fgets(line, sizeof(line), fp);

        /* ------- Start of core algorithm -----------*/
        ch = 'a';
        res[0][0] = ch;
        ch = go_my_way(0, 0, H, W);
        ch++;
        for(m=0;m<H;m++) {
            if(m==0 && n==0) continue;
            for(n=0;n<W;n++) {
                go_my_way(m, n, H, W);
            }
        }
        /* ------- End of core algorithm -----------*/

        /* print result */
        print_result(i+1, H, W);

        /* memory free */
        for(m=0;m<H;m++) {
            free(alt[m]);
            free(res[m]);
        }
        free(alt);
        free(res);
    }

    fclose(fp);
    return 0;
}

int where_am_i_go(int cent, int north, int west, int east, int south)
{
    int min = cent;
    int ret = GO_STOP;

    if(north >= 0 && min > north) {
        min = north;
        ret = GO_NORTH;
    }
    if(west >= 0 && min > west) {
        min = west;
        ret = GO_WEST;
    }
    if(east >= 0 && min > east) {
        min = east;
        ret = GO_EAST;
    }
    if(south >= 0 && min > south) {
        min = south;
        ret = GO_SOUTH;
    }
    return ret;
}

void print_result(int idx, int H, int W)
{
    int m, n;
    printf("Case #%d:\n", idx);
    for(m=0;m<H;m++) {
        for(n=0;n<W;n++) {
            printf("%c", res[m][n]);
            if(n+1<W) {
                printf(" ");
            }
        }
        printf("\n");
    }
}

char go_my_way(int m, int n, int H, int W)
{
    int     ret;
    int     north, west, east, south;
    int     x, y;

    /* set North */
    x = m-1;
    y = n;
    if(x < 0)   north = -1;
    else        north = alt[x][y];

    /* set West */
    x = m;
    y = n-1;
    if(y < 0)   west = -1;
    else        west = alt[x][y];

    /* set East */
    x = m;
    y = n+1;
    if(y >= W) east = -1;
    else        east = alt[x][y];

    /* set South */
    x = m+1;
    y = n;
    if(x >= H) south = -1;
    else        south = alt[x][y];

    ret = where_am_i_go(alt[m][n], north, west, east, south);
    switch(ret) {
        case GO_STOP:
            x = m;
            y = n;
            break;
        case GO_NORTH:
            x = m-1;
            y = n;
            break;
        case GO_WEST:
            x = m;
            y = n-1;
            break;
        case GO_EAST:
            x = m;
            y = n+1;
            break;
        case GO_SOUTH:
            x = m+1;
            y = n;
            break;
    }

    /* stop */
    if(ret==GO_STOP) {
        if(res[m][n]=='-') {
            res[m][n] = ch++;
        }
        return res[m][n];
    }

    /* n, w, e, s */
    else {
        int rch;
        rch = go_my_way(x, y, H, W);
        res[m][n] = rch;
        return rch;
    }
}

Posted by revoman

TAG 알고리즘

트랙백 0, | 댓글 0

Google code jam - Qualification Round 2009 - A. Alien Language

Programming/알고리즘 / 2010/04/09 09:57

원문 : http://code.google.com/codejam/contest/dashboard?c=90101#

Problem

After years of study, scientists at Google Labs have discovered an alien language transmitted from a faraway planet. The alien language is very unique in that every word consists of exactly L lowercase letters. Also, there are exactly D words in this language.

Once the dictionary of all the words in the alien language was built, the next breakthrough was to discover that the aliens have been transmitting messages to Earth for the past decade. Unfortunately, these signals are weakened due to the distance between our two planets and some of the words may be misinterpreted. In order to help them decipher these messages, the scientists have asked you to devise an algorithm that will determine the number of possible interpretations for a given pattern.

A pattern consists of exactly L tokens. Each token is either a single lowercase letter (the scientists are very sure that this is the letter) or a group of unique lowercase letters surrounded by parenthesis ( and ). For example: (ab)d(dc) means the first letter is either a or b, the second letter is definitely d and the last letter is either d or c. Therefore, the pattern (ab)d(dc) can stand for either one of these 4 possibilities: add, adc, bdd, bdc.

Input

The first line of input contains 3 integers, L, D and N separated by a space. D lines follow, each containing one word of length L. These are the words that are known to exist in the alien language. N test cases then follow, each on its own line and each consisting of a pattern as described above. You may assume that all known words provided are unique.

Output

For each test case, output

Case #X: K

where X is the test case number, starting from 1, and K indicates how many words in the alien language match the pattern.

Limits

Small dataset

1 ≤ L ≤ 10
1 ≤ D ≤ 25
1 ≤ N ≤ 10

Large dataset

1 ≤ L ≤ 15
1 ≤ D ≤ 5000
1 ≤ N ≤ 500

Sample

Input	Output
`3 5 4 abc bca dac dbc cba (ab)(bc)(ca) abc (abc)(abc)(abc) (zyx)bc`	`Case #1: 2 Case #2: 1 Case #3: 3 Case #4: 0`

[문제 설명]
자세한 설명은 생략하고 요점만 확인하자.
Sample Input 파일을 기준으로 설명하자면
3 5 4
--> 데이터의 크기를 정의하는 구문이다. 맨앞 3은 단어의 길이제한 L을 의미하고, 5는 단어의 개수 D, 4는 패턴 단어의 개수 N을 의미한다.

즉, 3은 abc, bca, dac 와 같은 하나의 단어의 길이, 5는 abc, bca, dac, abc, cba 와 같이 사전에 기록된 단어의 개수, 4는 (ab)(bc)(ca), abc, (abc)(abc)(abc), (zyx)bc 찾고자하는 패턴단어의 개수를 뜻한다.

패턴 단어 (ab)는 a 또는 b를 의미한다. Regular expression [ab]와 동일하게 생각하면 되겠다.

문제는 각각의 패턴단어가, 사전의 단어열과 일치하는 개수를 다음과 같은 형식의 Output으로 출력하면 된다.

Case #1: 2

Case #2: 1

Case #3: 3

Case #4: 0

[조건]
1. 모든 단어는 소문자 영문으로 구성된다.
2. 패턴 단어는 (, ) 문자를 포함할 수 있으며, ( 가 있을 경우, 반드시 )가 있는 것으로 단정 짓는다.

[나의 풀이]
소문자의 개수는 26개이므로, 4바이트 정수형에 비트 연산자를 사용한 고유 값을 지정할 수 있다.
즉 a = 0x01, b는 0x01<<1, c는 0x01<<2 와 같이 지정할 수 있다.

이렇게 했을 때, (ab)는 a|b와 같이 처리할 수 있고, (abc)의 경우는 a|b|c와 같이 처리할 수 있다.

해당 패턴을 사전에서 검색할 때는 pattern[i][j] & dic[m][j] 와 같이 & 연산자를 사용하여, 값이 검출되는지를 확인한다.

[소스코드]
완전한 소스코드는 다음과 같다. (Linux, gcc)

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

int main(int argc, char **argv)
{
    FILE *    fp;
    char    line[1024] = {0};
    int        L, D, N, X, K;
    int        i, j;

    int        bit = 0x01;
    int **     idb;
    int    *    ipattern;

    if(argc!=2) {
        printf("usage: %s input_file\n", argv[0]);
        exit (1);
    }

    /* build database from file*/
    if((fp = fopen(argv[1], "r")) == NULL) {
        printf("fopen() fail\n");
        exit (1);
    }

    fgets(line, sizeof(line), fp);
    if(sscanf(line, "%d %d %d", &L, &D, &N) != 3) {
        printf("invalid format\n");
        exit (1);
    }
#ifdef DEBUG
    printf("L=%d, D=%d, N=%d\n", L, D, N);
#endif
    idb = calloc(D, sizeof(int *));
    if(idb==NULL) {
        printf("calloc() fail\n");
        exit (1);
    }

    ipattern = calloc(L, sizeof(int));
    if(ipattern==NULL) {
        printf("calloc() fail\n");
        exit (1);
    }

    for(i=0;i<D;i++) {
        if(fgets(line, sizeof(line), fp) == NULL) {
            printf("fgets() fail\n");
            exit (1);
        }

        idb[i] = calloc(L, sizeof(int));
        if(idb[i]==NULL) {
            printf("calloc() fail\n");
            exit (1);
        }
        line[L] = '\0';
        for(j=0;j<L;j++) {
            idb[i][j] = bit << (line[j]-'a');
#ifdef DEBUG
            printf("[%c:%d] ", line[j], idb[i][j]);
#endif
        }
#ifdef DEBUG
        printf("\n");
#endif
    }

    for(X=0;X<N;X++) {
        int v, t;
        size_t len;
        K = 0;
        if(fgets(line, sizeof(line), fp) == NULL) {
            printf("fgets() fail\n");
            exit (1);
        }
        len = strlen(line);
        if(line[len-1] == '\n') {
            line[len-1] = '\0';
            len--;
        }

#ifdef DEBUG
        printf("pattern[%d] = %s\n", X+1, line);
#endif
        /* for each character of a word */
        j = 0;
        for(i=0;i<len;i++) {
            v = 0;
            if(line[i]=='(') {
                while(line[i+1]!=')') {
                    i++;
                    t = bit << (line[i]-'a');
                    v |= t;
                }
                i++;
            }
            else {
                v = bit << (line[i]-'a');
            }
#ifdef DEBUG
            printf("v=%d:", v);
            if(i+1==len) {
                printf("\n");
            }
#endif
            ipattern[j++] = v;
        }

        /* find in idb */
        for(i=0;i<D;i++) {
            for(j=0;j<L;j++) {
                if((ipattern[j]&idb[i][j])==0) {
                    break;
                }
            }
            if(j==L) {
                K++;
            }
        }
        printf("Case #%d: %d\n", X+1, K);
    }
    fclose(fp);

    free(ipattern);
    for(i=0;i<D;i++) {
        free(idb[i]);
    }
    free(idb);
    return 0;
}

Posted by revoman

TAG 알고리즘

트랙백 0, | 댓글 0

선택정렬 (selection sort)

Programming/알고리즘 / 2010/04/08 00:15

from~to까지 순차적으로 다음 리스트의 값과 비교한 후, 최소값을 대치해 가는 방식이다.

int selections_sort(int set[], int n)

{

int i, j;
int minv, mini;
for(i=0;i<n-1;i++) {

minv = set[i];
mini = i;

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

if(min > set[j]) {

minv = set[j];
mini = j;

}

if(mini != i) {

set[mini] = set[i]
set[i] = minv;

}

Posted by revoman

TAG 알고리즘

트랙백 0, | 댓글 0

소수 구하기

Programming/알고리즘 / 2010/04/07 23:52

소수 : 1과 자기자신 이외에는 나누어 떨어지는 정수가 없는 양의 정수

int is_prime(int n)
{

if ( n < 2) return 0;
for(i=2;i<n;i++) {

if(n%i == 0) return 0;

}
return 1;

}

Posted by revoman

TAG 알고리즘

트랙백 0, | 댓글 0

태터데스크 관리자

태터데스크 메시지

RevoLutioNist, RevomAN

카테고리

달력

공지사항

태그목록

최근에 올라온 글

'알고리즘'에 해당되는 글 6건

거품 정렬(Bubble Sort)

Trackback | http://revoman.nudecode.org/trackback/190

Google code jam - Qualification Round 2009 - C. Welcome to Code Jam

Trackback | http://revoman.nudecode.org/trackback/189

Google code jam - Qualification Round 2009 - B. Watersheds

Trackback | http://revoman.nudecode.org/trackback/188

Google code jam - Qualification Round 2009 - A. Alien Language

Trackback | http://revoman.nudecode.org/trackback/187

선택정렬 (selection sort)

Trackback | http://revoman.nudecode.org/trackback/186

소수 구하기

Trackback | http://revoman.nudecode.org/trackback/185

최근에 달린 댓글

최근에 받은 트랙백

글 보관함

링크