Java보다 좋은 Kotlin으로 문제를 풀어 봅시다

Kotlin?

Kotlin은 IntelliJ, Android Studio, PyCharm 등의 IDE를 만든 체코의 JetBrains에서, 개발에 쓸 적절한 JVM 기반 언어를 찾아보다가 필요한 기능들이 없어서 포기하고(예외로 Scala가 있지만 컴파일 속도가 느려서 스킵) 직접 만든 언어입니다.

Kotlin은 기존 자바 코드와 100% 호환되면서도 자바보다 좋은 언어를 만드는 것을 목표로 개발되었습니다. 따라서 기존에 Java로 코딩하셨다면 java.util.* 등의 클래스를 그냥 바로 가져다 쓸 수 있어 적응하기 어렵지 않습니다. 게다가 함수형입니다.

백준 온라인 저지와 Codeforces는 Kotlin을 지원하고 있습니다. ICPC에서는 리저널마다 다르지만 월드 파이널에서는 Kotlin을 지원하고 있습니다. 안타깝게도 한국 리저널에서는 아직 Kotlin을 지원하지 않고 있습니다.

더 읽기댓글 쓰기

자주 틀리는 요인

원래는 BOJ 101 글에 있었던 내용인데, 쓸 내용이 너무 많아져서 독립된 글로 옮겼습니다.

예제는 다 맞는데요...

  • 채점 데이터에는 예제만 있는 게 아니라 우리에게 공개되지 않는 추가적인 데이터가 많이 준비되어 있습니다. 그 데이터에서도 전부 옳은 답을 내야 합니다. 예제 입출력은 "예를 들어 이런 입력을 줄 것이고 이 때는 이렇게 출력해야 한다"라는 뜻이지, "이게 잘 돌아가면 대충 맞는 코드일 것이다"라는 뜻이 절대 아닙니다!!
  • 그 전에 예제가 다 맞는 건 확실한가요? 줄바꿈이나 띄어쓰기 등을 마음대로 바꿔서 입력받으면 안 되고, 마음대로 바꿔서 출력해도 안 됩니다. 반드시 주어진 형식 그대로 입력하고, 예제 출력에서 보이는 대로 출력해야 합니다.
  • ideone 등 온라인 컴파일러 사이트에서 여러분의 코드를 직접 돌려 볼 수 있습니다.

대부분의 언어

  • 입출력이 느리면 그것때문에 시간초과가 날 수 있습니다. 이 문제(링크)를 풀어 봅시다.
  • exit code가 0이 아니면 비정상적인 종료를 의미합니다. C/C++ main의 return 1, 여러 언어의 exit(1) 등으로 0이 아닌 exit code를 내면 런타임 에러입니다.
  • float, double 등의 부동소수점 자료형은 나타내는 수의 범위가 넓지만, 그 범위 안에 있는 모든 수를 정확하게 나타낼 수 있는 게 절대 아닙니다. 범위도 넓은데 원하는 수를 다 표현할 수도 있고 int만큼이나 빠르기까지 하면 그건 상상의 세계에 있는 자료형이죠.
  • '\b'는 하나의 문자일 뿐, 정말로 출력했던 문자를 도로 지우는 문자가 아닙니다. 단지 화면에 내보낼 때만 지운 것처럼 보이게 할 뿐입니다. 출력했던 문자는 지울 수 없습니다.
  • 데이터의 끝에 '\n'가 들어오는 것이 원칙이지만, 꼭 지켜지는 사항은 아니며 오래된 데이터일 수록 지켜지지 않을 가능성이 높습니다. '\n'으로 입력의 끝을 검사하거나, 한 줄을 입력받고 마지막 글자를 지울 경우 문제가 생길 수 있습니다.
  • 널 문자는 하나의 문자로 취급되며, 널 문자와 공백은 다릅니다. 일부 컴퓨터에서 널 문자를 출력할 때 빈 칸이 출력되는데, 실제로는 엄연히 공백과 다른 하나의 문자입니다. 그래서 널 문자를 출력하지 말아야 되는 데 / 공백을 출력해야 되는데 널 문자를 출력하면 오답입니다.
  • "여러 개의 테스트케이스로 이루어져 있는" 문제에서는 각 테스트케이스마다 초기화를 합시다.
  • "다음 코드를 실행했을 때 무슨 결과가 나오는지" 구하는 문제 (예시 1) (예시 2) 같은 경우, 정말로 그걸 직접 실행하라는 뜻이 아니라 만약에 실행한다면 무슨 값이 나올지를 구하라는 뜻입니다.

