문제 링크 참고 문헌 풀이 보고 풀었다. 나이브하게 생각하면 연결 안된 정점 쌍을 dsu로 묶어주면 된다. 이걸 빠르게 해야한다. 연견된 간선이 가장 작은 정점을을 $a$라고 하자. $a$와 연결된 간선은 최대 $\frac{M}{N}$개이다. $a$와 연결된 정점 집합을 $A$, 아닌 집합을 $B$라고 하자. $A$의 크기는 최대 $\frac{M...

문제 링크 $dp[x][e]$를 $x$번 자동차까지 해결한 상태에서, $e$번 칸이 가장 아래에 있을 때의 최소 비용이라고 정의하자. \(dp[x][e] = \min_s(dp[x-1][s] + C(s, e, x))\) \(C(s, e, x) = \text{x를 모두 지나며 s에서 시작해 e에서 끝내는 최소 비용}\) 이렇게 하면 $\mathcal...

문제 링크 참고 문헌 풀이 검색해서 풀었다. 통신 가능한 쌍 $i < j$에 대해 $ans[i] = \max(H[i] - H[j])$라고 하자. 이를 세그먼트 트리로 관리하며 스위핑으로 구할 것이다. $i$는 $[i + A[i], i + B[i]]$ 범위에서 유효하다. $i$가 유효할 때 세그먼트 트리의 $i$번째 인덱스에 $H[i]$를 ...

문제 링크 자력솔이다. 예전에 한 번 보고 “아, 비트DP구나”만 생각하고 묵혀놨던 문제다. 어떤 단어를 회문의 중심으로 잡고, 왼쪽과 오른쪽에 단어를 추가하며 비트DP를 할 것이다. 중심을 기준으로 왼쪽 문자열을 $L$, 오른쪽 문자열을 $R$라고 하자. $n(L) \lt n(R)$라면 $L$에 단어를 추가하고, 아니라면 $R$에 단어를 추가할 ...

목차 OSI 참조 모델 개념 3가지 OSI 참조 모델의 계층별 특징 1-3계층의 장비 이름과 특징 OSI 참조 모델 개념 국제 표준화 기구에서 발표한 7계층 이루어진 구조 컴퓨터 시스템에서 데이터를 전송하기 위한 과정을 기능별로 나눔 통신 관련 기업이 제품을 만들거나 프로그램을 개발할 때 참조하는 표준 OSI 참조 모델...

문제 링크 디미고 정올 대비반이 끝나고 골랜디하면서 흥미로운 문제를 찾아서 블로그에 쓴다. 난 이 문제를 풀지 못했는데 k_san이 풀어서 풀이 물어보고 이해한 내용이다. 웰논이라는데 테크닉 이름은 모르겠다. $A, B, C, D$는 헷갈리니까 $N_1, C_1, N_2, C_2$라고 하자. $1$번을 $N_2$개 사고 $2$번을 $N_1$개 ...

문제 링크 내가 처음으로 푼 언레 문제다. 내가 기여해서 다1이 되었다. 예전에 풀이를 들었었던 문제다. 무향 단순 연결 그래프가 주어진다. $u$와 $v$를 잇는 간선과 $u, v$ 그리고 $u, v$에 연결된 모든 간선을 지웠을 때 그래프가 연결되어 있지 않게하는 간선의 개수를 구하는 문제이다. 단절점/단절선 문제이니 당연히 DFS Span...

문제 링크 중국의 의문의 블로그에서 풀이를 보고 풀었다. 여기서 찾았다. Anton, Dmytro, Borys이 각각 받을 사탕의 개수를 $A, B, C$라고 하자. $A \geq B \geq C$를 만족해야 한다. $A - C$를 최소화해야 한다. $front := a[1:N/2]$ $back := a[N/2:N]$ 이라고 하자. $fro...

문제 링크 센트인 건 알고 풀었다. 어느 정도 접근한 다음에 뭔가 잘 안돼서 인터넷에서 풀이를 보고 풀었다. algorithm 일반성을 잃지 않고 $a \leq b \leq c$라고 하자. 직관적으로 $c$를 연결되게 하는 것보다는 $a, b$를 연결되게 하는 것이 편하다. 그래프에서 dfs spanning tree를 구성하자. (사실 아무렇게...

문제 링크 정답인 집합 $s$를 생각하자. $s$에서 가장 먼 두 점을 $a, b$와 그 거리를 $d$라고 하자. $a, b$를 중심으로 하고 반지름이 $d$인 두 원을 생각하자. $a, b$가 가장 먼 두 점이기 때문에 두 원이 겹치는 영역안에 집합의 모든 점이 들어갈 수 있다. 선분 $\overline{ab}$을 기준으로 두 구역 $p, ...