해시로 장난치기

안녕하세요. rdd6584입니다.

문자열이라면 절레절레 하던 제가 이번 네블컵을 준비하면서, 해시에 대해 어느정도 이해를 하게 되었습니다. 그래서 해시로 여러가지 장난을 쳐봤고, 해시로 풀 수 있는 문제와 기법을 소개해보려고 합니다.

더 읽기댓글 쓰기

OCaml로 문제 풀이하기

OCaml 소개

OCaml은 Objective Caml입니다. CAML은 Categorical and Abstract ML입니다. ML은 Machine Language입니다. 즉 Caml은 기계 언어를 카테고리적이고 추상적으로 다루기 위해 고안된 언어이고, OCaml은 그러한 Caml에 OOP적인 요소를 부가한 것입니다.

OCaml로 문제 풀이: 2769번 논리식 비교

더 읽기댓글 쓰기

Google Code Jam Kickstart 소개

안녕하세요. 구글 코드잼 킥스타트 2018의 신청이 시작되었습니다. 구글 코드잼은 많이들 알고 계실텐데, 킥스타트는 아직 아시는분이 많이 없는 것 같아서 대회를 소개하기 위해 블로그에 글을 쓰게 되었습니다.

구글 코드잼 킥스타트는 일반 구글 코드잼과는 별도로 진행되는 대회입니다. 대회 형식이나 진행방법은 일반 코드잼과 완전히 똑같아요. 공식 홈페이지에는 다음과 같이 소개되어있습니다.

Kickstart is a Code Jam competition that gives participants the opportunity to develop and grow their coding skills to explore a career at Google. Each round invites students and industry professionals to solve algorithmic challenges designed by Google engineers—you can participate in one, or join them all. Kickstart is a great way for students to not only have fun, but also get a glimpse into the programming skills needed for a technical career at Google. The top participants from each round may be contacted by a Google recruiter.

더 읽기댓글 쓰기

정렬 속도 비교

여러가지 언어와 정렬 방법을 이용해서 시간이 얼마나 걸리는지 비교해 보았습니다.

방법: N (= 10,000,000)개의 정수를 입력받은 다음, 오름차순으로 정렬하는 시간을 측정. 10번 측정해서 평균값으로 순위를 매김

입력 파일: https://github.com/Startlink/boj-sort-test

더 읽기댓글 쓰기

출력 속도 비교

여러가지 언어와 출력 방법을 이용해서 시간이 얼마나 걸리는지 비교해 보았습니다.

방법: 총 N개의 줄에 1부터 10,000,000까지의 자연수를 한 줄에 하나씩 출력하는 시간을 측정. 10번 측정해서 평균값으로 순위를 매김

순위 언어 출력 방법 평균 (초)
1 C11 fwrite 0.4423
2 C++17 ios_base::sync_with_stdio(false); cout << i << '\n'; 0.827
3 C++17 ios_base::sync_with_stdio(false); cout.tie(NULL); cout << i << '\n'; 0.8272
4 C++17 printf("%d\n",i); 0.8614
5 C11 printf("%d\n",i); 0.9118
6 C++17 cout << i << '\n'; 0.9229
7 Java BufferedWriter, bf.write(i + "\n"); 0.9581
8 PyPy for i in xrange(1,n+1): sys.stdout.write(str(i)+'\n') 0.9847
9 C++17 s += to_string(i) + '\n';를 이용해 문자열 하나로 만든 다음, 마지막에 cout << s << '\n'; 1.1507
10 Java StringBuilder를 이용해 문자열 하나로 만든 다음, System.out.println(sb); 1.1881
11 Java BufferedWriter, bf.write(Integer.toString(i)); bf.newLine(); 1.2556
12 PyPy3 for i in range(1,n+1): sys.stdout.write(str(i)+'\n') 1.3722
13 PyPy print '\n'.join(map(str,xrange(1,n+1))) 1.3738
14 PyPy sys.stdout.write('\n'.join(map(str,xrange(1,n+1)))) 1.3772
15 PyPy for i in xrange(1,n+1): print i 1.4968
16 Python 2 print '\n'.join(map(str,xrange(1,n+1))) 1.7621
17 Python 2 sys.stdout.write('\n'.join(map(str,xrange(1,n+1)))) 1.7658
18 Java PrintWriter 1.954
19 Python 3 print('\n'.join(map(str,range(1,n+1)))) 2.3312
20 Python 3 sys.stdout.write('\n'.join(map(str,range(1,n+1)))) 2.337
21 PyPy sys.stdout.write(''.join(str(i)+'\n' for i in xrange(1,n+1))) 2.3935
22 PyPy print ''.join(str(i)+'\n' for i in xrange(1,n+1)) 2.3974
23 Python 2 sys.stdout.write(''.join(str(i)+'\n' for i in xrange(1,n+1))) 2.536
24 Python 2 print ''.join(str(i)+'\n' for i in xrange(1,n+1)) 2.5372
25 PyPy3 for i in range(1,n+1): print(i) 3.051
26 Python 2 for i in xrange(1,n+1): print i 3.069
27 C# 6.0 StreamWriter 3.0959
28 PyPy3 sys.stdout.write('\n'.join(map(str,range(1,n+1)))) 3.5625
29 PyPy3 print('\n'.join(map(str,range(1,n+1)))) 3.566
30 Python 3 sys.stdout.write(''.join(str(i)+'\n' for i in range(1,n+1))) 3.6766
31 Python 3 print(''.join(str(i)+'\n' for i in range(1,n+1))) 3.6836
32 PyPy3 print(''.join(str(i)+'\n' for i in range(1,n+1))) 3.8326
33 PyPy3 sys.stdout.write(''.join(str(i)+'\n' for i in range(1,n+1))) 3.8339
34 C# 6.0 StringBuilder를 이용해 문자열 하나로 만든 다음, Console.Write(sb); 3.8562
35 Python 2 for i in xrange(1,n+1): sys.stdout.write(str(i)+'\n') 4.3475
36 Python 3 for i in range(1,n+1): sys.stdout.write(str(i)+'\n') 5.3699
37 Python 3 for i in range(1,n+1): print(i) 5.8186
38 PyPy for i in xrange(1,n+1): os.write(1,str(i)+'\n') 10.4553
39 C++17 cout << i << endl; 11.5322
40 PyPy3 for i in range(1,n+1): os.write(1,(str(i)+'\n').encode('utf-8')) 12.0509
41 Python 2 for i in xrange(1,n+1): os.write(1,str(i)+'\n') 14.8269
42 Python 3 for i in range(1,n+1): os.write(1,(str(i)+'\n').encode('utf-8')) 18.2189
43 Java System.out.println(i); 30.013
44 C# 6.0 Console.WriteLine(i); 30.1438

