Algorithms (28) 썸네일형 리스트형 [Baekjoon]11053.가장 긴 증가하는 부분수열(DP) Baekjoon #11053. 가장 긴 증가하는 부분 수열http://www.acmicpc.net/problem/11053 이 문제는 Longest Increasing Subsequence(LIS)로 유명한 문제라고 한다. 그 동안 풀었던 문제와는 다른 유형인 것 같아서 아이디어가 떠오르지 않았는데 유튜브에서 영상을 보고 바로 이해가 되어 풀 수 있었다. 이 영상이 도움이 되었다. 영상에서 설명한 방법은 시간복잡도가 O(n^2) 이다. 그런데 n이 100,000 이상일때는 이 방법으로 풀 수 없다. 시간 복잡도 O(nlogn) 인 방법이 있는데 이번 포스팅에서는 먼저 O(n^2)인 방법으로 풀고 이후에 따로 O(nlogn) 방법을 공부하여 포스팅 해야겠다. 먼저 배열 d를 정의하면 d[n] : 수열 a에.. [Baekjoon]9465.스티커(DP) Baekjoon #9465. 스티커http://www.acmicpc.net/problem/9465 처음에 문제를 보고 완전탐색으로 풀 수 있겠다고 생각했지만 알고리즘 분류에 DP로 되어 있어서 DP로 풀기로 했다. 완전탐색으로 풀어보고 비교해봐야겠다. 일단 DP를 이용해서 풀자. 문제에서 모서리를 공유하며 인접한 스티커는 뗄 수 없다고 했다. DP로 풀기 위해 N번째 열의 상태와 N-1번째 열의 상태를 비교하며 어떤 관계가 있는지 알아야 한다. 이렇게 스티커를 열로 분해하는 아이디어가 중요한것 같다. 먼저 스티커는 2Xn 이고 N번째 열이 표와 같은 상태일때 N-1번째에 올 수 있는 상태는 다음과 같다.(같은 행에 OO가 올 수 없음.)점화식을 세우기 위해서 배열 d를 정의한다. d[N][k] : 스티커.. [Baekjoon]2193. 이친수(DP) Baekjoon #2193. 이친수 http://www.acmicpc.com/problem/2193 개인적으로 오르막수나 쉬운 계단 수 문제보다 훨씬 쉽다고 생각했다. 이미 앞에 두 문제를 어떻게 접근하는지 알고 있어서 그런 것일 수도 있겠지만 코드 자체도 훨씬 간단하고 이해하기도 쉬웠다. 이 문제도 마찬가지로 배열d를 정의한다. d[N][k] : N자리 k로 끝나는 이친수 개수 (k=0, 1) 이 문제는 k에 올 수 있는 수가 0 또는 1 두 가지 경우이므로 생각해보기가 더 쉬웠다.먼저 N=1 일때 이친수는 0으로 시작할 수 없다고 했으므로 d[1][1] = 1 , d[1][0] = 0 으로 정의된다. 2자리부터 차근차근 생각해보면 다음과 같다. 1이 연속으로 나오면 안되기 때문에 1로 끝나는 N-1자.. [Baekjoon]11057.오르막수(DP) Baekjoon #11057. 오르막수 http://www.acmicpc.com/problem/11057 DP의 대표적인 문제로 쉬운 계단 수 문제랑 비슷한 방식으로 접근하면 될 것 같았다.먼저 쉬운 계단수 문제에서 힌트를 얻어 오르막수의 경우의 수를 저장할 배열 d를 다음과 같이 정했다. d[N][L] : N자리 수 중에서 L로 끝나는 오르막 수 개수 예를 들어 d[3][5]는 3자리수 중에서 일의 자리가 5로 끝나는 오르막수, 즉 ＿ ＿ 5 의 형태를 가진 오르막수의 경우의 수다. 생각을 해보면 5 앞에 두 자리 오르막수 중에서 마지막 자리가 5로 끝나는 오르막수가 오면 세자리가 된 그 수 또한 오르막 수가 된다.이것을 점화식으로 쓰면 d[3][5] = d[2][0] + d[2][1] + d[2][2.. 이전 1 2 3 4 다음
