테스트 데이터를 만들 때 즐겨 쓰는 데이터 들을 첨부합니다. 이 데이터들은 SCPC (삼성전자 대학생 프로그래밍 경진대회) 에도 활용 되었습니다.


내용이 간략하게만 쓰여져 있고, 정리 할 일이 있으면 길게 작성하도록 하겠습니다.


AntiHash.pdf

AntiSort.pdf


어떻게 될 지 모르겠습니다. 제가 성격상 애초에 동아리 회장같은게 적합하지 않았을지도 모릅니다. 오히려 System Operator 같은 포지션만 가지고 있는게 제일 맞았을지도 모르겠습니다.


내일 동아리 내부에서 얘기를 해보기로 했습니다. 거기까지. 회장인 상태에서 글을 쓰면, 물론 이건 제 생각을 쓰는 곳이지만 동아리의 의견으로 비출수도 있고 일단 좀 미뤄두려고 합니다.


개강도 했고 지치네요. 사이클을 돌리기 위해서라도 일찍 자야겠어요. 안녕히 주무세요.

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

동아리 하제  (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

홈페이지에 드디어 SSL 인증서를 달았습니다! 


https://kyouko.moe


티스토리 블로그에도 달고 싶은데 지원을 안하네요... SSL 인증서 좀 지원해주면 좋으려만


좀 더 자세한 얘기는 호스팅을 bluehost에서 linode로 옮겼습니다. 처음에 서버 세팅에 관한 지식이 없을때 php로 사이트를 뚝딱뚝딱 만든것도 있고, 가격이 월 10$라서 샀었는데, 지금은 linode하나 올려서 쓰는게 좀 더 마음이 편하네요. 가장 싼 플랜이 한 달 5$ 에요. 역시 루트권한 있으니까 마음이 편해요.

예전에는 블루호스트가 인증서 적용하는게 유료라서 못 달았는데, 지금은 letsencrypt로 인증서를 받아서 적용했습니다.


호스팅이 이것저것 난잡해지기도 해서, 아예 flask기반으로 웹을 재구성 하고 있는데 아직 옮기지 못한게 있네요.


하나는 Musicplayer인데, Youtube Red를 쓰니까 별로 쓸 일이 없어지는것 같기도 하네요.

다른건, 사람들에게 링크를 줄 때 잡다하게 파일들을 올리고 그걸 주는 방식으로 문제를 만들었는데, 이것들은 지금 살려둬야 할지 말아야 할지 모르겠는 링크도 많아서 일단은 안 살려 뒀습니다...


사실 최근에 트래픽 부담이 꽤나 있는데 linode도 한달정도 써보고 트래픽 부담이 있으면 여기만 따로 옮기는 방식을 쓰든가 여러가지 조치를 취해야 할 것 같네요.

  1. SSL 2018.07.29 09:22 신고

    클라우드 플레어를 이용하면 티스토리에도 인증서를 붙이는게 가능한걸로 알아요ㅎㅎ


과 같은 선형 점화식을에 계산 해야하는 문제가 나와서 write-up을 해봤습니다.


n번째 항까지의 모든 항을 계산하는 방법이고, 풀이가 생각보다는 깔끔합니다.


지금은 일단 간략하게 쓴 것이고, 제출을 해야 할 때 되면 아마 보강을 해서 좀 더 써서 올리지 않을 까 싶습니다.


201808.pdf



문제: https://csacademy.com/contest/round-9/task/jetpack/



Porter Robinsom & Madeon의 Shelter입니다.


가사가 마음에 들어서 계속 듣고 있습니다. 노래를 들을때 생각해보면 가사를 굉장히 중요하게 따지는것 같기도 하네요


'음악' 카테고리의 다른 글

Porter Robinson & Madeon - Shelter  (0) 2018.07.13
너의 은빛 정원 (君の銀の庭)  (0) 2018.07.10

학교의 교수님과 상담을 하고 왔습니다. 정말 좋으신 교수님인것 같아요 이야기 1시간 씩이나 들어주시고


저는 자기 자신에게 가혹하게 다룬다고 생각을 안 했는데, 제가 제 자신을 너무 가혹하게 다룬것 같기도 하네요. 좀 자기 자신에 대해서 긍정적인 평가를 할필요가 있다고도 생각합니다. 방학 때는 조금 더 쉬어야 할 것 같네요.


Problem Solving을 이제 줄여서 허무함이 다가오는게 있던것 같습니다. 그게 다른 사람은 대학 입학에서 오는것 같다던데 제가 좀 늦게 왔나 보네요... 사실 정말 많은 것들을 했어요. 이제 제가 어떤 것에 흥미가 있는지를 좀 찾아보려고 합니다. 일단 하나 확실한거는, 다른 사람을 가르치는 데에는 흥미가 있는것 같고- 이제 다른 것들을 찾아보려고 합니다.


이번학기는 아마 수학과 교수님과 조합론이나 그래프 이론에 관련하여 연구도 진행할 것 같습니다. 꽤나 좋은 경험이 될 것이라고 생각합니다.



또, 시간표를 어느정도 개조했습니다. 아마 거시경제학이나 조합위상은 듣다가 힘들어서 드랍할 수도 있을것 같은데... 어쨌든 다음 학기는 수학위주의 학기가 될 것 같습니다. 경영은 하다가 재밌으면 듣고 아니면 말고... 할 것 같네요





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

동아리 하제  (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
  1. Fan 2018.07.12 13:08 신고

    팬으로서 멀리서밖에 못 봤지만 너무 열심히 살고 있어서 항상 놀라웠어요. 혜아님도 사랑받을 가치가 충분한 사람이란걸 기억해주시면 좋겠어요.


듣고 있는 노래중에 정말 마음에 드는 노래들을 올려보려고 합니다.


극장판 마법소녀 마도카☆마기카 반역의 이야기의 엔딩으로 사용된 "너의 은의 정원" 입니다. 영화를 본 여운이 아직도 남아서 계속 듣고 있네요.



'음악' 카테고리의 다른 글

Porter Robinson & Madeon - Shelter  (0) 2018.07.13
너의 은빛 정원 (君の銀の庭)  (0) 2018.07.10

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