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


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



'프로그래밍 > 알고리즘' 카테고리의 다른 글

선형 점화식의 빠른 계산  (0) 2018.07.24
HYEA Online Judge 개발  (0) 2018.07.06
Run@KAIST 봄 연습 3주차  (0) 2018.03.20
Run@KAIST 봄 연습 2주차 에디토리얼.  (0) 2018.03.14
Run@KAIST 봄 연습 2주차  (0) 2018.03.11

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문제 쯤 더 추가 될 예정입니다. 현재 문제들의 목록은 다음과 같습니다. :


이 문서는, 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차이고, 이걸 구해서 대소비교를 하는 방법으로도 해결을 할 수는 있습니다.



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





시간복잡도(Time complexity)는 어떤 프로그램이 수행하는데 걸리는 시간을 말한다. 프로그램이 빨리 실행 될 수록 이로운 점이 많기 때문에, 우리는 시간복잡도를 줄이려고 노력한다. 프로그램이 수행하는데 걸리는 시간과 시간복잡도에 대해 알아보자. 참고로 이 글에는 이해하기 어려울 수 있는 수학적인/공학적인 내용이 들어있다. 이해하지 않고 읽기만 해도 되는 내용에는 표시를 해놓겠다. 이외의 내용은 최대한 이해하기 쉽게 작성하려고 했다.


프로그램의 실행 시간

최신 프로세서 들은 어느정도의 연산을 할 수 있을까? 필자가 쓰고 있는 컴퓨터의 CPU는 Intel(R) Core(TM) i7-7700HQ @ 2.80GHz 이다. 여기서 2.80GHz라는 의미는, 1초에 28억번 "클럭"을 돌릴 수 있다는 것이다. CPU는 기본적으로 하나의 클럭에 한 가지 연산을 처리한다. 쉽게 말하면, 내 CPU는 1초에 28억번 연산을 할 수 있다는 뜻이다. 물론 실제로는 그렇지 않고, 파이프라이닝이라는 것을 한다.


[그림 1] (a)는 일을 순차적으로 처리한다. (b)는 파이프라인을 통해 동시에 처리한다.


쉽게 말해서, 동시에 진행할 수 있는 일 들을 동시에 진행하는 것이다. 우리가 어떤 두 수를 더하기 위해서는, 그 두 수를 본 다음에 계산을 하고, 결과를 어딘가에 작성해야 한다. 그래서 우리가 더해야 할 두 수가 많으면, 속도를 올리기 위해서 "두 수를 보는 것", "계산 하는 것", "결과를 작성하는 것"의 세 단계로 나눠서 일을 수행하게 되고 결과를 작성하면서 두 수를 보고, 계산을 하게 된다. CPU 내에서도 이런 작업이 일어나게 된다. 이것을 "파이프라이닝"이라고 한다. 최신 CPU의 파이프라인은 13~30단계 정도이고, 하나의 파이프라인이 기본적으로 하나의 일을 하는데 걸리는 시간은 1클럭이다. 모든 연산이 모든 파이프라인을 거치는 것은 아니며, 여기서 연산들의 속도차이가 생긴다.

결론적으로 말해서, 연산 하나의 연산시간을 측정하는 것은 의미가 없고, 그 연산의 "평균적인" 연산시간을 측정하는 것이 전체 실행시간을 판단하는 데에 도움을 준다. 간단한 연산인 64bit수의 덧셈, 뺄셈 같은 것은 1클럭 정도가, 곱셈 등은 3클럭, 메모리 접근은 4~300클락, 나눗셈은 80~100 클락 정도가 걸린다. 자세한 내용은 http://www.7-cpu.com/ 등의 사이트를 참조하면 좋다.

뭐 결론적으로, 우리는 가벼운 연산들을 30억번 정도, 무거운 연산들을 1억번 정도 할 수 있다고 생각하면 된다.


큰 수에서의 프로그램의 실행 시간

다음 두 함수를 생각하자. 이 두 함수는 같은 입력에 대해 같은 결과가 나온다. 이 두 프로그램의 차이가 뭔지 살펴보자.

