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


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


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


201808.pdf



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


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


저만의 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인 점을 타고가기만 하는 경우에는 반례가 있습니다.



Run@KAIST 봄 연습 3주차 문제입니다.


앞으로 문제들은 이정도 난이도로 구성될 것 같습니다.


8문제를 준비했습니다.


Week3 (ko).pdf



2주차 에디토리얼입니다.


문제의 출처는 다음과 같습니다.:


A to Z (Atcoder ABC053B: https://beta.atcoder.jp/contests/abc053/tasks/abc053_b)

직사각형 (Atcoder ARC081A: https://beta.atcoder.jp/contests/arc081/tasks/arc081_a)

음식 맛있게 먹기 (Maximum Sum Subarray 연습문제)

조상 (Dfs Ordering 연습문제)

어비스의 탐험가 (Running Median 연습문제)

도시 연결 (Minimum Spanning Tree 연습문제)

혜아의 타이핑 (Atcoder ARC059D: https://beta.atcoder.jp/contests/arc059/tasks/arc059_d)

돌 (Atcoder ARC085C: https://beta.atcoder.jp/contests/arc085/tasks/arc085_c)


Week2_Editorial.pdf



Run@KAIST 봄 연습 2주차 문제입니다.


저번 주 보다는 문제의 난이도를 올렸습니다.



역시 8문제를 준비했습니다.


Week2 (ko).pdf



P. S. 배점의 수정이 있었습니다.

1주차 에디토리얼입니다.


문제의 출처는 다음과 같습니다.:


쉬운 계산기 (Atcoder ABC050A: https://beta.atcoder.jp/contests/abc050/tasks/abc050_a)

세 수의 합 (Atcoder ABC051B: https://beta.atcoder.jp/contests/abc051/tasks/abc051_b)

팩토리얼 (Atcoder ABC052C: https://beta.atcoder.jp/contests/abc052/tasks/arc067_a)

혜아 인 어비스 (Priority Queue 연습문제)

집단 (Disjoint set 연습문제)

계산기 (계산기 구현 연습문제)

구간의 합 (Segment Tree 연습문제)

피라미드 (Atcoder AGC006D: https://beta.atcoder.jp/contests/agc006/tasks/agc006_d)


Week1_Editorial.pdf



Run@KAIST 봄 연습을 9주동안 진행하게 되었습니다...

교육용 문제를 기반으로 하고 풀이를 쓰려고 하는데 강제성이 없으면 절대로 쓰지 않을 것 같아 스스로 족쇄를 채웠습니다...


Run@KAIST 봄 연습 1주차 문제입니다.


8문제를 준비했고, 첫 주라서 쉬운 문제들입니다.

Week1 (ko).pdf




일이 있어서 교육용으로 만든 알고리즘 문제 세트가 꽤나 좋은 세트 같아서 퍼블릭하게 공개하고 싶어졌습니다. 같이 문제를 만든 사람은, kajebiiiKENNYSOFT 입니다. 


문제들의 난이도는 KOI 중등부 1번 ~ 고등부 3번 정도인 것 같습니다. 문제들이 꽤 넓은 분야를 다루고 있으니 문제를 풀고 풀이를 들으면 실력이 오르는 세트라고 생각합니다.


문제들은 잘 알려진 문제들도 있고, 만든 문제들도 있으며 다른 곳에서 가져오거나 변형한 문제들도 있습니다. 블로그에 문제와 풀이를 계속 올릴 생각입니다. Logical Thinking은 일이 바빠서 잘 안 올리고 있네요...

혹시 문제가 지금 궁금하고 풀어보실 생각이 있거나 관심이 있으시면 이 게시글에 비밀 덧글로 이메일 주소를 달아주시거나 이메일 sakura★kyouko.moe 로 (★=@) 메일을 보내주시기 바랍니다.




문제는 계속 추가 되고 있습니다. 앞으로 10문제 쯤 더 추가 될 예정입니다. 현재 문제들의 목록은 다음과 같습니다. :


  1. 2018.02.05 23:18

    비밀댓글입니다

  2. 2018.02.06 13:25

    비밀댓글입니다

  3. 2018.02.06 13:52

    비밀댓글입니다

  4. 2018.03.28 00:43

    비밀댓글입니다

이 문서는, acmicpc.net 15328번 산타의 선물 문제를 만들게 된 계기, 풀이 그리고 테스트 데이터를 만든 방법에 대해 설명합니다. 문제 스포일러를 원치 않는 분은 읽지 않아주셨으면 합니다.




문제를 단순화 하면 다음과 같습니다.인지 아닌지 판단하세요.


이 문제를 만들게 된 계기는 어떤 트윗에서 시작합니다.

UCPC 2016 D번문제인 Flowey's Love입니다. 입력과 출력이 전부다 정수이지만, 실수오차에 매우 민감한 가혹한 문제입니다. 사실 데이터가 충분히 강한지도 의문입니다. 왜냐하면 이 문제는 유리수, 혹은 제곱근, 혹은 그 수의 제곱근등등을 대소비교를 해야하는 문제이고, 이 문제가 다항시간 안에 풀리는지 안 풀리는지는 현재도 아직 결론이 나지 않은 문제입니다.

뭐 결론적으로 말해서, 컴퓨터에서 지원하는 double 자료형은 오차가 있기 때문에 사용을 해서는 안됩니다. 한가지 예로는 double을 사용한 sqrt에서는

sqrt(6222) + sqrt(8801) + sqrt(14431) + sqrt(8132): 383.00000000000006

이지만, 실제로는



입니다. double을 사용하면 383보다 크다고 나오지만, 실제로는 작죠.


여담으로, a, b, c, d가 모두 제곱수가 아닌 경우에는 등호가 성립하지 않습니다. 숫자가 4개가 아니라 임의의 갯수여도 성립합니다. 다음 논문을 참조하면 좋을 것 같습니다. http://www.math.uchicago.edu/~may/VIGRE/VIGRE2007/REUPapers/INCOMING/reu_paper.pdf


뭐 결국에는, 문제는 실수 오차입니다. 실수 오차에 대해서 깊은 설명은 하지 않겠지만, double자료형의 경우에는 2-53, long double자료형의 경우에는 2-64만큼의 오차가 계산할 때 생길 수 있습니다. 이 문제를 풀기 위해서는 충분하지 못한 정확도 입니다.


사람들이 실수 오차에 대해 좀 더 유의해줬으면 바라고, 문제를 내는 사람들이 실수에 대해 좀 더 관대한 생각을 가지기를 그리고 사람들이 고통받는것을 보기 위해 이 문제를 내었습니다.




이 문제에 대한 제 코드는 다음과 같습니다.

#include<bits/stdc++.h>
using namespace std;
typedef __float128 real_t;

__float128 mysqrt(__float128 x)
{
if(x==0) return 0;
__float128 y = 1, gy = 0;
do
{
__float128 t = (y+(x/y))/2;
gy = y;
y = t;
}while(y!=gy);
return y;
}


int main()
{
int N; scanf("%d", &N);
for(int i=0; i<N; ++i)
{
int px = 0, py = 0, pz = 0;
real_t ans = 0;
int x; scanf("%d", &x);
for(int j=0; j<4; ++j)
{
int a, b, c; scanf("%d%d%d",&a,&b,&c);
ans += mysqrt(real_t((px-a)*(px-a)+(py-b)*(py-b)+(pz-c)*(pz-c)));
px = a, py = b, pz = c;
}
if(ans <= x) puts("YES");
else puts("NO");
}
return 0;
}

결국에는, __float128자료형을 써서 해결했습니다. 어떻게 __float128을 사용하면 충분한 정확도를 가지냐 라는것을 확인했냐고요? 왜냐하면, 이 문제를 만들 때에 모든 가능한 입력에 대해서 확인을 해 보았습니다.

0부터 40000까지의 제곱수 세개의 합으로 표현 가능한 숫자는 58000개 정도가 나옵니다. 여기서 4SUM 문제를 풀고 (4SUM문제는 N^2 lgN의 시간복잡도를 가집니다.)  오차가 일정 범위안에 있는 수들을 다 뽑아내었습니다. 램은 26GB, CPU시간은 2.8GHz 프로세서에서 18분이 걸렸고, 숫자들의 후보를 모은 파일은 60GB였습니다.

여기서 오차가 매우 작은 숫자들을 추려내고 추려내서 숫자들을 뽑아내고, 그리고 그 데이터를 가지고 절댓값이 100 이하가 되게 넣을 수 있는지를 이리저리 계산을 했습니다. 그래서 데이터 파일들을 만들었습니다.


사용된 데이터 중 하나는,

2
583
-9 -5 0
-97 -21 -16
22 -100 95
-100 98 -96
747
-42 -30 -2
-98 -93 74
97 57 -66
-98 -98 99

이고,



의 결과를 얻었습니다.


참고로 이 문제는, 제곱을 열심히 반복하면 정수만 사용해서 문제를 풀 수 있다고 합니다. minimal polynomial이 16차이고, 이걸 구해서 대소비교를 하는 방법으로도 해결을 할 수는 있습니다.



기프티콘을 받으신 모든 분들 축하합니다! 그리고 기프티콘을 받지 못하신 분도 이런 재미있는 문제가 있으면 제가 다시 기프티콘을 들고 오도록 하겠으니 풀어주셨으면 합니다. 감사합니다.





  1. Flowey the Flower 2017.12.28 20:37

    flowey 문제는 실제로 매우 데이터가 약해요. 2~3 개를 빼면 전부 랜덤데이터라..

+ Recent posts