이번 글에서는 `LCS(Longest Common Subsequence)` 알고리즘에 대해 정리하려고한다. Longest Common Substring도 있지만 이번 글에서는 `Longest Common Subsequence`만 다룰 예정이다. 먼저, `LCS(Longest Common Subsequence)`가 무엇인지 알아보자 What is LCS(Longest Common Subsequence)?`LCS(Longest Common Subsequence)`란 다음과 같다. 두 개의 문자열에서 순서를 유지하면서 일부 문자를 선택해 만들 수 있는 가장 긴 공통 부분 수열  예를 들어, 다음과 같은 문자열이 있다고 가정해보자 String A: ACDBEString B: ABCDE 이 두 문자열의 `LCS`..

난이도: EasyProblem DescriptionYou are given a 0-indexed array nums of size n consisting of non-negative integers. You need to apply n - 1 operations to this array where, in the ith operation (0-indexed), you will apply the following on the ith element of nums:If nums[i] == nums[i + 1], then multiply nums[i] by 2 and set nums[i + 1] to 0. Otherwise, you skip this operation.After performing all the ..

What is Kadane's Algorithm? `Kadane's Algorithm`은 다음과 같다. 연속 하는 부분 배열의 최대 합을 효율적으로 찾는 알고리즘  즉, 주어진 배열에서 연속된 요소들의 부분 배열 중 가장 큰 합을 가지는 부분 배열을 찾는 알고리즘이다. 이 알고리즘은 `동적 계획법(Dynamic Programming, DP)`을 활용하여 문제를 해결하며 `O(N)`의 시간 복잡도를 갖는다.  Kadane's Algorithm 동작 원리`Kadane's Algorithm`의 동작 원리는 다음과 같다. 현재 위치까지의 최대 부분합을 저장하는 `local_max` 변수를 유지한다.`local_max`는 `max(nums[i], nums[i] + local_max)`를 통해 계속 큰 값으로 갱신..

난이도: HardProblem Description Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If there are multiple valid strings, return any of them. A string s is a subsequence of string t if deleting some number of characters from t (possibly 0) results in the string s. Problem ExampleExample 1:Input: str1 = "abac", str2 = "cab"Output: "cabac"Explanatio..

난이도: MediumProblem DescriptionA sequence x1, x2, ..., xn is Fibonacci-like if:n >= 3xi + xi+1 == xi+2 for all i + 2 Given a strictly increasing array arr of positive integers forming a sequence, return the length of the longest Fibonacci-like subsequence of arr. If one does not exist, return 0. A subsequence is derived from another sequence arr by deleting any number of elements (including none)..

난이도: MediumProblem Description You are given an integer array nums. The absolute sum of a subarray [numsl, numsl+1, ..., numsr-1, numsr] is abs(numsl + numsl+1 + ... + numsr-1 + numsr). Return the maximum absolute sum of any (possibly empty) subarray of nums. Note that abs(x) is defined as follows:If x is a negative integer, then abs(x) = -x.If x is a non-negative integer, then abs(x) = x. Probl..