인생에 후회 따윈 없다.

2015년 12월 2일 수요일

알고리즘: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;
}

2012년 8월 21일 화요일

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

2012년 2월 17일 금요일

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()));

2012년 2월 14일 화요일

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 !.

2011년 11월 7일 월요일

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

2011년 11월 4일 금요일

source insight in linux

How to use source insight in linux??

OS : ubuntu 11.04

download source insight
http://sourceinsight.com

trial 30 days or something :)

apt-get install wine
or
install using synaptics

chmod +x sourceinsight.exe

right click on incon of sourceinsight.exe

run on wine !!

how to add file
z: is root directory (/)

enjoy source insight on Linux~~~~

2011년 9월 28일 수요일

동성동본 혼인 신고

검색에 속지 말고 한방에 가는 동성동본 혼인신고 ^^

동성동본에서 의미있는 관계는 부계 모계 즉 어머니 아버지 쪽으로 8촌이내를 말한다.

와이프와 어머니가 동성동본이기 때문에 혼인 신고 전 열심히 구글링을 하였는데

어디 속시원하게 설명한 곳이 없었음.

신빙성 있어보이는 사이트에서 얻은 결과는 혼인신고와 부부가 8촌에 속하지 않는다는 확인서를 제출해야 한다였다.

두 서류를 들고 와이프와 구청에 가서 신고 하려 하니 담당자가 확인서에 대한 언급조차 없더라는 ㅎㅎ.. 낚였음..-> (http://root.or.kr/root/d11.htm)

혼인신고 양식에 보면 아래 동성동본에 8촌이내이냐? 라는 질문이 있는데 단순히 아님이라고 하면 모든 절차가 끝난다.

괜히 이상한테 낚이지 말고 혼인신고 양식만 출력해서 아는 것만 채우고 증인 2명 정보 적은 후

신분증 들고 와이프와 구청으로 갑시다 ~~

시청, 동사무소 머 이런데 안됩니다. ~~

혼인신고 절차 전자정부 안내, 신청서를 누르면 양식 다운됨
http://www.egov.go.kr/main?a=AA020InfoCappViewApp&HighCtgCD=A01004&CappBizCD=12700000050