unsigned func1(unsigned n)
{
int sum = 0;
for(int i=0; i<=n; ++i) sum += i;
return sum;
}

unsigned func2(unsigned n)
{
return (unsigned long) n * (n-1) / 2 + n;
}

위의 프로그램은 덧셈, 비교라는 가벼운 연산으로 이루어져 있어서, 연산 하나하나의 실행속도가 빠르다, 반면 아래의 프로그램은 곱셈과 나눗셈(사실 대부분의 컴파일러는 나눗셈을 최적화 해준다.) 으로 이루어져 있어서, 연산 하나하나의 실행속도가 느리다. 우리는 대략, 위의 프로그램이 기본 2클락에, 숫자를 한번 더 할 때 3클락 정도가 걸린다고 생각할 수 있다. 그리고, 아래의 프로그램은 입력에 관계 없이 100클락 정도가 필요하다는 것을 알 수 있다. 결론적으로, 우리는 실행시간을 n에 대한 함수로 나타낼 수 있다. 첫번째 함수의 실행시간은 T(n) = 3n+2일 것이고, 두번째 함수의 실행시간은 T(n) = 100일 것이다.


만약 우리가 쓰는 n의 범위가 0에서 10정도라면, 우리는 func1(n)을 사용할 것이다. 왜냐하면 func1은 2~32클락이 필요할 것이고, func2는 100클락이 필요할 것이기 때문이다. 하지만 만약 우리가 프로그램이 임의의 큰 n에 대해서 빠르게 돌기를 원한다면, n이 33을 넘은 시점부터는 func2가 더 빠르기 때문에, func2를 써야한다.


우리는 대부분 프로그램이 큰 입력에 대해서도 빠르게 실행되기를 원하기 때문에, func2를 사용할 것이고, 여기서 우리가 관심이 있는것은 n에 대해서 얼마나 프로그램의 실행시간이 커지는지에 대해서이다. 우리는 프로그램의 시간을 big-O 표기법으로 표현할 것이다. 이 표기법은 가장 시간이 오래 걸리는 부분에 대해서만 관심을 가진다. 첫번째 함수의 경우 T(n) = 3n + 2에서, 3n은 2보다 충분히 빠르게 커지기 때문에, 2를 무시하고 3n만 남길 수 있다. 그리고 커지는 정도에서 우리는 3이라는 숫자에 관심을 가지지 않는다. 왜냐하면, 이 숫자가 얼마나 크든 작든, 큰 수에서의 대소관계가 변하지 않기 때문이다. T(n) = an인 알고리즘과, T(n) = bn2인 알고리즘이 있으면, a와 b가 얼마나 크든 충분히 큰 n (>a/b)에 대해서, 앞의 알고리즘이 유리할 것이기 때문이다. 그래서 우리는 T(n) = 3n+2에서, 의미있는 부분인 n만 가져와서, O(n)이라고 부른다. T(n) = 100일 경우에는, O(1) 알고리즘이 되는 것이고,  T(n) = 0.00001n4+8n+92312312 같은 경우에는, O(n4) 알고리즘이 되는 것이다. (좀 더 자세히 말해서, f(n) = O(g(n)) 이라고 부르는 것은, 일 때 이다.)


우리가 충분히 큰 입력에 대해서 빠르게 실행되는 것에 관심을 가지는 이유는 여러가지가 있지만, 시간을 상수배만큼 줄이는것보다, n에 관한 식으로 줄이는게 좀 더 효율적이기 때문인 것이 크다.




최근에 바빠서 글을 못 남기는것 같아서, 짧게 짧게라도 글을 올리는게 낫겠다고 느껴서 간단하게 올렸다. 다음 포스트에서는 시간복잡도 분석에 대해서 써 볼것이다. 게시글에 개선할 사항은 덧글로 남겨줬으면 한다.




이제까지의 모든 Logical Thinking 게시글 보기: http://blog.kyouko.moe/8

+ Recent posts