안녕하세요! 저는 KOI 특기자 전형으로 디미고에 입학해 알고리즘 동아리 O(n)에서 활동하고 있습니다. 경쟁적 프로그래밍/문제 해결에 흥미를 느껴 고 1,2에 다양한 대회에 출전하거나 학교에서 진행하는 정보올림피아드 준비반에 참가하며 알고리즘에 관해 공부해왔습니다. 알고리즘을 통해 문제를 해결하는 것에 흥미를 느껴 앞으로 컴퓨터로 전공하고 알고리즘...

문제 링크 참고 문헌 못 풀겠어서, 공식 풀이를 보고 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...