서론 문제 설명 $G = (V, E)$에서, 각 Vertex를 $v_i$라 할 때, $v_0$부터 $v_{n-1}$까지의 path들 중, path를 이루는 edge의 최대/최소 weight 차이의 최솟값을 구하시오. 문제 링크 문제 유형 최소 범위 경로(Minimum Range Path) 문제를 풀어봅시다. 최소 범위 경로란? 최소 범위 경로 문...

9주차 계획 개요 9주차(2. 26 ~ 3. 4)의 계획입니다. 30장 최단 경로 알고리즘 서론 문제: ROUTING 문제: FIRETRUCKS 문제: NTHLON 문제: TIMETRIP 문제: DRUNKEN 문제: PROMISES 31장 최소 ...

서론 문제 설명 팀 $n(1 \leq n \leq 100)$개가 회의가 되는 시간대가 각각 $2$개 주어집니다. 팀끼리 겹치지 않게 시간대를 조정하시오, 각 팀당 회의는 무조건 한 번 해야합니다. 한 팀이라도 회의가 불가능할 경우, 불가능함을 보이시오. 문제 링크 문제 유형 2-SAT 문제로 변형해서 2-SAT문제를 함의 그래프(Implicat...

서론 문제 설명 단어 $n(1 \leq n \leq 100)$개가 주어져 단어의 끝 문자와 다음 단어의 첫 문자가 같게 연속적으로 말해야 합니다. 단어들을 전부 사용해서 말할 수 있으면 어떤 순서로 단어를 사용해야 하는지 출력하고, 사용할 수 없으면, IMPOSSIBLE을 출력합니다. 문제 링크 문제 유형 DFS를 활용하여 오일러 경로(Eule...

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