2018년 가을 5학기 수강신청을 했습니다. 시간표는 아래와 같습니다.



"이게 대체 뭘까" 하는 시간표라는걸 잘 압니다. 하지만 이렇게 신청한 데에는 몇가지 이유가 있습니다.


첫째로, 전산과 과목에서 살짝 손을 때고 싶어진 느낌입니다. 그 이유는 여러가지가 있는데, 경영학을 복수전공 하기로 결정했으면, 병역을 하러 가기 전에 경영학 과목들을 몇개 들어야 하는게 아닐까 하고 생각했기도 하고, 전산과 과목을 계속 잡는게 너무 지루했다는 점 도 있으며, 분산처리 관련 알고리즘 후기에 비트코인이라는 말이 써있었기도 했기 때문입니다. 어쨌든 여러가지 이유로, 전산과 과목들을 전부 다 뺐습니다.


둘째로, 해석학II와 조합적 위상수학이 있는데, 이건 해석학이란 분야에 대한 감각을 다시 살려보고 싶었습니다. 해석학 I과 위상수학 사이, 그리고 위상수학 너머를 좀 더 배워보고 싶었습니다.


셋째로, 일본어 회화는 듣다가 휴학을 해서 다시 신청 해 놓은 것 입니다... 아마 어느정도 공부를 하고 학점인정 시험을 볼 수도 있겠네요.


넷째로, 결론이 5전공인 이유는 이번에 빡빡하게 수업을 듣고 싶었기 때문입니다. 높은 학점과 공부를 열심히 하는 것에 대한 갈망이 없었는데 최근에 너무 막 사는게 아닌가 하는 생각이 들었습니다... 그래서 다시 공부를 열심히 하는것으로 노력해 보기로 했습니다. 물론 그러다가 1학기 때 처럼 번아웃이 올 수도 있지만 그때는 24학점이었으니 좀 더 얘기가 다르겠지요. 2018년 겨울에 회사로 떠나기 전에, 공부라는 적성에 대해 조금 다시 생각 해보려고도 생각합니다.


그래서 위와같은 시간표가 나왔습니다. 참 뭔지 모를 시간표이지만, 그래도 해 보려고 합니다. 이번에는 자기 자신을 좀 더 구슬려 보려고 합니다.


'생각들' 카테고리의 다른 글

동아리 하제  (0) 2018.08.27
교수님과 상담을 하고 왔습니다  (1) 2018.07.11
2018년 가을 5학기 수강신청  (0) 2018.07.09
자기비하에 내가 느낀 점에 대해  (2) 2017.12.16
기말고사 안 갔다.  (0) 2017.12.12
자취에 대해서  (0) 2017.11.22

최근에 블로그에 포스팅을 잘 하지 않았네요. 휴학하고 아예 머릿속에서 지워버린 것 같네요.


저만의 Online Judge를 만들고 싶다는 생각이 생겨서, HYEA Online Judge를 개발했습니다. 주소는 다음과 같습니다.: http://cms2.kyouko.moe:5000/

지금은 베타 버전이고, 다양한 버그들이나 race condition들이 존재할 수 있으며 계속 수정중입니다. 오류가 있거나 오동작 한다고 생각하면 알려주시기 바랍니다.

또한 문제들이 예전 블로그에 포스팅한, 교육용 문제 모음에 있는 문제들이기 때문에, 채점을 원하시면 저한테 메일을 (사이트에 나와있음), 사용하고 싶은 아이디와 함께 보내주시기 바랍니다. 단체로 프로그래밍 사이트를 사용해도 괜찮습니다.

덧글은 제가 확인을 잘 못하지만, 만약에 확인한다면 만들어 드리도록 하겠습니다.




일단 프로그램은 sandbox등을 담고있는 Frontend와, 문제의 Description이나 회원관리등을 담고 있는 Backend로 구분하였습니다.

사용한 OS, 프로그램, 라이브러리등은 다음과 같습니다.


