ㅇㅇ
gogyzzz@gmail.com
2018년 4월 19일 목요일
Queue를 이용한 일관된 framework로 쉬운 BFS(Breadth First Search)문제를 풀어보자
이번학기 수강중인 멀티미디어 프로그래밍 수업에서 BFS 유형의 문제를 이것저것 풀고 있습니다. 교수님께서 queue를 사용하면 된다고 하셔서 queue를 썼더니 놀랍게도 모든 문제가 쉽게 풀려서, 내친김에 대부분의 BFS 문제를 전부 일관된 Framework로 해결할 수 있도록 정리를 해두려 합니다. (컴공과 학생들에게는 너무나도 당연한 건데, 늦게라도 이런걸 알아서 다행입니다) 아래 두 문제에 대해 적용해보았습니다. [화염에서 탈출](http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1839&sca=3040) [저글링 감염](http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=362&sca=3040) ```cpp 1. 입력 파싱 -> 변수 초기화 (변수: 배열 또는 그래프 형태의 지도, 위치정보를 가지는 instance) 2. queue 초기화 (맨 처음 출발해야 하는 worker들을 queue에 넣어줍니다) 3. while(!queue.empty()) { 4. worker = queue.front(); queue.pop(); n. 프로세스 #1 with worker n+1. 프로세스 #2 with worker ... } -2. 성공 여부 확인 -1. 출력 ``` '화염에서 탈출'문제에서 실제로 사용한 코드입니다. ```cpp #include
#include
#include
#include
struct Object { int x,y; int id; // also time it takes Object(int x=0, int y=0, int id=0):x(x),y(y),id(id){} }; void initialize_objects(int (&forest)[50][50], Object& man, std::vector
& fires, Object& home); void initialize_queue(std::queue
& obj_queue, Object& man, std::vector
& fires); void process_fire(int (&forest)[50][50], std::queue
& obj_queue, Object& fire, int (&move)[4][2]); void process_man(int (&forest)[50][50], std::queue
& obj_queue, Object& man, int (&move)[4][2]); void check_success(int& is_success, int (&forest)[50][50], Object& home); // tools bool is_valid(Object& obj, int (&forest)[50][50]); int main(void) { int forest[50][50] = {-99}; std::queue
obj_queue; Object man, home; std::vector
fires; int move[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; initialize_objects(forest, man, fires, home); initialize_queue(obj_queue, man, fires); while(!obj_queue.empty()) { Object obj = obj_queue.front(); obj_queue.pop(); //std::cout << "id: " << obj.id << std::endl; //std::cout << obj.y << " " << obj.x << std::endl; if (obj.id == -2) process_fire(forest, obj_queue, obj, move); else process_man(forest, obj_queue, obj, move); } // int is_success = forest[home.y][home.x]; if(is_success == -3) std::cout << "impossible" << std::endl; else std::cout << is_success << std::endl; return 0; } void initialize_objects(int (&forest)[50][50], Object& man, std::vector
& fires, Object& home) { int R,C; std::cin >> R >> C; std::string buffer; for (int irow=0; irow < R; irow++) { std::cin >> buffer; for (int icol=0; icol < C; icol++) { if(buffer[icol] == 'S') // man { forest[irow][icol] = 0; man = Object(icol,irow,0); } else if(buffer[icol] == '*') // fire { forest[irow][icol] = -2; fires.push_back(Object(icol,irow,-2)); } else if(buffer[icol] == 'X') // stone { forest[irow][icol] = -2; } else if(buffer[icol] == 'D') // home { forest[irow][icol] = -3; home = Object(icol,irow,0); } else if(buffer[icol] == '.') // grass { forest[irow][icol] = -1; } else { std::cout << "Error in setting forest" << std::endl; } } } } void initialize_queue(std::queue
& obj_queue, Object& man, std::vector
& fires) { // care order! (fire , man) (O) (man, fire) (X) for (int i=0; i < fires.size(); i++) obj_queue.push(fires[i]); obj_queue.push(man); } void process_fire(int (&forest)[50][50], std::queue
& obj_queue, Object& fire, int (&move)[4][2]) { for (int i = 0; i < 4; i++) { Object cfire(fire.x + move[i][0], fire.y + move[i][1], -2); if (cfire.x >= 0 && cfire.y >= 0 && forest[cfire.y][cfire.x] == -1) { forest[cfire.y][cfire.x] = cfire.id; obj_queue.push(cfire); } } } void process_man(int (&forest)[50][50], std::queue
& obj_queue, Object& man, int (&move)[4][2]) { for (int i = 0; i < 4; i++) { Object cman(man.x + move[i][0], man.y + move[i][1], man.id+1); if (cman.x >= 0 && cman.y >= 0 && (forest[cman.y][cman.x] == -1 || forest[cman.y][cman.x] == -3)) { forest[cman.y][cman.x] = cman.id; obj_queue.push(cman); } } } ```
2018년 4월 9일 월요일
Pytorch에서 Batch Normalization을 알아보자
참고
batch normalization
http://pytorch.org/docs/master/nn.html?highlight=nn%20sigmoid#normalization-layers
batch normalization 예제
https://discuss.pytorch.org/t/example-on-how-to-use-batch-norm/216
fully connected network에서 batch normalization을 수행하는 예제
https://stackoverflow.com/questions/47197885/how-to-do-fully-connected-batch-norm-in-pytorch
2018년 4월 8일 일요일
Batch Normalization을 알아보자
논문
https://arxiv.org/pdf/1502.03167.pdf
한국어 설명
https://shuuki4.wordpress.com/2016/01/13/batch-normalization-%EC%84%A4%EB%AA%85-%EB%B0%8F-%EA%B5%AC%ED%98%84/
http://blog.naver.com/PostView.nhn?blogId=laonple&logNo=220808903260&parentCategoryNo=&categoryNo=21&viewDate=&isShowPopularPosts=true&from=search
최근 게시물
이전 게시물
홈
피드 구독하기:
글 (Atom)