leetcode30 leet code 167 - Two Sum II - Input Array is Sorted 리트 코드의 첫문제인 two sum 과 거의 같은 문제.. 뭐가 다른거지? class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: l, r = 0, len(numbers) - 1 while l target: r -= 1 elif curSum < target: l += 1 else: return [l + 1, r + 1 ] 해쉬맵으로 풀 수 있다. 왜 해쉬 맵을 쓰는가? 문제는 간단하다. 배열을 전부 순회하며 타겟값을 만드는 조합을 찾는 브루트 포스의 방법이 있다. 하지만 이는 N2의 시간 복잡도를 지닐뿐더러 매우 비효율적이다. .. 2023. 4. 21. leet code 33 - Search in Rotated Sorted Array 문제 자체의 난점은 log 시간 안에 풀수 있느냐에 있다. 정렬된 리스트, log의 시간, 중복 없는 고유 리스트. 이진탐색 응용으로 풀 수 있는 문제이다. 문제의 해설을 잘 읽어보면 연속적인 리스트의 최우단을 최 좌단으로 순환 시킨다. 즉 pivot. 이산되는 구간이 발생한다. 그리고 이산되는 구간에서는 오름차순의 배열 두개가 생기는 것과 마찬가지이다. 그리고 항상 왼쪽의 배열이 오른쪽의 배열보다 크다. 알다시피 이진 탐색의 포인터는 세개. l, m, r이다. 먼저 tartget 값이 m과 같다고 해보자. 그러면 그대로 인덱스를 반환하면 된다. 만약 m이 왼쪽의 이산되는 구간에 있다고 해보자. 그리고 target 값이 m 보다 크다고 해보자. 이미 m의 왼쪽에서는 target 값이 없다는 것을 알 고 .. 2023. 4. 17. leet code 153 - Find Minimum in Rotated Sorted Array 이진 탐색의 변형 문제이다. 볼 수 있는 키워드는 일단 고유값, 오름 차순의 정렬. log n의 시간 복잡도, 최소값의 탐색 하지만 rotate돼 있고 , 특정값이 주어지는게 아닌, 임의의 최소값을 찾는 문제이기 때문에 일반적 이진탐색 문제는 아님을 알 수 있다. 아래는 기본 이진탐색 알고리즘이다. def binary_search(arr, target): left = 0 right = len(arr) - 1 while left int: #최소값을 구하라. 제약조건 log n #최소값이 리스트 맨 뒤에 있다면? res = nums[0] l, r =0, len(nums) - 1 while l = nums[l]: l = m + 1 else: r = m - 1 return res 일단 l, r을 포인터로 선언해.. 2023. 4. 17. Leet code 152 - Maximum Product Subarray 기가 막힌 문제다.. 53번 최대 부분합 문제의 응용버전이다. 1. s와 e의 범위를 조정하는 최악의 브루트포스 def maxProduct(self, nums:List[int]) -> int: max_prod = nums[0] for s in range(len(nums)): for e in range(s, len(nums)): prod = 1 for i in range(s, e + 1): prod *= nums[i] max_prod = max(prod, max_prod) return max_prod for 문으로 시작인덱스와 끝 인덱스를 정해준뒤 , 요소 하나하나 전부 순회하며 곱해준다. O(n^3) 2.인덱스를 정해주지 않고 누적으로 계속 곱해가는 브루트 포스. def maxProduct(self, n.. 2023. 4. 15. 이전 1 ··· 3 4 5 6 7 8 다음
