https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/ Find Minimum in Rotated Sorted Array - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 핵심 아이디어 문제 조건이 O(logN)으로 찾으라고 되어 있으니 binary search를 사용한다 정렬된 array를 rotate해서 binary search를 응용할 수 있다 정렬이 안 맞기 시작하는 지점이 최솟값이니 정렬..
Problem Solving
https://leetcode.com/problems/maximum-product-subarray/ Maximum Product Subarray - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 핵심 아이디어 (n-1)번째 local max 와 연산해서 n번째 local max를 구할 수 있으므로 DP. 그러나 (n-1)번째 지역해만을 사용하기 때문에 배열은 만들지 않고 localMin, localMax 변수 2개로 지역해를 트래킹했다 정수를 곱하면 절댓값이 커..
https://leetcode.com/problems/maximum-subarray/ Maximum Subarray - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 핵심 아이디어 Sliding Window 지금까지 구했던 prefix sum이 음수이면 더하는게 의미가 없으므로 값을 누적할 때 버린다 복잡도 시간 복잡도: O(n) 배열 1회 순회 공간 복잡도: O(1) 저장하는 변수 외에 추가적으로 사용하는 메모리 없음 설명 알고리즘을 개선해 가는 해설이 재미있..
https://leetcode.com/problems/product-of-array-except-self/ Product of Array Except Self - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 핵심 아이디어 result[i]의 값은 왼쪽 부분(prefix)의 곱과 오른쪽 부분(postfix)의 곱을 곱한 것이다 prefix[i]와 postfix[i] 는 각자 이전 값에다 nums[i]를 곱하면 되기 때문에 O(1) 시간에 구할 수 있다 resul..
https://leetcode.com/problems/contains-duplicate/ Contains Duplicate - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 핵심 아이디어 hashSet `has()`로 이전에 나왔던 값인지 1회당 O(1) 시간에 찾기 복잡도 시간 복잡도: O(n) hashSet.has() O(1) * n개 원소 공간 복잡도: O(n) hashSet()에 n개의 데이터를 저장하는 데 드는 공간 설명 배열 안에 중복된 요소가 있는지..
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/ Best Time to Buy and Sell Stock - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 핵심 아이디어 Sliding window - left, right pointer(index) 이용하여 지역값 구하고, 저장된 max와 비교. 매번 right pointer를 움직이지만, profit 조건이 깨지면 left = right로 초기화 ..
https://leetcode.com/problems/two-sum/ Two Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 핵심 아이디어 value: index HashMap을 만들어서 pair(target - num)의 index를 1회당 O(1)에 찾기 배열 탐색과 동시에 hash map 초기 복잡도 시간 복잡도: O(n) 1차원 배열 탐색, hashMap 초기화 O(n) * hashMap get O(1) 공간 복잡도: O(n) 1차원 hashMa..