문제 문자열 $k(1 \leq k \leq 15)$개를 입력을 받아서, 해당 문자열을 한 줄로 모두 포함하는 가장 짧은 문자열 하나를 출력합니다. $length(k):1 \leq k \leq 40$ 문제 링크 서론 이번에는 입력이 문자열 여러 개인 경우에 대해서 Dynamic programming을 적용해보려고 합니다. 알고리즘 구상 문...

문제 최대 15자리 정수 $e$와 정수 $k(2 \leq k \leq 20)$가 주어졌을때, $e$의 각 자리를 바꾼 $e’$의 개수를 세는 문제입니다. $e’$는 다음과 같은 조건이 있습니다. $e’ < e$ $e’ \mod k = 0$ 문제 링크 서론 이번에는 입력이 순열인 경우에 대해서 Dynamic programming...

문제 중복되는 $LIS$ (Longest Increasing subsequence) 중, 사전 순으로 정렬했을 때 중복되는 $k$번째의 $LIS$를 구하는 문제입니다. 문제 링크 서론 지금까지 DP를 이용하여 최댓값이나 최솟값을 구하는 문제를 풀어보았습니다. 하지만, 최댓값이나 최솟값이 아닌 k번째의 답을 계산하는건 어떨까요? 이럴 때에도 ...

문제 문제 링크 알고리즘 구상 Dynamic Programming 이 문제는 어떤 문장을 단어별로 인식한 결과가 주어졌을 때, 원본일 조건부 확률이 가장 높은 문장을 찾아내는 프로그램을 작성하는 프로그램입니다. Dynamic Programming을 이용해서 이를 풀 것입니다. 알아둘 것 문장 R이 주어질 때 조건부 확률 $P(Q|R)$을 최대...