더 읽기댓글 쓰기

입력 속도 비교

여러가지 언어와 입력 방법을 이용해서 시간이 얼마나 걸리는지 비교해 보았습니다.

방법: 첫째 줄에 정수의 개수 N (= 10,000,000), 둘째 줄부터 N개의 줄에 한 개의 자연수(10,000 이하)가 적힌 파일을 입력받는데 걸리는 시간을 측정. 10번 측정해서 평균값으로 순위를 매김

순위 언어 입력 방법 평균 (초)
1 C11 mmap 0.043
2 C11 fread 0.0799
3 C11 getchar 0.3496
4 C++17 ios_base::sync_with_stdio(false); cin.tie(NULL); 0.5938
5 C++17 ios_base::sync_with_stdio(false); 0.6348
6 Java BufferedReader, Integer.parseInt 0.6585
7 C11 scanf 0.9206
8 PyPy int(sys.stdin.readline()) 0.9229
9 PyPy map(int,os.read(0, 100000000).split('\n')) 1.1169
10 PyPy3 map(int,os.read(0, 100000000).decode('utf-8').split('\n')) 1.5408
11 PyPy int(raw_input()) 1.925
12 C++17 cin.tie(NULL); 2.059
13 C++17 cin 2.1742
14 C# 6.0 int.Parse(Console.ReadLine()) 2.9635
15 Python 3 map(int,os.read(0, 100000000).decode('utf-8').split('\n')) 4.4033
16 Python 3 int(sys.stdin.readline()) 4.4394
17 Java Scanner 4.8448
18 Python 2 map(int,os.read(0, 100000000).split('\n')) 4.8553
19 Python 2 int(sys.stdin.readline()) 5.7471
20 PyPy3 int(sys.stdin.readline()) 6.6291
21 Python 2 int(raw_input()) 8.9765
22 Python 3 int(input()) 12.4443
23 PyPy3 int(input()) 17.3772
24 Python 2 input() 37.7823
25 PyPy input() 110.3676

더 읽기댓글 쓰기

BOJ 101

BOJ 작동 원리

채점 서버에는 한 쌍 이상의 입력 파일과 출력 파일이 있습니다.코드를 제출하면 그 코드에 입력 파일에 적힌 대로 입력하고 나타나는 출력을 출력 파일과 비교합니다. 모든 입력/출력 파일에 대해 코드가 문제 없이 올바른 출력을 내야 합니다. 여기서 "올바름"이란 것은 단순히 정답과 같은 값이 아니라 같은 출력을 의미합니다. 예를 들어 45.0을 출력해야 하는데 45나 45.00을 출력하면 오답입니다.

입출력 파일은 공개되지 않습니다. 예제는 데이터 중 극히 일부에 불과합니다. 예제는 자신의 코드가 맞을 것임을 확신하는 용도가 아니라, 입출력의 형식을 확인하고 문제의 설명을 검토하는 용도로 사용해야 합니다.

스페셜 저지가 있는 문제에는 출력이 올바른지 검사하는 채점 코드가 따로 있습니다. 그러므로 "올바른 출력"은 여러 가지가 될 수 있고, 그 중 하나만 출력하면 됩니다. 예를 들어 10^-2 이하의 오차를 허용하는 문제라면 출력과 정답의 오차가 10^-2 이하인지 검사하는 코드가 있습니다. 그런 문제에서 정답이 45.0이라면 45나 45.00을 출력해도 정답을 받을 수 있습니다.

더 읽기댓글 쓰기

2017 ACM ICPC Asia-Tsukuba Regional 후기

12월 16, 17일에 일본 츠쿠바에서 열린 ACM ICPC Tsukuba Regional에 다녀왔습니다!

이번 츠쿠바 리저널은 일본 43팀, 일본 외 7팀으로 총 50팀이 참가했습니다.

더 읽기댓글 쓰기

백준 온라인 저지에서 푼 문제 수와 codeforce rating간 관계 (개발기)

(선 스포 후 설명)

0. 서론

안녕하세요, BOJ의 데이터를 긁긁하면서 BOJ계의 OP.GG 개발을 꿈꾸는(?) 사람입니다.

더 읽기댓글 쓰기

컴파일 에러가 나시나요? (C/C++)

최근들어 컴파일에러로 오답을 받고 질문을 올리시는 분이 자주 보이는 것 같습니다.

주로 그 내용은 "비주얼 스튜디오에서는 되는 데 백준에서는 오류가 나네요" 등이더군요.

컴파일 에러를 해결하시는 데에 도움이 될 만한 글을 남기고자 합니다.

더 읽기댓글 쓰기