알고리즘:bfs 색칠하기

알고리즘:bfs 색칠하기

0으로 둘러 쌓인 1로 이루어진 곳에 다른 숫자 채우기

bfs3.txt

7
0 1 1 0 1 0 0
0 1 1 0 1 0 1
1 1 1 0 1 0 1
0 0 0 0 1 1 1
0 1 0 0 0 0 0
0 1 1 1 1 1 0
0 1 1 1 0 0 0

------------------------------------------------

#include <stdio.h>

typedef struct _path{
    int x;
    int y;
    int length;
} Path;

Path que[100];

int n;
int map[100][100];
int front = 0;
int rear = 0;
int count = 1;
int ans = 100;
void enque(int x, int y, int c){
    que[rear].x = x;
    que[rear].y = y;
    que[rear].length = c +1;
    rear ++;

    map[y][x] = c;

}
void bfs3(int x, int y, int c){
        map[y][x] = c;

        que[rear].x = x;
        que[rear].y = y;
        que[rear].length = count;

        rear++;
        Path path;
        while(front < rear){
            path  = que[front++];

            if (path.y -1 >= 0 && map[path.y -1][path.x] == 1){
                enque(path.x, path.y -1, c);
            }
            if (path.y +1 < n && map[path.y +1][path.x] == 1){
                enque(path.x, path.y+1, c);
            }
            //left
            if (path.x-1 >= 0 && map[path.y][path.x-1] == 1){
                enque(path.x-1, path.y,c);
            }
            //right
            if (path.x+1 < n  && map[path.y ][path.x+1] == 1){
                enque(path.x+1, path.y, c);
            }
        }
}

void printmap(){
    printf("-------------------------------\n");
     for(int i =0 ; i < n; i++){
        for(int j = 0 ; j < n ; j++){
                printf("%d", map[i][j]);
        }
        printf("\n");
    }
}
int main()
{
    int start;
    int v1, v2;


    freopen("bfs3.txt","r",stdin);

    scanf("%d", &n);


    for(int i =0 ; i < n; i++){
        for(int j = 0 ; j < n ; j++){
                scanf("%d", &map[i][j]);
        }
    }

    printmap();

    int color = 2;
    for (int i = 0; i < n ; i ++){
        for(int j = 0; j < n ; j++){
            if(map[i][j] == 1){
                bfs3(j,i, color++);
            }
        }
    }

    printf("answer %d\n", color-2);
    printmap();

    return 0;
}

알고리즘:bfs 길찾기

알고리즘:bfs 길찾기

bfs2.txt

6
1 1 1 1 1 1
0 0 1 0 0 1
1 1 1 0 1 1
1 0 0 0 1 0
1 1 1 0 1 0
0 0 1 1 1 1

---------------------------------------------------
#include <stdio.h>

typedef struct _path{
    int x;
    int y;
    int length;
} Path;

Path que[100];

int n;
int map[100][100];
int front = 0;
int rear = 0;
int count = 1;
int ans = 100;
void enque(int x, int y, int len){
    que[rear].x = x;
    que[rear].y = y;
    que[rear].length = len +1;
    rear ++;

    map[y][x] = 0;

}
void bfs2(int x, int y){
    //map에 방문 표시
    //que에 넣기
    enque(x,y, 0);

    // if que != empty 까지 loop
    while(front < rear){
        //que에서 하나 꺼내기
        Path path  = que[front++];

        // end에 도착 했으면 break;
        //ans update
        if(path.x == n-1 && path.y == n-1){
            ans = path.length;
            break;
        }

        //up
        if (path.y -1 >= 0 && map[path.y -1][path.x] == 1){
            enque(path.x, path.y -1, path.length);
        }
        //down
        if (path.y +1 < n && map[path.y +1][path.x] == 1){
            enque(path.x, path.y+1, path.length);
        }
        //left
        if (path.x-1 >= 0 && map[path.y][path.x-1] == 1){
            enque(path.x-1, path.y, path.length);
        }
        //right
        if (path.x+1 < n  && map[path.y ][path.x+1] == 1){
            enque(path.x+1, path.y, path.length);
        }
    }
    printf("ans = %d \n", ans);
}
void printmap(){
    printf("-------------------------------\n");
     for(int i =0 ; i < n; i++){
        for(int j = 0 ; j < n ; j++){
                printf("%d", map[i][j]);
        }
        printf("\n");
    }
}

