ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 넥슨 면접 1번문제
    개발하면서/Algorithm,DS,PS 2010. 2. 12. 11:32
    반응형

    현재 소장님이 작성하신 메모리 저장구조를 분석하고 있습니다. 일하다가 찾은 사이트에서 재미난 문제가 있어서 풀어봤습니다.(정말 일하다가? ㅋㅋㅋㅋㅋ)

    Nexon 면접문제    (좀 오래됐음;;;)

     

    뭐 genrator구하는것은 쉽게 되는데 1부터 5000까지의 숫자 중 generator인지 아닌지를 체크해주는 것이

    메모리 저장구조에 있는 것을 써먹으면 좋을 것 같아 적용을 시작했습니다....

    8bit * 625 = 5000~!! 딱 떨어지네요 문제도 이걸 원한 게 아닐까 생각합니다.

     

    generator에 해당하는 비트에 체크를 해주고 나중에 이 비트를 검사해서 selfnum여부를 판별하는 구조입니다.

     

     

    #include <stdio.h>
    #include <stdlib.h>
    const unsigned char mask[8] = {0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};
    unsigned short make_generator(int i);
    
    int main(int argc, char *argv[]){
            unsigned char bit[625];
            int i, j;
            int k = 0;
            int sum = 0;
            int root, leaf;
            unsigned short generator;
            int self_num;
            for ( i = 0; i < 625; i++ )     {
                    bit[i] = 0;
            }
    
            for ( k = 1; k < 5000; k++ )    {
                    generator = make_generator(k);
                    //printf("%d'sgenerator :%d\n", k, generator);
                    root = generator >> 3;
                    leaf = generator & 0x07;
                    bit[root] = bit[root] | mask[leaf];
            }
            for ( i = 0; i < 625; i++ )     {
                    for ( j = 0; j < 8; j++ )
                    {
                            if ( (bit[i] & mask[j]) == 0 ){
                                    self_num = (i << 3) | j;
                                    printf("self_num : %d\n", self_num);
                                    sum += self_num;
                            }
                    }
            }
            printf("sum : %d\n", sum);
            return 0;
    }
    unsigned short make_generator(int i)
    {
            int generator = 0;
            int org;
            int num;
            //org = i;
            generator += i;
            while ( i > 0 ) {
                    num = i % 10;
                    generator += num;
                    i = i / 10;
            }
            //if ( org > 9 )
            //{
            //              generator += org;
            //}
            return generator;
    }

     

    원문에 해결한 답하고 45가 차이 납니다......

    아놔....... 뭐가 잘못됐지? 라며 프린트도 하고 비교도 했는데 모르겠습니다

    지금 보니 제가 generator에 대한 이해가 부족했네요. 한자리 자연수는 그 자체가 generator수로 처리를 했다는....

     

    진행 하면서 많은 생각을 한것에 대만족 ㅋㅋㅋ

     

    보시면서 잘못된 부분이나 수정했으면 하는 부분을 알려주시면 정말 감사하겠습니다~ : )

    반응형

    댓글

Designed by Tistory.