문제 링크 참고 문헌 못 풀겠어서, 공식 풀이를 보고 AI로 번역해가며 풀었다. 첫번째 연산을 off, 두번째 연산을 on, 세번째 연산을 toggle 이라고 부르겠다. 이 문제는 세심한 관찰을 요구한다. 그것들을 나열해 보겠다. off, on 연산들이 겹치지 않는 최적해가 항상 존재한다. 모든 on, off 연산 이후에 모든 tog...

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

문제 링크 $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를 구성하자. (사실 아무렇게...