Algorithm/문제풀이

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

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

❐ Description문제링크https://leetcode.com/problems/longest-consecutive-sequence/description/난이도medium(골드3~2)     ❐ 문제 분석주어진 배열에서 가장 긴 연속되는 요소의 길이를 구하는 문제이다.중복되는 숫자는 제외해야 하며, `O(n)`의 시간 복잡도로 구현해야 한다.     ❐ 문제 풀이1. 시간 복잡도 `O(NlogN)`정렬을 사용해서 풀이할 수 있는 방법이다. 물론 문제의 요구사항인 시간복잡도 보다 크지만,문제 제약 조건이 허술해서 이 방법으로도 풀이는 된다.public int longestConsecutive(int[] nums) { Arrays.sort(nums); int maxLength = -1; ..

❐ Description문제 링크Koko Eating Bananas난이도medium / Gold 4~3     ❐ 문제 분석 및 접근 piles : 바나나 더미h : 가드가 자리를 비우는 시간k : 원숭이가 한 시간동안 먹을 수 있는 바나나 갯수 int[] piles = {10, 13, 34, 55}예를 들어 위와 같은 경우에, 원숭이가 시간당 먹을 수 있는 바나나의 갯수(k)가 15라면 원숭이가 모든 바나나 더미를 다 먹는데 걸리는 시간은 아래와 같을 것이다.‣ 10개 - 1시간‣ 13개 - 1시간‣ 34개 - 3시간‣ 55개 - 4시간  원숭이가 먹을 수 있는 최소 바나나 갯수는 1개이고 최대 바나나 갯수는 piles 중 가장 큰 수이다.⇨ 정답 k는 이 사이에 존재한다. 그리고 위의 예시에서 `k ..

❐ Description[1631. Path With Minimum Effort] 문제를 다시 풀었는데 제대로 풀지 못해서 정리한다.     ❐ 접근 방식 (Binary Search)여기서는 Mid 값일 때 움직일 수 있는 경로만 움직이는 것이 핵심 포인트다. lowerEffort, upperEffort를 각각 설정한다.최소 : 0최대 : 1_000_000lowerEffort가 upperEffort 보다 작을 때만 while문을 수행한다.시작점으로 부터 좌,우,위,아래를 순회하는데Mid 값보다 작거나 같은 경우에만 이동할수 있다.목표 지점에 도달했는지 확인한다.도달하지 못함 ⇨ 현재 Mid 값으로 부족 ⇨ 더 큰 Mid 값이 필요 ⇨ lower = mid;도달 함 ⇨ 현재 Mid 값으로도 충분 ⇨ 최소..