구사과

간선에 음이 아닌 가중치가 있는 무방향 그래프 $G$가 주어졌을 때, 다음과 같은 쿼리를 처리하자:1 u v: $u, v$ 간의 최단 경로의 길이를 반환한다...는 어려운 문제이다. Balanced separator를 쉽게 찾을 수 있거나 하는 특수 케이스가 아니면 보통 $O(nm)$ 시간에 Dijkstra를 $n$ 번 돌리는 방법보다 좋은 방법이 없다. 그러니까 다음과 같은 Approximate 버전을 생각하자. 초기에 정수 파라미터 $k \geq 1$ 이 같이 주어졌을 때:1 u v: $u, v$ 간의 최단 경로의 길이가 $d$ 라면, $[d, (2k-1)d]$ 범위에 있는 수를 출력하라.실제 출력한 수를 길이로 가지는 경로가 존재하지 않을 수도 있지만, 일단 오늘 얘기할 알고리즘에서는 항상 있는 경..

까먹기 전에 뭐라도 씀원래 아인타랑 같이 Season 3을 좀 했다. 친구없음 이슈로 거의 다 2인팀이었는데, 세미파이널 때는 잘하는 사람을 한명 데려가고 싶어서 정민찬이랑 같이 나갔다. 처음으로 해 본 3인팀이었다.SemifinalsUCPC 세미나에서 강연을 하고 참가한 대회였고 뭔가 제대로 기여를 못 한 기억밖에 안 난다. 아마 한시간 넘게 늦참하고 엄청 피곤하게 쳤던 것으로 기억한다. 지금 제출창을 열어보니까 내가 짠 문제가 3개 있는데D는 내가 풀었던게 기억난다L은 아인타가 Directed MST로 환원하고 난 그냥 그 풀이를 그대로 짰던게 기억난다E는 뭔가 내 코드가 있는데 기억이 안 난다.. 내가 풀었을까? 누가 도와줬을까? 흠...아무튼 난 버스만 탔고, 그래서 커트에 약간 미달했는데, 어쩌..

(6/11 추가) 두 구글 폼은 당분간 계속 열어두겠습니다. 아직 많은 마이그레이션이 처리되지 않은 상태이기도 하고, 폼을 특별히 닫을 이유도 없어 보여서, 현재 상태로 두고 관리도 하겠습니다. 다만 제가 불시에 사전 공지 없이 폼을 닫을 수도 있습니다.(5/13 추가) 두 구글 폼은 한국 시간 6월 10일 오후 1시까지 열어두겠습니다.(4/19 추가: 권한 WRITE로 해주세요! READ로 하니까 업로드가 안 되네요. 수정은 안할건데, 걱정되시면 clone해서 주시면 됩니다)BOJ 서비스 종료에 관해서 Qingyu님과 이야기를 나누었는데, Qingyu님이 기존 문제를 QOJ.ac로 마이그레이션하는 데 있어 도움을 주실 의향이 있다고 해 주셔서 마이그레이션 신청을 받고자 합니다. 도움을 주신 Qingyu..