hyunkookim 님의 블로그

79. Word Search ✅ 먼저 흐름 짚자퍼져나가면서 문자를 찾아야 하니까→ 당연히 DFS나 BFS 둘 다 가능해.그런데,"한 번 간 경로만 따라가야 해" (방문한 곳 재방문 X)"중간에 틀리면 바로 백트래킹" 해야 함이런 문제에서는 DFS + 백트래킹이 훨씬 자연스럽고 빠르다. 🚀(실제 LeetCode에서도 DFS 풀이를 추천하고 있어.)🔥 정리: Word Search는 DFS + 백트래킹 문제그래서 너가 처음 떠올린 "dfs 재귀 괜찮은가?"→ 네! 완전 괜찮고 오히려 정석이야.내 코드class Solution: def exist(self, board: List[List[str]], word: str) -> bool: # 퍼져 나가야하기때문에, bfs 인듯한데? 그래도 df..

5. Longest Palindromic Substring 내 처음 코드class Solution: def longestPalindrome(self, s: str) -> str: # 가장 긴 연속 부분문자열 중 Palindrome(좌우 반대 동일)인 문자열 l, r = 0, 0 max_ln = 0 for r in range(1, len(s)): strs = s[l:r+1] while strs == strs[::-1]: max_ln= max(max_ln, r-l+1) l+=1 return max_ln 좋아! 네가 지금 쓰고 있는 방식은아이디어는..

199. Binary Tree Right Side View # Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def rightSideView(self, root: Optional[TreeNode]) -> List[int]: # 제일 오른쪽꺼 찾으려면, 각 레벨별로 bst 에 끝에꺼 res = [] if not root: return re..

8. String to Integer (atoi) 지금 문자열을 int로 변환하는 myAtoi 함수를 직접 짜고 있는데,잘못된 부분이 몇 개 있어서 정확하게 짚어줄게. 👏❗ 문제점 1 — 부호(+, -) 체크가 잘못됨if s[i] not in valid: breakif s[i] not in op: break이렇게 되면 숫자도 아니고, 부호도 아니면 끊어야 하는데,네 코드에서는 숫자가 아니기만 해도 바로 break 되어버려.즉, -42 같은 걸 만나면,-는 숫자가 아니니까 첫 줄에서 바로 break 됨 ❗실제로는 부호는 받아야 하는데.✅ 고쳐야 해:첫 번째 글자는 부호일 수도 있고, 숫자일 수도 있음그 이후부터는 숫자만 와야 함❗ 문제점 2 — if s[i] not in valid와 if s[..

416. Partition Equal Subset Sum Partition Equal Subset Sum 문제는 DP(동적 계획법) 클래식 문제야. ✨✅ 문제 요약nums 배열을 두 부분으로 나누어서각 부분의 합이 같게 만들 수 있는지 True/False로 답하는 문제야.🧠 핵심 아이디어전체 합(total)을 먼저 구한다.total이 홀수면, 두 부분으로 절대 나눌 수 없다 → 바로 Falsetotal이 짝수면, target = total // 2로 설정한다.그다음, nums 중 일부 원소를 골라서 합이 target이 되는 조합이 있는지 찾는 문제로 바뀐다.👉 이건 Subset Sum 문제야!✨ 풀이 전략 (DP)dp[i] = sum이 i가 되는 부분집합이 가능한가?dp[0] = True (합 0은 ..

15. 3Sumclass Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: # 숫자 3개 더해서 0 # for 돌리면서 투포인터 사용 nums.sort() # 우선 정렬 -> 그래야.. 투포인터 사용가능 res = [] for a in range(len(nums)): l, r = a+1, len(nums)-1 while l 0: r -=1 else: # nums[a]+ nums[l] + nums[r] 지금 코드는 3Sum 문제의 기본 구조는 ..

53. Maximum Subarray 좋아요! 먼저 주신 코드는 Kadane's Algorithm 기반의 O(n) 시간 복잡도 풀이예요.아주 잘 작성하셨고, 여기에 상세 주석을 달아드릴게요.그 다음 Follow-up: Divide and Conquer 방식도 자세히 설명드릴게요.✅ Kadane's Algorithm 풀이 (O(n)) + 주석class Solution: def maxSubArray(self, nums: List[int]) -> int: # 현재까지 탐색한 부분에서의 최대 연속합을 저장할 변수 curSum = maxSum = nums[0] # 초기값: 첫 번째 원소 # 두 번째 원소부터 끝까지 순회 for r in range(1, le..

543. Diameter of Binary Tree 이 문제 Diameter of Binary Tree는 트리에서 두 노드 사이의 **가장 긴 경로의 길이(엣지 수)**를 구하는 문제입니다.❗️Diameter에는 **노드 수가 아니라 엣지 수(edge count)**가 포함됩니다.즉, **노드는 포함되지 않고, 그 사이의 연결선(엣지)**만 세는 거예요. Diameter = 엣지 수 = 노드수 -1📌 예시: root = [1,2,3,4,5]이 트리 구조는 이렇게 생겼어요: 1 / \ 2 3 / \ 4 5가장 긴 경로는 4 -> 2 -> 1 -> 3 또는 5 -> 2 -> 1 -> 3이 경로의 노드 수는 4개지만,엣지 수 = 3개입니다 (4-2, 2-1, 1-3)그래서 ..

409. Longest Palindromeclass Solution: def longestPalindrome(self, s: str) -> int: # s 는 대소문자 모두 가능 # s 의 문자로 만들수 있는, 최고로 긴 Palindrome 길이 반환 # Palindrome 은 앞으로 읽으나 뒤로 읽으나 같은 문자 # 글자 단위로 count 한뒤 2로 나누고. 1개짜리 문자 있으면 1 더할수 있음 countDict = {} for w in s: if w not in countDict: countDict[w] = 0 countDict[w] += 1 ..

278. First Bad Version# The isBadVersion API is already defined for you.# def isBadVersion(version: int) -> bool:class Solution: def firstBadVersion(self, n: int) -> int: # 가장 빨리 나오는 bad 버전 찾기.. # 그러니깐. 경계 # isBadVersion(n) 했는데, bad 이면, n-1로 옮기고. l, r = 1, n+1 fisrtBad = n while l 지금 아이디어는 **이진 탐색(Binary Search)**을 이용한 것이고 방향도 거의 맞지만,조건 해석이 반대로 되어 있어..