thisisuser's study

일단 시간복잡도는 제껴두고, 이 문제를 풀어봅시다.13323번: BOJ 수열 1 (acmicpc.net)  만약 $N \le 10000$ 정도라면, 약간의 관찰을 통한 간단한 $O(N^{2})$ DP를 통해 해결할 수 있습니다.대충 '$DP(x, k) = x$번째 값을 $k$로 만들었을때 최소 연산 어쩌구' 꼴로 구성해주고,$DP(x, k) = \min (1 \le i \le k - 1) DP(x-1, i) + |a[x] - k| $ 이라 정의하여 간단히 해결할 수 있습니다. 하지만 만약 $N$이 무지막지하게 커져서, 한 $10^{6}$ 쯤 된다고 해봅시다.그러면 당연히 시간 내에 풀 수 없을 것입니다. 물론 그 전에 메모리가 터지겠지만요. 문제를 해결하기 위해서는 DP(x, k)를 k에 따른 함수로 해..

DP를 활용하는 대표적인 문제로 LCS(Longest Common Sequence)가 있습니다.시간복잡도 $O(N^{2})$, 공간복잡도 $O(N^{2})$로 해결하는 풀이가 가장 일반적입니다. 그렇다면 다음 문제를 봅시다.https://www.acmicpc.net/problem/18438 18438번: LCS 5LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.www.acmicpc.net문자열의 길이가 7000 이하이니 시간 복잡도는 문제될 게 없습니다만,공간 복잡도가 비정상적으로 줄어버리며 난이도가 확 올라갔습니..

문제 링크 Codeup: 5313 잔디밭의 개미굴 고등3) KOI 공원의 잔디밭에는 여러 개미가 모여 사는 개미굴이 있다. 개미굴은 $N$ 개의 방으로 구성되어 있으며, 서로 다른 두 개미굴을 직접 잇는 $N - 1$ 개의 통로가 있고, 임의의 서로 다른 두 codeup.kr Baekjoon: 28328 28328번: 잔디밭의 개미굴 KOI 공원의 잔디밭에는 여러 개미가 모여 사는 개미굴이 있다. 개미굴은 $N$ 개의 방으로 구성되어 있으며, 서로 다른 두 개미굴을 직접 잇는 $N - 1$ 개의 통로가 있고, 임의의 서로 다른 두 개미굴 www.acmicpc.net 문제 선정 과정 먼저 문제가 굉장히 길었다. 대략적으로 요약하면 다음과 같다. 트리 구조의 그래프가 주어지고, 각 노드는 0 또는 1의 데이..