Need not to know

▣ 문제 출처 ─ 제3회 kriiicon ㅅ번 문제 ▣ 알고리즘 분류 ─ 수학 / 구현 / 기하 / 많은 조건 분기 / 미적분학(그린 정리) ▣ solved.ac 기준 난이도 ─ Ruby II 문제 링크: https://www.acmicpc.net/problem/11392 약 한 달 전쯤, 모 세미나(?)에서 본 문제의 풀이에 대해 발표할 일이 있었어서 발표 자료를 만들었는데… 나름대로 열심히 만든 자료를 한 번 발표하는 데 쓰고 끝내기는 좀 아까워서 여기에도 올려봅니다! (파일 저장 후 '읽기 전용'으로 여시면 됩니다.) 원본 발표 자료에서 개인 정보나 문제 풀이와 관련 없는 부분 등을 조금 수정한 버전입니다. 이 문제를 도전하시는 분들에게 조금이라도 도움이 되셨으면 좋겠습니다. :) 덧붙여, 본 문제..

▣ 문제 출처 ─ Polish Olympiad in Informatics(POI) 2005/2006 Stage 1의 5번 문제 ▣ 알고리즘 분류 ─ DFS / 이분 탐색 / 스위핑 / 기하 / CHT(Convex Hull Trick) ▣ solved.ac 기준 난이도 ─ Diamond IV (개인적으로는 다3 정도라고 생각한다.) 문제 링크: https://www.acmicpc.net/problem/1909 크기 $S = W_x \times W_y$ 그리드에 $n$개의 '특별한 점'이 주어진다. $(sx,\, sy)$에서 $(tx,\, ty)$로 가는 임의의 경로에 대해, 경로상의 임의의 점과 특별한 점들 사이 거리의 최솟값을 최대화하는 문제다. 일단 최솟값을 최대화하는 건 나중에 생각하기로 하고, 문제..

인접행렬과 인접리스트 $V$개의 정점이 있고 $E$개의 간선(방향이든 무방향이든 상관없지만, 여기서는 편의를 위해 무방향이라 가정하자)이 있는 그래프 $G(V,\, E)$를 생각하자. 이러한 그래프를 저장하는 방법은 크게 두 가지가 있다. 첫 번째는 인접행렬(Adjacency Matrix)이다. 어떤 두 점이 인접한지, 즉 두 점 사이에 간선이 있는지를 표시하는 행렬로 그래프를 표현한다. 실제 프로그래밍에서는 아래 코드와 같이 $V \times V$ 크기의 배열 g를 사용해서 g[A][B] 값을 A번 정점과 B번 정점 사이 간선의 개수로 저장한다. #include #define NMAX 1000 int g[NMAX][NMAX]; int main() { int N, M; scanf("%d%d", &N, &..

몫 연산자(/)는 알다시피 컴퓨터공학에서 주로 정수끼리의 나눗셈을 나타낼 때 사용된다. 이름대로 나눗셈의 값을 그대로 반환하는 것이 아닌, '몫'을 반환하는 연산자다. 즉 수학에서 쓰는 '/'와 차이점이 있다(단, 파이썬의 '/'는 수학에서의 쓰임과 동일하다. 대신 파이썬에는 '//'이라는 몫 연산자가 따로 존재한다). 가우스 기호([ ])를 사용해서 말하자면, 정보과학에서 p/q는 수학에서의 $\left[\frac{p}{q}\right]$와 같다고 할 수 있다. 이 글에서는, 몫 연산자의 이러한 점을 이용한 팁을 알아볼 것이다. ※ 편의상 이후에 등장하는 미지수들은 모두 양수일 경우만 고려한다. floor, ceil, round 정수와 관련해서, 유명한(?) 함수들이 있다. 바로 floor(x), ce..