int main()
{
    int start;
    int v1, v2;


    freopen("bfs2.txt","r",stdin);

    scanf("%d", &n);


    for(int i =0 ; i < n; i++){
        for(int j = 0 ; j < n ; j++){
                scanf("%d", &map[i][j]);
        }
    }

    printmap();
    bfs2(0,0);

    return 0;
}

알고리즘:BFS node 순회 하기

BFS node 순회 하기

bfs.txt

6 9
1 2 1 3 2 4 2 5 3 4 3 6 4 5 4 6 5 6

----------------------------------------------

#include <stdio.h>

int n;
int link;
int que[30];
int visit[30];
int map[30][30];
int front = 0;
int rear = 0;

void bfs(int v){
    // visit 표시
    visit[v] = 1;
    //que에 v 삽입
    que[rear++] = v;
    // que가 빌때까지
    while(front < rear){
            // v 값에 연결된 값 검색
        int node = que[front++];
        // node와 연결된 v를 찾는다.
        for(int i = 0; i <= n; i ++ ){
                // 연결 되어 있고 방문하지 않았다면
            if(map[node][i] == 1 && visit[i] == 0 ){
                // 방문표시 하고 que에 넣는다.
                visit[i] = 1;
                que[rear++] = i;
                printf("%d -> %d \n", node, i);
            }
        }
    }
}


int main()
{
    int start;
    int v1, v2;


    freopen("bfs.txt","r",stdin);

    scanf("%d%d", &n, &link);


    for(int i =0 ; i < link; i++){
        scanf("%d%d", &v1, &v2);

        map[v1][v2] = map[v2][v1] = 1;
    }

    bfs(1);

    return 0;
}

Regular expression

The regular expression is very useful, however, it makes me have a headache.

Below sites are useful to verify or study the reg exp.

http://gskinner.com/RegExr/

http://www.gethifi.com/tools/regex

llvm Kaleidoscope ch3

I have been studying llvm in following http://llvm.org/docs/tutorial/LangImpl3.html.

In compiling example on ch3, i met below errors.


ch3.cpp:401:18: error: no matching member function for call to 'CreateCall'
  return Builder.CreateCall(CalleeF, ArgsV, "calltmp");

ch3.cpp:406:22: error: no matching constructor for initialization of

      'std::vector<Type *>'

  std::vector<Type*> Doubles(Args.size(),Type::getDoubleTy(getGlobalContext()));

                     ^       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

solution

--------------------------------------------------------

 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp"); 

 std::vector<const Type *> Doubles(Args.size(), Type::getDoubleTy(getGlobalContext()));

llvm-gcc: invalid bitcode signature

ubuntu 11.10

llvm and llvm-gcc have been installed by ubuntu package ( apt-get install llvm llvm-gcc ). 

llvm-2.8 or llvm-2.9 and llvm-gcc-4.5 were tested.

llvm-gcc hello.c -> ok.

llvm -gcc -O3 -emit-llvm hello.c -c -o hello.b-> ok

but

lli hello.bc -> error : invalid bitcode signature 

In googling, I found below, but it was not useful.

https://bugs.launchpad.net/ubuntu/+source/dragonegg/+bug/712199

There are two solution.

1. build all of things on your PC not packages, llvm and llvm-gcc. 

2. using llvm-clang , I chosen this option. 

apt-get insatll llvm-clang

llvm-clang ........ -> it's still ok !.

Flash-Aware RAID Techniques

Flash-Aware Raid Techniques for Dependable and High-Performance Flash Memory SSD


IEEE Transactions on Computers, page 80~92, 2011
Soojun Im : Sungkyunkwan Univ.
Dongkun Shin : Sungkyunkwan Univ.


Conclusion

•Efficient RAID techniques for reliable flash memory SSDs

–The delayed parity update technique

•Reduces the number of flash memory write operations

–The partial parity caching technique

•Exploits the implicit redundant data of flash memory

•Reduce the number of read operations required to calculate the parity

•Reduce GC overheads in flash memory