Algorithm

❐ Description1. Requests주어진 두 문자열의 겹치는 subsequence 중 가장 긴 문자열의 길이를 반환하라.겹치는 부분이 없다면 0을 반환하라. 두 문자열의 순서를 유지한 채 공통으로 존재하는 가장 긴 부분 수열을 찾는 것 2. Constrains`1 제약 조건에 의하면 시간복잡도는 최대 O(n²)까지는 괜찮다.     ❐ Approach  1 - 2D memoization (Bottom - Up)class KtSolutionV1 { fun longestCommonSubsequence(text1: String, text2: String): Int { val maxRow = text1.length val maxCol = text2.length ..

❐ Description[LeetCode#1143. Longest Common Subsequence]를 풀면서 학습한 LCS 알고리즘 정리 *참고 블로그 : [알고리즘] 그림으로 알아보는 LCS 알고리즘    ❐ Longest Common Subsequence란?우선 Longest Common Subsequence의 의미를 이해하자.LCS란 두 문자열의 순서를 유지한 채 공통으로 존재하는 가장 긴 부분 수열을 찾는 것이다.부분 수열이기 때문에, 주어진 문자열에서 순서만 유지하면 몇 개든 건너 뛰어도 된다.Longest Common Substring이란?주어진 문자열에서 순서를 유지한 채 공통으로 존재하는 연속된 문자를 찾는 것     ❐ 점화식 이해하기1. 두 문자가 동일한 경우//text1[i - 1]..

❐ Description문제 링크https://leetcode.com/problems/3sum/description/난이도Medium(골드Ⅴ~Ⅲ)     ❐ 문제 분석주어진 `nums[]`에서 서로 다른 세 수의 합이 0이 되는 조합을 찾아야 한다.  🧩 Step 1. Two Pointer를 사용하기세 숫자의 합을 찾는 대신, 첫 번째 숫자를 기준으로 나머지 두 숫자를 Two-Pointer 방식으로 탐색한다. 🧩 Step 2. 주어진 nums[] 정렬하기배열을 오름차순으로 정렬해준다. 이는 Two Pointer 방식을 효율적으로 사용하기 위함이다.  🧩 Step 3. 중복 방지하기같은 숫자가 여러 번 사용되면 결과에 중복된 조합이 포함되므로 이를 방지해야 한다.같은 숫자를 연속적으로 사용할 경우 이..

❐ Description[LeetCode#274] HIndex를 풀면서 Counting Sort를 알게 됐다. 이를 직접 구현해보자!     ❐ 특징시간 복잡도최선, 평균, 최악 모구 O(n+k)n : 정렬할 데이터의 개수k : 데이터 값의 범위비교 기반이 아님데이터를 비교하지 않고, 데이터의 출현 횟수만 이용하여 정렬한다.안정정렬데이터의 순서를 유지하며 정렬한다.한계점데이터 범위가 크면 비효율적이다.정수 또는 정수로 변환 가능한 데이터에만 사용할 수 있다.부동소수점이나 복잡한 객체에는 적합하지 않다.     ❐ 순서대로 구현해보기Step1. 주어진 배열의 요소 중 최댓값 찾기int maxElement = Arrays.stream(nums).max().getAsInt();  Step2. 길이가 `최대값 ..

❐ Description문제 링크https://leetcode.com/problems/maximum-product-subarray/description/난이도Medium      ❐ 문제 분석이 문제는 배열 내 음수, 0, 양수의 특성을 고려해야 하기 때문에 단순히 한 번의 반복으로 최대값을찾을 수 없다. 대신 DP를 사용하여 최대값과 최소값을 동시에 추적하여 풀이해야 한다. 그럼 왜 최소값도 추적해야 할까? 음수가 곱해질 경우, 최소값이 최대값으로 변할 수 있기 때문이다.예를들어, `[-2, 3, -4]`에서는`-2`를 시작으로 음수를 만나면 곱셈 결과가 양수가 된다.따라서 현재 최소값을 함께 고려해야 최대값을 얻을 수 있다.     ❐ 문제 풀이1. Dynamic Programmingpublic cl..

❐ Description문제 링크https://leetcode.com/problems/longest-increasing-subsequence/description난이도Medium     ❐ Dynamic Programming나의 경우 주어진 nums 배열을 거꾸로 순회하면서 풀이하는 방식으로 접근했다.우선 memo 배열은 1로 초기화해주었다. 왜냐면 최소 길이가 1 이기 때문이다. 작동 방식은 다음과 같다.// 1. idx = 7int target = nums[7] = 18최대 길이는 18 자신이므로 1// 2. idx = 6int target = nums[6] = 101101 다음 숫자가 18로, 101 보다 작기 때문에 현재 위치에서 최대 길이는 1// 3. idx = 5int target = num..

❐ Description문제링크https://leetcode.com/problems/reverse-words-in-a-string/description난이도Medium (골드5) 이번 문제는 어떤 방식으로 푸느냐에 따라 개인적으로 느끼는 난이도에 차이가 있는 문제 같다.기본적으로 제공해주는 메서드(trim, replaceAll)를 사용하면 비교적 간단하게 해결할 수 있다.하지만, 면접에서 기본 메소드를 사용하지 말고 위 문제를 해결하라고 하면 어떻게 해야할지생각해봐야 한다.     ❐ 문제 분석문제를 요약하자면,문장을 거꾸로 뒤집어라.앞뒤에 공백이 와서는 안된다.문자 사이에 공백은 하나여야 한다.주어진 문자열의 길이 : `1 영어 대소문자, digits, 공백으로 이루어짐적어도 하나의 단어가 있음.   ..

❐ Description문제 링크https://leetcode.com/problems/house-robber/description/난이도Medium(실버2~1)최초에 DFS로 풀이를 했었는데 Time Limit Exceed가 발생했다. 이 문제를 해결하는 과정에서 Memoization을다시 제대로 학습하게 됐으며, 이 문제를 시작으로 보다 다양한 DP 문제를 풀어봐야겠다.     ❐ Solutions1. Reculsive Ⅰ - Time Limit Exceedpublic class Solution { private int answer = 0; public int rob(int[] nums) { for (int i = 0; i nums.length - 1) { ..