구사과

조만간 2020.05.11(?) problem solving이 올라옵니다. 그 글의 일부였는데, 좀 길어서 분리했습니다. https://www.acmicpc.net/problem/17405 Step 1 $gcd(F_i, F_j)$ 자체가 너무 커서 주어진 식 그대로는 다항 시간에도 계산을 할 수 없습니다. 하지만, $gcd(F_i, F_j) = F_{gcd(i, j)}$ 임이 잘 알려져 있기 때문에, 이 식을 쓰면 문제는 $\sum_{i = 1}^{n} \sum_{j=1}^{n} gcd(i, j)^k F_{gcd(i, j)}$ 가 됩니다. 항의 계산 결과가 gcd에만 의존함에 주목하십시오. $f(k) = 1 \le i, j \le N, gcd(i, j) = k$ 인 $i, j$ 의 수라고 하면, 위 식은..

이미 아시는 분들도 계시겠지만, 2017년 가을 이후 포스팅되는 대부분의 글은 삼성전자 SW멤버십의 지원을 받아 작성되고 있습니다. 매달 컴퓨터 과학에 관한 글을 주기적으로 SW멤버십에 제공하고, 이에 따른 지원금을 받는 식입니다. 비정기적으로 관리하던 블로그에 매달 주기적으로 글이 올라올 수 있게 된 것은 SW멤버십의 지원 덕분이 큽니다. 감사합니다. SW멤버십에 제공하는 대다수의 글은 제 블로그에 같이 올립니다. 일반적으로 제출 기한이 있는 SW멤버십에 글을 먼저 제출한 후, 데드라인 안에 손보지 못한 부분이 있으면 이 부분을 보강해서 블로그에 올리는 식입니다. 잘못된 사실이나 오탈자 등도 블로그 글 우선으로 반영하기 때문에 (일반적으로는 SW멤버십 글도 반영하려고 하고 있으나 우선순위는 블로그가 높..

http://www.hani.co.kr/arti/opinion/column/935716.html [세상읽기] 죽은 스탈린, 살아있는 진영론 / 조형근 사망 4개월 전인 1952년 당 대회에서의 스탈린. 이렇게 미화되지 않은 사진들은 공개되지 않았다. 러시아 국립사회정치사문서보관소. 삼인 제공 www.hani.co.kr 스탈린은 진영 테제의 창시자였다. 세상은 공존할 수 없는 적대 진영으로 나뉘어 있으며, 정치는 진영 간의 전쟁이라고 믿었다. 이상을 떠벌리는 지식인 부류를 경멸했다. 역사에 만약은 없지만 그의 미친 듯한 중공업 육성이 없었다면 소련은 나치한테 패망했을 확률이 높다. 그렇게 소련은 기적처럼 살아남았다. 진영론을 폄하할 수 없는 까닭이다. 그렇게 기적이 된 소련은 사회주의도 민주주의도 아닌 괴..