소개 1차원 배열이 주어졌을 때, 연속된 구간의 최대 합을 구하는 알고리즘을 카데인 알고리즘이라고 한다. 예를 들어 다음 배열이 있다면, [-2, 1, -3, 4, -1, 2, 1, -5, 4] 연속된 구간 [4, -1, 2, 1]의 합인 6이 가장 크다. 카데인 알고리즘은 앞에서 계산한 결과를 재활용하여 배열을 한 번만 순회한다. 따라서 시간 복잡도 O(n), 공간 복잡도 O(1)로 문제를 해결할 수 있다. 아이디어 현재 원소에서 끝나는 연속 구간의 최대 합을 유지하고 다음 원소를 만났을 때 기존 구간을 이어가는 것과 현재 원소부터 새로운 구간을 시작하는 것 중 더 큰 값을 선택한다. ...
소개 수열의 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크면서, 가장 긴 길이를 가지는 부분 수열을 찾는 알고리즘 DP 방식과 Binary Search를 쓰는 Greedy 방식 두 가지가 있으며, 별개의 방식이 아닌 두 방식이 밀접하게 연관되어 있다. 아이디어 LIS는 현재까지 구한 부분 수열의 결과를 이용해 더 긴 부분 수열을 만들어 나가는 문제이다. DP는 이전 계산 결과를 이용해 현재 상태를 구하며, Binary Search를 이용한 방식은 같은 아이디어를 유지하면서 탐색 과정을 최적화한 것이다. ...
소개 두 문자열이 있을 때, 가장 긴 공통 부분 문자열을 찾아내는 알고리즘, 부분 문자열이란 원소들이 원래 순서를 유지하면서 일부 원소를 생략할 수 있는 형태를 말함 예시: 문자열 A: A**B**CB**DAB** 문자열 B: **BD**C**AB**B A와 B의 LCS는 BDAB라고 할 수 있다. 아이디어 2차원 배열을 통해 중간 결과를 메모이제이션 한다. 이 배열은 두 문자열의 길이에 따라 결정된다. 알고리즘 편의상 첫 번째 열과 행은 0으로 초기화 한다. 빈 문자열과 비교했을 때의 경우를 처리할 수 있다. - A B C B D A B - 0 0 0 0 0 0 0 0 두 번째 문자열의 문자를 차례대로 가져와 비교한다. - A B C B D A B - 0 0 0 0 0 0 0 0 B 0 0 1 테이블의 각 원소는 그 시점의 substring간의 LCS를 의미한다. 즉 위 표에서 1인 원소는 substring “AB”와 “B”의 LCS의 길이가 1임을 의미한다. 앞선 결과를 기반으로 LCS의 크기를 계산한다. - A B C B D A B - 0 0 0 0 0 0 0 0 B 0 0 1 1 B와 C는 같지 않더라도, “ABC”와 “B”를 비교하는 것과 같으므로, 이전에 “AB”와 “B”를 비교한 값인 1이 유지된다. 만약 두 문자가 다른 경우 - A B C B D A B - 0 0 0 0 0 0 0 0 B 0 0 1 1 1 1 1 1 D 0 0 1 B와 D는 다르지만, “AB”와 “BD”의 LCS의 길이는 1이다. 3번의 경우와 합쳐서 두 원소가 다르지 않을 때, DP 테이블을 채우는 점화식을 세울 수 있다. dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) 두 문자가 같은 경우 - A B C B D A B - 0 0 0 0 0 0 0 0 B 0 0 1 1 1 1 1 1 D 0 0 1 1 1 2 두 문자가 같은 경우, 즉 위 표의 상황에서는 “ABCBD”와 “BD”의 LCS의 크기를 구하는 경우가 된다. 이 경우는 “ABCB”와 “B”의 LCS의 크기에서 원소 “D”가 더해진 것과 같으므로, 대각선 위에 있는 값에서 1을 더한 값이 된다. dp[i][j] = dp[i - 1][j - 1] + 1 동작 원리 DP 테이블을 채우면서 두 문자가 다른 경우 이전에 계산한 결과를 그대로 유지한다. 두 문자가 같은 경우 그 문자가 없는 경우의 LCS의 크기에서 1을 더한다. 점화식 if (A[i - 1] == B[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1 } else { dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1]; } 기타 길이와 실제 문자열 DP 테이블의 마지막 값인 dp[m][n]은 LCS의 길이만 나타낸다. ...