hyunkookim 님의 블로그

4. Median of Two Sorted Arrays GPT 좋아요! 다시 처음부터 차근차근, 이 문제를 해결하기 위해 "왼쪽 부분의 최대값 ≤ 오른쪽 부분의 최소값" 조건이 필요한 이유와 이 조건을 중심으로 문제를 푸는 방식을 전체적으로 설명하겠습니다.문제의 목표두 개의 정렬된 배열 nums1과 nums2가 주어집니다.이 두 배열을 병합한 후 **중앙값(중간값, Median)**을 구해야 합니다.단, 병합하지 않고 O(log(m + n)) 시간 복잡도 안에 해결해야 합니다.중앙값(Median)의 정의중앙값은 정렬된 배열에서 중앙에 위치한 값입니다. 배열의 길이에 따라 정의가 달라집니다.배열의 길이가 홀수인 경우:중앙에 위치한 하나의 값이 중앙값.예: [1, 3, 5] → 중앙값은 3.배열의 길이가 짝..

153. Find Minimum in Rotated Sorted Array class Solution: def findMin(self, nums: List[int]) -> int: """ 회전된 정렬 배열에서 최소값을 찾는 함수. 배열은 오름차순으로 정렬된 상태에서 몇 번 회전된 상태일 수 있다. 예: [4, 5, 6, 7, 0, 1, 2] Find the minimum value in a rotated sorted array. The array was originally sorted in ascending order but may have been rotated. Example: [4, 5, 6, 7, 0, 1..

34. Find First and Last Position of Element in Sorted Array class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: # O (log n) 이므로, bst 로 .. # bst 로 우선 target 이 있는지 없는지 찾고, # 있으면 idx 반환, 없으면 -1 # 있으면, 좌우로 움직이면서, 시작, 끝 찾고 def binary_search(l, r): while l

33. Search in Rotated Sorted Array https://youtu.be/U8XENwh8Oy8?si=nX8vCqYVxsjI-ODx class Solution: def search(self, nums: List[int], target: int) -> int: left, right = 0, len(nums)-1 while left https://youtu.be/Og8J5E6qC4M?si=l86Brf6j4hSpcKaI class Solution: def search(self, nums: List[int], target: int) -> int: def find_pivot(): # pivot = 최소값 지점 ..

74. Search a 2D Matrix class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: ROWS = len(matrix) COLS = len(matrix[0]) l, r = 0, COLS*ROWS - 1 while l target: r = mid-1 else: return True return False https://youtu.be/Ber2pi2C0j0 class Solution: def searchMatrix(self, matrix: List[List..

35. Search Insert Position class Solution: def searchInsert(self, nums: List[int], target: int) -> int: # O(log n) 이므로, 이진 탐색 BST 사용 l, r= 0, len(nums)-1 while(l target: r = mid-1 else: return mid # 못찾으면, # target > nums[l] 이면, # target을 l+1에 값을 넣어야 하니, l+1을 반환 # 아니면, target nums[l] else l while (l w..

918. Maximum Sum Circular Subarray 내 코드class Solution: def maxSubarraySumCircular(self, nums: List[int]) -> int: maxSum = nums[0] curSum = 0 for n in range(len(nums)*2): if curSum  이 코드는 틀렸음. %  모듈러 연산으로 회전 행렬을 반영하고 있으나.행렬 길이를 고려하고 있지 않음. class Solution: def maxSubarraySumCircular(self, nums: List[int]) -> int: maxSum = nums[0] curSum =..

53. Maximum Subarray class Solution: def maxSubArray(self, nums: List[int]) -> int: l, r = 0, len(nums)-1 # window = l-r # l는 1개씩 증가하는데, # l부터 len(nums) 까지, max_sum 계속 구함 max_sum = -float("inf") for l in range(len(nums)): # if nums[l]  Time Limit Exceeded https://youtu.be/5WZl3MMT0Eg?si=F16OBsmPYHPefkwv class Solution: def maxSubArray(s..

172. Factorial Trailing Zeroes class Solution: def trailingZeroes(self, n: int) -> int: # 펙토리알 구하는게 아니라. # 펙토리알 구해서 끝부분의 0의 개수 구하는.. if not n: return 0 def factorial(n): if n ==1: return 1 return n * factorial(n-1) fac = factorial(n) zero_cnt = 0 while (fac % 10 == 0): zero_cnt += 1 ..

66. Plus One class Solution: def plusOne(self, digits: List[int]) -> List[int]: stack = [] carry = 1 for i in range(len(digits)-1, -1, -1): new = digits[i] + carry carry = new // 10 stack.append(new % 10) if carry: # carry == 1 stack.append(carry) return stack[::-1]