- libsandbox (https://github.com/openjudge/sandbox)

- python3 (https://www.python.org/)

- flask (http://flask.pocoo.org/)

- flask-restful (https://flask-restful.readthedocs.io/en/latest/)

- mariadb (https://mariadb.com/)




Sandbox는 기본적으로 libsandbox를 사용했고, ptrace를 이용해서 시스템콜이 있을 때 마다 가로채서 올바른지 확인하는 방법을 사용했습니다. 이러면 퍼포먼스 저하가 있기 때문에 다른 방법을 사용할까 하고 고민중입니다.

하드디스크의 I/O로 인한 병목을 없애기 위해서, 모두다 메모리에 가져와서 memfd로 메모리 공간 위에 파일 디스크립터를 만드는 방법을 사용했습니다. 하드디스크의 상태와 관계 없이 꽤나 안정적인 테스팅 환경을 가집니다. 디테일이 궁금하신 분이 있다면 저한테 메일을 주시거나 아니면, 제가 언젠가 이런것들을 전부다 정리할 수 있는 여유가 될 때 까지 기다려 주시기 바랍니다.


프론트엔드는 사실 별 게 없습니다... 그냥 빡구현을 했습니다.




뭐 결론적으로 제가 만들고 싶은 Online Judge를 만들었고, 많은 사람이 써줬으면 좋겠다는 바람을 가지고 있습니다. 코딩 테스트 준비를 하든, 개인적으로 PS를 배우든, 알고리즘 커뮤니티에 기여할 수 있는 것은 언제든지 좋은 일이라고 생각하니까요.


General Maximum Matching Algorithm에 대해 삽질을 많이 했고, 다른 사람이 삽질을 하지 않기 위해서 이 글을 쓰려고 합니다.


이 글은 매칭에 대해 잘 이해를 하고 있다고 가정하고, 이분그래프의 매칭을 찾는 법을 아는 사람을 위한 글입니다.



이분그래프에 대해서는 O(EV^0.5) 풀이가 존재하고, 시간복잡도 증명이 어렵지만 그 부분을 제외하고는 이해할 만 합니다. 


사실 일반그래프에 대해서도 마찬가지가 존재하나, 구현하기가 굉장히 어렵습니다. 그래서 O(V^3) 시간 알고리즘을 소개하려고 합니다.




먼저 General Graph의 Matching에 어려움의 대해 설명을 하겠습니다.


odd는 정점에서 간선을 홀수 번 타고 갈 수 있는 점, even은 정점에서 간선을 짝수번 타고 갈 수 있는 점이라고 말하겠습니다.




Graph 에서 Augment Path를 찾을 때, 이분그래프는 2가지 색으로 잘 칠해질 수 있기 때문에(odd, even) odd 정점이 비어있는지 아닌지만 확인하면 됩니다.


하지만 General graph에서는 어떤 정점이 odd이면서 동시에 even일 수 있기 때문에, 잘 처리를 해야 하고 처리를 한다고 해도 역추적이 어렵습니다.


우리는 이 Augment Odd cycle을 Blossom이라고 부르겠습니다.



이 cycle에는 특징이 하나 있습니다. 모든 Cycle위에 있는 점은 even입니다. 방향에 따라서 case가 2개가 나뉘게 되는데, 두 케이스 모두 blossom 위를 한 방향이나 반대방향으로 돌면서 Augment Path를 만들게 됩니다.



그래서 우리는, 이 blossom 위에 있는 점을 모두 even이라고 표시 해 줄것입니다. 이렇게 되면, augmenting path를 탐색하지 못하는 일이 없고 이것은 Edmond의 논문에서 증명이 되어 있습니다. 그러면 역추적을 할 때 굉장히 힘들것입니다. 우리는 이 역추적을 하는 방법을, blossom을 줄이지 않고 두개로 확장하는 방법을 사용할 것 입니다.


그림을 보면 10 - 3 - 4 - 6 - 5 의 blossom 이, 10 - 3 - 4 - 6 - 5와 10 - 5 - 6 - 4 - 3으로 나뉘어져 있다는 것을 확인할 수 있습니다. 우리는 탐색을 even인 점에서만 시작하기 때문에 (odd인 점은 단지 matching을 타고 가는것으로 끝납니다.) 탐색을 중복해서 하는일은 없게 되고, 10 - 3 - 4 - 6 - 5 가 모두 10에서 시작하는 blossom에 속해있다. 라는 사실을 저장해 두면, 다른 blossom이 생겼을 때 합치는 일도 어렵지 않습니다.



제가 과제로 작성했던 pdf 하나를 첨부하고 글을 마치도록 하겠습니다. 소스코드는 제가 첨부한 pdf안에 존재합니다.


201805.pdf





참고 문헌:

Maximales matching in Graphen [Pape & Conradt 1980]


Data Structures and Network Algorithms [Tarjan 1987]


추가:


이 방식의 시간복잡도가 O(V^3)이지만, 대부분의 경우에 O(VE)정도로 도는것 같습니다. 증명 혹은 반증은 하지 못했는데 나중에 O(VE^0.5) 알고리즘에 대해 공부하면서 써보려고 합니다. 


추가 2: 트리를 나누어서 방문한 모든 odd, even 정점을 기억하는게 아니라 아니라, 그냥 even인 점을 타고가기만 하는 경우에는 반례가 있습니다.



+ Recent posts