Leetcode: Longest Increasing Subsequence (LIS: 최장 증가 부분 수열)
Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7]. Example 1: Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest inc..
Leetcode : Subsets
Subsets I Given an integer array nums, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Example 1: Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] Example 2: Input: nums = [0] Output: [[],[0]] 중복이 없는 array의 모든 부분집합을 구하는 문제이다. 아래에 소개한 방법처럼 recursive하게 풀 수도 있겠으나, 배열에 중복이 없으므로 각 원소는 각 부분집합에 속하는가/속하지 않는가의 두 가지 가능성밖에 없고, 결론적으로 ..
Leetcode: Kth largest element in an Array
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. Example 1: Input: [3,2,1,5,6,4] and k = 2 Output: 5 Example 2: Input: [3,2,3,1,2,4,5,5,6] and k = 4 Output: 소팅되지 않은 배열에서 k번째로 큰 수를 찾는 문제이다. 가장 쉽게 떠오르는 방법은 배열을 소팅해서 끝에서 k번째 element를 찾는 것이다. 길이 N짜리 배열을 소팅하므로 time complexity는 O(nlogn)이다. class Solution: def f..
