구사과

이 글은 https://codeforces.com/blog/entry/75431 의 한글 번역본입니다. 가능하면 원문을 보는 것을 추천합니다 ;) 그래프 $G$가 주어질 때, 각 정점 $v$에 대해 자연수 색상 을 배정하여 간선으로 직접 연결된 정점 쌍마다 다른 색상을 배정해야 한다. 이 때, 배정된 최대 색상을 최소화해보자. 즉, 서로 다른 색의 수를 최소화해야 한다. 이 문제는 그래프의 정점 색칠 (Graph Coloring, Vertex Coloring) 문제로, NP-complete임이 잘 알려져 있다. 너무 어려우니까 다른 문제를 생각해 보자. 그래프 $G$가 주어질 때, 각 간선 $v$에 대해 자연수 색상 을 배정하여 간선으로 직접 연결된 정점 쌍마다 다른 색상을 배정해야 한다. 이 때, 배정..

조만간 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$ 의 수라고 하면, 위 식은..

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