Tech for good

슬라이딩 윈도우(Sliding Window): 윈도우(특정 범위)가 있을 때, 윈도우 내부 요소의 값을 이용하여 문제를 풀이하는 알고리즘.class Solution: def findMaxAverage(self, nums: List[int], k: int) -> float: # 초기 윈도우 설정 (첫 k개의 합) current_sum = sum(nums[:k]) max_sum = current_sum # 슬라이딩 윈도우 이동 for i in range(k, len(nums)): current_sum += nums[i] - nums[i - k] # 윈도우 이동 (새로운 값 추가, 오래된 값 제거) m..

첫번째 방법 - 해시맵(HashMap)class Solution: def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool: index_map = {} # 숫자의 마지막 등장 인덱스를 저장할 딕셔너리 for i, num in enumerate(nums): if num in index_map and i - index_map[num] 딕셔너리(HashMap)을 사용하여 숫자의 인덱스를 저장하고, 현재 인덱스와 이전에 나온 동일 숫자의 인덱스 차이가 k 이하인지 확인하는 방식.풀이 설명index_map 딕셔너리를 사용하여 숫자 num의 가장 최근 인덱스를 저장한다.리스트 nums를 순회하면서:현재..

Two Pointers Approach (O(n) 시간, O(1) 공간)뒤에서부터 문자열을 처리하면서 '#'을 만나면 백스페이스를 적용한다.각 문자열에 대해 유효한 문자 위치를 찾아 비교한다.포인터를 이동하면서 문자 비교를 진행한다.class Solution: def backspaceCompare(self, s: str, t: str) -> bool: # 두 개의 포인터를 각각 문자열 s와 t의 끝에서 시작 i, j = len(s) - 1, len(t) - 1 # 백스페이스('#')의 개수를 추적하는 변수 back_s, back_t = 0, 0 # 두 문자열 중 하나라도 아직 탐색할 문자가 남아있는 동안 반복 whil..

첫번째 방법class Solution: def canMakeSubsequence(self, str1: str, str2: str) -> bool: i, j = 0, 0 # 두 문자열을 비교할 포인터 while i 코드 설명투 포인터 접근법 (i, j 사용)i: str1을 탐색하는 포인터j: str2를 탐색하는 포인터문자 비교str1[i] == str2[j]: 그대로 유지 가능str1[i]가 str2[j]의 바로 이전 문자인지 확인(ord(str1[i]) - ord('a') + 1) % 26 + ord('a') == ord(str2[j])이 조건이 참이면 str1[i]를 변환하여 str2[j]로 만들 수 있음.26이 나오는 이유는 알파벳이 26개 존재하기 때문..

https://neetcode.io/problems/is-palindrome NeetCode neetcode.io첫번째 방법 - String Manipulationclass Solution: def isPalindrome(self, s: str) -> bool: # 1. 알파벳과 숫자만 남기고 소문자로 변환 filtered_s = ''.join(c.lower() for c in s if c.isalnum()) # 2. 문자열을 뒤집어서 원래 문자열과 비교 return filtered_s == filtered_s[::-1]isalnum() -> 문자열이 문자 혹은 숫자로 되어있으면 참 리턴, 아니면 거짓 리턴시간 복잡도문자열 필터링: O..

풀이1) set  자료구조 사용class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: return list(set(nums1) & set(nums2))시간 복잡도 분석set(nums1): O(N)set(nums2): O(M)set1 & set2: O(min(N, M))list(...): O(K) (교집합 원소 수를 K라고 가정)➡️ 최종 시간 복잡도: O(N + M) (매우 효율적)풀이2) two-pointer 사용class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: ..

1️⃣번째 방법class Solution: def reverseWords(self, s: str) -> str: return " ".join(s.split()[::-1]) 시간 복잡도 및 공간 복잡도시간 복잡도: O(n)split() → O(n)[::-1] (리스트 뒤집기) → O(n)" ".join() → O(n)따라서 전체 시간 복잡도는 O(n) 입니다.공간 복잡도: O(n)split()이 새로운 리스트를 생성하므로 O(n)의 추가 공간이 필요합니다.2️⃣번째 방법Follow-up: O(1) 추가 공간으로 해결할 수 있을까?문자열이 가변(mutable)한 경우, O(1) 공간에서 In-place 방식으로 해결할 수 있습니다.파이썬에서는 문자열이 **불변(immutable)**이라서 ..

class Solution: def isSubsequence(self, s: str, t: str) -> bool: i, j = 0, 0 # Pointers for s and t while i i += 1 -> s의 인덱스를 증가j += 1 -> s와 상관없이 (즉, 매치됨과 상관없이) t의 인덱스를 하나씩 증가 Example 2의 경우, x가 t에 없으므로 i False시간 복잡도 및 공간 복잡도시간 복잡도: O(n) (t의 길이만큼 한 번 순회)공간 복잡도: O(1) (추가적인 공간 사용 없음)

🔹 문제 풀이 접근이 문제는 최소한의 거래로 모든 부채를 정산하는 문제이다.즉, 누가 누구에게 돈을 줘야 하는지 최소한의 거래(transactions)로 해결하는 것이 목표이다.✅ 해결 방법: Backtracking 각 사람의 최종 잔액을 계산주어진 거래를 기반으로 각 사람의 순 잔액(balance)을 계산.예를 들어, 어떤 사람이 $10 빌려줬으면 +10, $5 빌렸으면 -5.잔액이 0이 아닌 사람들을 대상으로 최소 거래 조합 찾기부채(- 잔액)와 자산(+ 잔액)을 매칭하여 최소 거래로 해결.백트래킹(Backtracking)을 활용하여 모든 가능한 거래를 탐색.from collections import defaultdictclass Solution: def minTransfers(self, tr..

https://leetcode.com/problems/median-of-two-sorted-arrays/description/ 🔹 문제 풀이 접근이 문제는 두 개의 정렬된 배열(nums1, nums2)이 주어질 때, 병합 후 중앙값(median)을 찾는 문제이다. ✅ 최적화 방법 (이진 탐색 활용)이진 탐색(Binary Search)을 사용하여 한 배열을 절반으로 분할하면서 답을 찾음.시간 복잡도: O(log(min(m, n)))class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: # nums1이 항상 짧은 배열이 되도록 보장 if len(nums1) > l..