▣ 문제 출처 ─ 2019년도 서울대학교 프로그래밍 경시대회(SNUPC) Div. 1 G번 문제 ▣ 알고리즘 분류 ─ 수학(미적분학, 기하학, 확률론) ▣ solved.ac 기준 난이도 ─ Diamond II 문제의 내용은 여기에서 볼 수 있다. 필요하지 않은 스토리텔링 부분을 제외하면 문제의 내용은 한 줄로 요약할 수 있다: 다각형이 주어질 때, 다각형 내의 임의의 두 점 사이 거리의 제곱의 기댓값을 구하는 것이 목표다. 다각형 내의 점은 연속적으로 분포하므로 적분을 써야한다는 것을 쉽게 짐작할 수 있다. 주어지는 다각형의 전체 넓이(혹은 다각형 그 자체)를 $S$라고 하자. 두 점의 좌표를 각각 $(x_1,\, y_1),\, (x_2,\, y_2)$라 하면 거리의 제곱은 $(x_1 - x_2)^2 +..
▣ 문제 출처 ─ 2017년도 한국 정보올림피아드(KOI) 전국 본선 고등부 1번 문제 ▣ 알고리즘 분류 ─ BFS / 수학 / 구현 ▣ solved.ac 기준 난이도 ─ Gold II 2017년도 고등 KOI 1번으로 나온 문제다. (문제의 내용은 여기에서 확인할 수 있다.) 문제의 내용을 대략 요약하면 다음과 같다: 용량이 다른 두 개의 빈 물통 A, B가 있고, 각 시행마다 하나의 물통을 가득 채우거나, 비우거나, 한 물통에서 다른 물통으로 물을 옮기는 행위를 할 수 있다고 한다. 물통 A, B의 용량 $a,\, b\,(a < b)$와 최종 상태 $(c,\, d)$가 주어질 때, $(0,\, 0)$에서 $(c,\, d)$로 만들기 위한 최소 시행 수를 구하는 문제다. 만약 최종 상태로 만들 수 없다..
몫 연산자(/)는 알다시피 컴퓨터공학에서 주로 정수끼리의 나눗셈을 나타낼 때 사용된다. 이름대로 나눗셈의 값을 그대로 반환하는 것이 아닌, '몫'을 반환하는 연산자다. 즉 수학에서 쓰는 '/'와 차이점이 있다(단, 파이썬의 '/'는 수학에서의 쓰임과 동일하다. 대신 파이썬에는 '//'이라는 몫 연산자가 따로 존재한다). 가우스 기호([ ])를 사용해서 말하자면, 정보과학에서 p/q는 수학에서의 $\left[\frac{p}{q}\right]$와 같다고 할 수 있다. 이 글에서는, 몫 연산자의 이러한 점을 이용한 팁을 알아볼 것이다. ※ 편의상 이후에 등장하는 미지수들은 모두 양수일 경우만 고려한다. floor, ceil, round 정수와 관련해서, 유명한(?) 함수들이 있다. 바로 floor(x), ce..
- Total
- Today
- Yesterday