백준이 서비스 종료한 관계로 제 개인 블로그에 에디토리얼 옮겨 둡니다. 지난 3월 14일 18:00 ~ 23:00에 열렸던 제2회 디미고 프로그래밍 챌린지의 에디토리얼을 공개합니다! 제2회 디미고 프로그래밍 챌린지 Editorial.pdf 대회 진행을 위해 힘써주신 검수진 분들과 출제 및 운영진 분들의 노력에 다시 한 번 감사드립니다. 대회...

PART 2에서는 LCS 문제와 그 변형 문제를 정의하고, 이를 해결하기 위한 다양한 방법을 알아보겠다. Longest Common Subsequence 문제 정의 정의: 부분 수열(subsequence)은 문자열 $S$에서 0개 이상의 문자를 제거하여 얻을 수 있는 문자열이다. 정의: 부분 문자열(substring)은 문자열 $S$의 연속한 일...

안녕하세요! 저는 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$개 ...