서론 문제 설명 $m(1 \leq m \leq 200)$개의 문자열 패턴이 주어진다. 패턴의 길이 $length(pattern)$은 최대 $10$이다. 길이 $n$의 문자열 $s$가 될 수 있는 경우의 수를 구하시오. 출력할 때는 (경우의 수) $\bmod 10007$을 출력한다. 문제 링크 문제 유형 아호 코라식을 구현하고, 동적 계획법을 이...

8주차 계획 개요 8주차(2. 19 ~ 2. 25)의 계획입니다. 27장 그래프의 표현과 정의 내용 28장 그래프의 깊이 우선 탐색 서론 문제: DICTIONARY 문제: WORDCHAIN 문제: GALLERY 문제: MEETINGROOM ...

서론 문제 설명 어떤 임의의 원소가 같다와 다르다라는 정보가 $m(1 \leq m \leq 100000)$개 제공되고, 원소의 개수는 $n(1 \leq n \leq 10000)$개 입니다. 원소의 상태가 2개라면, 같은 원소의 최대 크기를 구하시오, 만약 입력에 모순이 존재한다면, 모순이 존재함을 출력하시오. 문제 링크 문제 유형 이분 그래프 판...

서론 문제 설명 트리에서, 노드 $u$, $v$간의 거리를 계산하시오. 트리의 노드의 개수는 $n(1 \leq n \leq 100000)$개이고, 거리를 계산하는 질문(Query)의 수는 $q(1 \leq q \leq 10000)$개이다. 문제 링크 아이디어 노드의 거리를 구하기 위해서는 우리는 먼저 BFS를 떠올릴 수 있습니다만, 공교롭게도, ...

서론 문제 설명 삽입 정렬에서 각 원소의 inversion count가 주어질 때, 초기의 배열 값을 복원하시오. 문제 링크 inversion count inversion count는 삽입 정렬과 같이 진행되는 정렬 알고리즘에서, 각 원소가 자신의 최종 위치에 도달하기 전 자신보다 큰 원소와 교환한 횟수를 의미합니다. 다른 이름으로는 레머 코드(...

7주차 계획 개요 7주차(2. 12 ~ 2. 18)의 계획입니다. 24장 구간 트리 서론 문제: MORDOR 문제: FAMILYTREE 문제: MEASURETIME 25장 상호 배타적 집합 서론 문제: EDITORWARS 26장 ...

문제 정의 및 문제 설명 집합 $S$에 속하는 $n$개의 순서쌍$(p_i, q_i)(i = 1, \ldots, n)$ 가 주어지고, 서로 다른 순서쌍끼리는 $p$ 값과 $q$ 값이 서로 같지 않다고 가정합니다. 즉, 임의의 $i \neq j$에 대해 $p_i \neq p_j \quad \text{and} \quad q_i \neq q_j$ 가 성립합...

문제 $n (1 \leq n \leq 100)$개의 원형 장벽이 주어질 때, 최대 성벽을 몇 번이나 넘어야 하는지 구하시오. 맨 처음 큰 장벽이 주어지고, 나머지 $n-1$개의 장벽은 첫 장벽 안에 포함된다. 장벽은 서로 겹치고, 닿지 않는다. 문제 링크 서론 문제를 Tree Diameter Problem로 변환하고, Tree Diamet...

문제 문자열 $s$가 주어지면, $s$의 $substring$ $k$번 이상 등장하는 $substring$의 최대 길이를 구하시오. $k$번 이상 등장하는 $substring$이 존재하지 않으면, $0$을 출력한다. 문제 링크 서론 문자열 문제를 풀기 위한 접미사 배열(suffix array)을 배우고 이것에 대한 장점. 접미사 배열을 만드...

문제 길이가 최대 10,000인 문자열이 N+1(1 ≤ N ≤ 100) 개 주어진다. 각 문자열은 다이얼의 상태를 나타내며, 서로 다른 순서로 정렬된 문자의 집합이다. 초기 상태에서 시작하여, 주어진 순서대로 문자열을 맞추기 위해 오른쪽(시계 방향) 또는 왼쪽(반시계 방향) 회전을 수행할 수 있다. 목표는 주어진 순서대로 다이얼을 맞추기 위해 수...