알고리즘

[LeetCode] Longest Common Subsequence (Java)

✉️문제 https://leetcode.com/problems/longest-common-subsequence/description/ Longest Common Subsequence - LeetCode Can you solve this real interview question? Longest Common Subsequence - Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0. A subsequence of a string is a new string genera leetcode.com 🗝 문제풀이 2차원 배열을 ..

[LeetCode] Longest Increasing Subsequence (Java)

✉️문제 https://leetcode.com/problems/longest-increasing-subsequence/description/ Longest Increasing Subsequence - LeetCode Can you solve this real interview question? Longest Increasing Subsequence - Given an integer array nums, return the length of the longest strictly increasing subsequence. Example 1: Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest leetcode.com 📝 접근 1. 다이..

[LeetCode] Non-overlapping Intervals (Java)

✉️문제 https://leetcode.com/problems/non-overlapping-intervals/description/ Non-overlapping Intervals - LeetCode Can you solve this real interview question? Non-overlapping Intervals - Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping. leetcode.com 🗝 문제풀이 겹치는 부분을 최소화..

[알고리즘] 카데인 알고리즘

카데인 알고리즘 DP(Dynamic Programming)기법 중 하나로 연속적인 수의 나열에서 최대합 또는 곱을 구하는데 사용된다. 아이디어 [-2, 3, -1, 2]의 숫자가 있다. 이 배열에서 최대 부분합을 구해보자. [-2, 3, -1, 2]의 최대 부분합을 구하기 위해서는 [-2, 3, -1]의 최대 부분합을 알아야 한다. 이를 알기 위해서는 [-2, 3]의 최대 부분합을 알아야 한다. 마지막으로 [-2]의 최대 부분합을 알아야 한다. 이렇게 큰 집합을 작은 부분 집합으로 나누어서 풀이해 정복하는 DP 기법을 이용한다. 슈도 코드 function kadaneAlgorithm(nums) { var curSum = 0, max = INT_MIN // i = 1 부터 nums.length - 1까지 ..

[알고리즘] 버킷 정렬

[Bucket Sort (버킷 정렬)] 버킷 정렬은 N개의 버킷으로 나눈 뒤, 각 버킷 안에 하나 이상의 값을 저장한다. 예를 들어보어 사과(2개), 배(2개), 망고(3개), 수박(1개) 총 8개의 과일이 있다고 가정해보자. 버킷 정렬에서는 다음과 같이 과일의 정보를 저장한다. 숫자 범위를 기준으로 버킷의 정렬 순서를 정할 수도 있다. 예를 들어 29, 25, 3, 49, 9, 37, 21, 43 이라는 숫자가 있으면 이를 10단위로 나누어 관리할 수 있다. [구현] 두 번째 예시를 기준으로 의사 코드를 작성하면 다음과 같다. function bucketSort(array, k) buckets ← N 크기의 빈 배열을 선언한다. M ← 가장 큰 숫자를 M으로 선언한다. for i = 1 to lengt..