DP

난이도: MediumProblem DescriptionGiven an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise. Problem ExampleExample 1:Input: nums = [1,5,11,5]Output: trueExplanation: The array can be partitioned as [1, 5, 5] and [11].Example 2:Input: nums = [1,2,3,5]Output: falseExplanation: The array cannot..

난이도: MediumProblem DescriptionYou are given a 0-indexed 2D integer array questions where questions[i] = [pointsi, brainpoweri]. The array describes the questions of an exam, where you have to process the questions in order (i.e., starting from question 0) and make a decision whether to solve or skip each question. Solving question i will earn you pointsi points but you will be unable to solve ea..

이번 글에서는 `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`..

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)..