얼마전 APIO 2019 대회가 진행되었다. Open Contest를 진행한 후, 풀이를 써달라는 분이 계서서 풀이를 작성하였다.

이러고 바로 풀이로 진행하면 블로그 미리보기로 스포일러가 되기 때문에, 몇가지 TMI를 추가한다. 한국은 비공식 성적으로 금메달 0개, 은메달 13개, 동메달 0개를 얻었으며, 보통 6명의 학생만 메달을 받는 것이 룰이지만 너무 많은 동점이 나와서 13명의 학생이 수상을 하는 일이 발생하였다. APIO 2008 이후 초유의 사태이지만 사실 금메달 컷이 깔끔하게 잘려서 별 상관은 없는 것 같다.

문제는 Strange Device / Bridges / Street Lamps 3 문제가 출제되었다.

Berlekamp-Massey 알고리즘은 특정한 DP의 점화식을 찾아주는 알고리즘이다. $10^{18}$ 번째 피보나치 수를 찾기 위해서 행렬 곱셈을 짜고, 타일 채우기 문제를 풀기 위해서 수많은 점화식과 씨름하던 옛 시간은 이젠 안녕. 이제는 백트래킹 짜고 하드코딩해서 넣으면 끝난다.

이 글은 알고리즘의 구현법, 동작 원리나 증명에 대해서 거의 설명하지 않는다. 그 이유는 내가 구현법과 동작 원리, 증명을 모르기 때문이다. 알고리즘 구현은 여기에서 복붙해서 사용하면 된다. 이론적 배경지식이 상당히 깊지만, 그 활용도가 매우 높기 때문에, 일단 이해하지 말고 작동법부터 제대로 깨우친 후, 나중에 다시 돌아와서 방법을 이해하는 것을 추천한다.

1967년 이 알고리즘을 개발한 수학자 Elwyn Berlekamp가 최근 (2019년 4월 9일) 사망했습니다. 고인의 명복을 빕니다. A final game with Elwyn Berlekamp

$K$번째 소수를 구하는 문제: 15965번 문제: K번째 소수

$n$번째 소수를 구하는 방법에는 여러 가지가 있습니다. $i=2$부터 시작해서 각 양의 정수의 약수 개수를 구한 다음, 만약 두 개이면 소수이라는 성질을 이용하거나, 에라토스테네스의 체를 이용할 수도 있습니다. 수학동아 기사에 의하면 $n-1$번째 소수를 알고 있을 때, $n$번째 소수를 찾는 점화식(아래의 점화식)이 발견되었다고 합니다. 아래의 점화식으로 $f_{n}$의 값을 계산한 다음, 그 값의 정수 부분이 $n$번째 소수인 $P_{n}$이 됩니다.

$$f_{1}=\lim_{n\rightarrow\infty} \sum_{k=1}^n \frac{P_{k}-1}{P_{1} \times P_{2} \times \cdots \times P_{k-1}} \fallingdotseq 2.920050977316 \cdots (단, P_{n}=[f_{n}])$$ $$f_{n}=[f_{n-1}] \times (f_{n-1}-[f_{n-1}]+1)$$

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

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

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

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

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

• 이런 글이 올라올 때 대부분의 경우는 본인의 코드가 잘못된 것이었습니다.
• 이런 건 단순 추측 말고 assert문으로 확실하게 확인해 보시기 바랍니다.

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

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

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

안녕하세요. rdd6584입니다.

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

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

안녕하세요. 구글 코드잼 킥스타트 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