hyunkookim 님의 블로그

287. Find the Duplicate Number 이 문제 LeetCode 287. Find the Duplicate Number는 배열을 수정하지 않고,**O(1)**의 추가 공간만으로 중복된 숫자 하나를 찾아야 하는 문제예요. 내 코드class Solution: def findDuplicate(self, nums: List[int]) -> int: # nums 수정하지 말고, 공간복잡도는 O(1) 로..!! # n+1 개수 n = len(nums)-1 res = 1 for i in range(2, n+1): res ^= i for n in nums: res ^= ..

876. Middle of the Linked List # Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]: """ - slow는 한 칸씩 - fast는 두 칸씩 이동 - fast가 끝에 도달하면, slow는 중간에 도달 """ slow = fast = head ..

560. Subarray Sum Equals K 누적합 + 해시맵을 사용하는 대표적인 패턴 문제입니다.✅ 문제 요약배열 nums와 정수 k가 주어질 때,연속된 구간(subarray)의 합이 k가 되는 경우의 수를 구하라. from collections import defaultdictclass Solution: def subarraySum(self, nums: List[int], k: int) -> int: count = 0 # 정답: 합이 k인 서브어레이의 개수 prefixSum = 0 # 누적합 (0부터 현재 인덱스까지의 합) prefixCount = defaultdict(in..

724. Find Pivot Index 1) Prefix Sums 누적합 이용 풀이 방법class Solution: def pivotIndex(self, nums: List[int]) -> int: # 자신을 제외한 왼쪽 합 == 오른쪽 합이 되는 pivot index를 찾는 문제 total = 0 # 전체 합을 계산하기 위한 변수 PrefixSum = [] # 0번 인덱스부터의 누적합 배열 for n in nums: total += n # 현재까지의 누적합을 계산 PrefixSum.append(total) # 누적합을 배열..

304. Range Sum Query 2D - Immutable class NumMatrix: def __init__(self, matrix: List[List[int]]): self.matrix = matrix rows, cols = len(matrix), len(matrix[0]) # prefixSums[i][j]는 (0,0)부터 (i,j)까지의 누적합을 저장 self.prefixSums = [[0] * cols for _ in range(rows)] for r in range(rows): for c in range(cols): top = self.prefixSums[r-1][c] if ..

303. Range Sum Query - Immutable class NumArray: def __init__(self, nums: List[int]): self.nums = nums self.area = [0]*len(nums) self.area[0] = nums[0] # 첫 원소는 그대로 할당 for i in range(1, len(nums)): self.area[i] = self.area[i - 1] + nums[i] # 누적합 계산 def sumRange(self, left: int, right: int) -> int: if left == 0: return self.area[righ..

424. Longest Repeating Character Replacement https://youtu.be/gqXU1UyA8pk 이 문제는 슬라이딩 윈도우 [Sliding Window Variable Size] + 해시맵을 활용해서 풀 수 있어요.핵심은 윈도우 안의 가장 많이 나온 문자를 기준으로나머지를 바꾸는 데 k번 이하로 가능한지 체크하는 것입니다.✅ 아이디어 요약:윈도우 내 가장 많이 나온 문자 수 = max_count현재 윈도우 크기 = r - l + 1바꿔야 하는 문자 수 = 전체 윈도우 크기 - max_count이 값이 k보다 작거나 같을 때만 윈도우 유지, 아니면 왼쪽 포인터 이동✅ 코드 (주석 포함)from collections import defaultdictclass Soluti..

1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold ✅ 문제 요약 (LeetCode 1343)정수 배열 arr, 정수 k, threshold가 주어짐크기가 k인 연속된 부분 배열(subarray) 중,평균이 threshold 이상인 경우의 개수를 리턴✅ 핵심 아이디어슬라이딩 윈도우 크기 = k평균 ≥ threshold → sum ≥ threshold * k 로 변환해서 비교하면 정수만 다룰 수 있음슬라이딩 윈도우 방식으로 한 칸씩 이동하면서 합을 업데이트✅ 최적 풀이 (Python, O(n) 시간)class Solution: def numOfSubarrays(self, arr: List[int], k:..

978. Longest Turbulent Subarray 이 문제는 **“인접한 숫자의 크고 작음이 번갈아가며 나타나는 subarray”**의 최대 길이를 구하는 문제예요.✅ 핵심 개념🔁 Turbulent Subarray란?인접한 숫자들이 번갈아 가며 크거나 작아지는 구조예요.예:[9, 4, 2, 10, 7, 8, 8, 1, 9]→ [4, 2, 10, 7, 8]는 turbulent→ 4 > 2 7 즉, 비교 부호 (>, 매번 반대여야 해요. ✅ 접근법: 슬라이딩 윈도우 + 비교class Solution: def maxTurbulenceSize(self, arr: List[int]) -> int: len_arr = len(arr) # 길이가 1이면 비교할 쌍이 없으므로 그..

Graph -> 링크드리스트, 트리 둘다 포함 -> vertex (노드) 와 edge (연결방향)으로 구성 -> E    그래서,Tree와 linked list 는 방향성 있는 그래프(directed Graph) 라고 할 수 있고 방향성 없는 그래프(Undirected Graph) 라는 의미는,= 즉, 양방향 모두 갈수 있다는 의미= 양방향 에지(간선)=> matrix 행렬 또는 adjacency list 인접 리스트 를 사용해서 문제 품!! 1. 행렬(Matrix) 문제는?# Matrix (2D Grid)grid = [[0, 0, 0, 0], [1, 1, 0, 0], [0, 0, 0, 1], [0, 1, 0, 0]] 0: Free1: Blocked 위에서 아래로 행..