반례 찾기

  • 가장 중요한 것은 직접 데이터를 만들어서 넣어 보는 것입니다. 질문 게시판에는 이렇게 아무거나 집어넣다 보면 반례가 바로 나오는 질문이 굉장히 많습니다. https://www.acmicpc.net/problem/14405 를 예로 들어 봅시다. 그러면 이런 입력들을 넣어 볼 수 있습니다.
    1. pi 하나만 넣으면? ka? chu? 한 글자만 넣으면? p? k? c? i? a? r?
    1. pika는 YES가 나와야 합니다. 이걸 조금 변형하면? pik? pia? pka? piak? pkia? ipka? kipa? pikaa? pikka? piika? ppika?
    1. kapi도 YES가 나와야 합니다. 이걸 조금 변형하면? kap? kai? api? kaip? kpai? kapii? kaapi?
    1. 주어진 예제를 조금 변형하면? pikap? pikpi? pipikach? pipikaphu?
    1. 그냥 정말로 아무거나 넣으면? abcd? pipichukachuka? pichaku? ppap? pikach?
  • 입력으로 1 이상 1,000,000 이하의 정수 N이 주어진다면 N=1, N=2 등의 최소 케이스가 잘 나오는지 확인하는 것이 좋습니다. 이런 입력이 특이 케이스가 되는 문제들이 종종 있고, 굳이 특이 케이스가 아니더라도 우리의 코드가 최소 케이스에서 틀릴 가능성은 얼마든지 있습니다. 위에서 언급한 "피카츄" 문제의 경우 p, k 등의 한 글자짜리 입력이 여기에 해당되겠죠.
  • N=1,000,000 같은 최대 케이스를 넣었을 때 주어진 시간 제한 안에 답이 나오는지도 확인해 볼 수 있습니다. 답이 맞는지 확인하는 건 어떨까요? 문제에 따라 답을 손으로 알아내기 힘들 수도 있는데, 적어도 말이 되는 값은 나와야겠죠? 출력이 무조건 0 이상일 수밖에 없는 문제에서 음수가 나오면 뭔가 잘못되었다는 뜻입니다.
  • 매우 간단한 풀이가 있는데 시간복잡도가 너무 커서 못 쓰고, 그 대신 더 효율적인 풀이를 생각해야 하는 문제가 있습니다. 이런 문제는 다음 방법으로도 반례를 찾을 수 있습니다. 매우 간단한 풀이이면 구현하기 쉬워서 틀릴 가능성이 낮다는 점을 이용한 방법입니다.
    1. 매우 간단한 풀이를 작성한다.
    1. 랜덤으로 데이터를 만든다.
    1. 간단한 풀이와 틀린 풀이가 내놓는 답이 일치하는지 검사한다.
    1. 2-3번을 반복...

더 읽기댓글 쓰기

2018 SCAL-MOOKJA 대회 진행에 대한 사과문 입니다.

안녕하세요. 이번 SCAL-MOOKJA대회의 문제 출제를 담당했던 출제진 입니다. 먼저, 이번 SCAL-MOOKJA 대회의 문제 지문 오류, 테스트 케이스 데이터의 미숙함, 지문과 인풋 데이터의 잦은 수정으로 인해 Open Contest대회 및 온사이트 대회 중 불편을 겪으신 참가자 여러분께 정말 죄송하다는 말씀을 올립니다.

저를 포함한 대회 문제 출제진들은 SCAL-MOOKJA 대회 문제를 출제할 때, 문제 출제부터 대회까지 4주라는 많은 시간이 있었는데도 각자가 출제한 문제의 솔루션과 정답이 일치하는지만 검사하고, 그 이외의 기본적인 부분을 철저히 검증하지 않았을 뿐더러, 다른 출제진들과 문제를 공유하여 문제 출제와 오류 검증의 기본이 되는 교차검증 마저 하지 않았습니다. 그렇기 때문에, 문제 지문의 맞춤법, 비문, 오타 및 입력 데이터 형식, 범위 오류를 정확히 체크하지 않았습니다.

그리고, 대회 중에 질문으로 들어온 ‘그래프의 방향성 재확인’, ‘데이터 오류 확인 요청’, ‘문제 조건 오류 및 수정 요청’을 포함해 갑작스러운 문제 수정과 재 채점, 확인도 제대로 하지 않고 생각으로만 빠르게 답변을 한 것, 데이터에 오류가 없다고 했지만 나중에 데이터에 오류가 있음을 공지사항으로 답변하는 등, 잦은 문제 변경과 늦은 답변 등 미숙한 대회 운영으로 인해 참가자분들께서 불편을 느끼셨다는 것에 대해 정말 죄송하다는 말씀을 드리고 싶습니다.

더 읽기댓글 쓰기

해시로 장난치기

안녕하세요. 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 질문 게시판에서 활동하면서 "이건 모두가 알아야 할 것 같다"라고 생각한 것들을 적어 보려 합니다.

가장 중요한 팁

  • 채점 데이터에는 예제만 있는 게 아니라 우리에게 공개되지 않는 추가적인 데이터가 많이 준비되어 있습니다. 예제 입출력은 "예를 들어 이런 입력을 줄 것이고 이 때는 이렇게 출력해야 한다"라는 뜻이지, "이게 잘 돌아가면 대충 맞는 코드일 것이다"라는 뜻이 절대 아닙니다!! 그러니 틀렸다고 바로 질문을 올리지 말고 적어도 여러 종류의 입력을 직접 만들어서 넣어 봅시다. 아무렇게나 만들어서 몇 번 넣으면 반례가 나오는 질문이 많이 있습니다.
  • 입력 범위를 봅시다. n이 1,000,000,000까지 가는 문제에서 1부터 n까지 루프를 돌리면 당연히 안 되고, 배열 크기가 10,000까지 가야 되는데 1,000까지 잡으면 당연히 안 됩니다...
  • 질문 게시판을 봅시다. 제출한 사람이 많은 문제일 수록 여러분과 똑같은 질문이 들어있을 가능성이 높아집니다.

더 읽기댓글 쓰기