siino's 개발톡

더보기 시간 복잡도를 줄여야하는 문제 아이디어를 찾아서 해결 해야하는 문제 꼭 손으로 그려보면서 규칙성을 찾기 문제를 보고 처음에는 각 차례에서 밑장빼기를 하는 경우를 재귀로 구현하여 풀어보면 어떨지 생각했다. 하지만 주어진 N의 범위는 10만. 따라서 모든 경우의 수를 재귀로 구현하면 시간복잡도는 O(N^2)이 된다. (N개 중 밑장빼기를 할 index 찾기 * 원소 순회하면서 누적합 계산) O(N) * O(N) 따라서 시간복잡도를 줄여야 했고, 다른 방법을 생각하게 되었다. 이렇게 아이디어를 필요로 하는 문제들을 푸는 과정은 직접 손으로 그려라!! 밑장 빼기 하는 숫자는 맨 마지막 원소이므로 고정. 밑장 빼기를 하면 맨 마지막 원소를 다른 index에 삽입하여 홀수번째/짝수번째 index를 나눠서 누..

https://www.acmicpc.net/problem/9251 [9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net](https://www.acmicpc.net/problem/9251) 문제해결과정 최장 공통 부분 수열 2개의 문자열이 주어지고 두 문자열의 공통 부분 문자열 중, 가장 긴 것의 길이를 구하는 문제. 각 문자열의 i번째, j번째 문자를 포함을 시키거나 포함하지 않는 공통 부분 문자열의 길이를 구한다. 유명한 dp문제이다. dp테이블은 dp[i][j] ..