Merge pull request DaleStudy#2477 from kangdaia/main

kangdaia · web-flow · commit aef74ca60a68 · 2026-03-29T13:20:31.000+09:00
[kangdaia] WEEK 04 Solutions
diff --git a/coin-change/kangdaia.py b/coin-change/kangdaia.py
@@ -0,0 +1,28 @@
+class Solution:
+    def coinChange(self, coins: list[int], amount: int) -> int:
+        """amount를 만들기 위해 최소한의 코인으로 구성할 수 있는 방안의 수를 구하는 함수
+        동일한 동전을 여러번 사용해도 됨
+
+        방법:
+        - 방법 수를 보고 dp로 풀기로 함. 금액이 dp 단계가 됨.
+            모든 금액별로, 코인 목록을 돌면서, 코인을 사용할 수 있으면 amount-coin한 금액의 방법수 + 1과 비교하기
+            -> 조합이 불가능한 상태를 어떻게 판단하지? 에서 dp init을 0이 아니라 inf로 해야, 구분이 가능하다는 점.
+            -> 그래서 min 비교를 현재 인덱스 dp값과 i-coin의 dp 값 + 1으로 함
+            coin이 정렬되지 않은 리스트라, 정렬해, coin 값이 amount를 넘어가면 pass
+
+        Args:
+            coins (list[int]): 사용할 수 있는 동전 목록
+            amount (int): 목표하는 금액
+
+        Returns:
+            int: 금액을 만들기 위해 구성할 수 있는 동전들 방안 수
+        """
+        dp = [float("inf")] * (amount + 1)
+        dp[0] = 0
+        coins.sort()
+        for coin in coins:
+            if coin > amount:
+                continue
+            for i in range(coin, amount + 1):
+                dp[i] = min(dp[i], 1 + dp[i - coin])
+        return dp[amount] if dp[amount] != float("inf") else -1
diff --git a/decode-ways/kangdaia.py b/decode-ways/kangdaia.py
@@ -0,0 +1,28 @@
+class Solution:
+    def numDecodings(self, s: str) -> int:
+        """1에서 26까지 숫자를 알파벳으로 치환할 수 있을때,
+        주어진 숫자 문자열이 어떤 알파벳으로 치환 될 수 있는지 방법의 수를 찾는 함수
+
+        방법:
+        1. 경우의 수를 찾는 경우는 대부분 DP..?
+        - 케이스가 명확함.
+            현 위치의 숫자가 0이 아닌 경우, 해당 자리가 앞 숫자와 별개로 1~9 사이의 숫자를 선택할 수 있다.
+            만약 앞의 경우를 포함해서 숫자가 10에서 26사이면 앞의 경우를 포함해서 경우의 숫자를 생각해야 함.
+        다만 첫번째 숫자가 0이면 넘어가야 함.
+        시간 복잡도: O(n) 공간 복잡도: O(n)
+
+        Args:
+            s (str): 숫자로 이루어진 문자열
+
+        Returns:
+            int: 문자열로 치환할 수 있는 알파벳 구성의 수
+        """
+        dp = [0] * len(s)
+        if s[0] != "0":
+            dp[0] = 1
+        for i in range(1, len(s)):
+            if s[i] != "0":
+                dp[i] += dp[i - 1]
+            if "10" <= s[i - 1 : i + 1] <= "26":
+                dp[i] += dp[i - 2] if i > 1 else 1
+        return dp[-1]
diff --git a/find-minimum-in-rotated-sorted-array/kangdaia.py b/find-minimum-in-rotated-sorted-array/kangdaia.py
@@ -0,0 +1,27 @@
+class Solution:
+    def findMin(self, nums: list[int]) -> int:
+        """
+        정렬된 리스트에서 n번 돌아간 상태에서 기존의 첫번째 값 (가장 작은)을 찾는 함수
+
+        방법:
+        Hint2의 Can you think of an algorithm which has O(logN) search complexity?
+        에서 binary search!
+
+        Args:
+            nums (list[int]): n번 돌아간 정수 리스트
+
+        Returns:
+            int: 최초 정렬된 리스트의 첫번째 값
+        """
+        if nums[0] <= nums[-1]:
+            return nums[0]
+        start, end = 0, len(nums) - 1
+        while start < end:
+            if start == end:
+                break
+            mid = start + (end - start) // 2
+            if nums[mid] > nums[end]:
+                start = mid + 1
+            else:
+                end = mid
+        return nums[start]
diff --git a/maximum-depth-of-binary-tree/kangdaia.py b/maximum-depth-of-binary-tree/kangdaia.py
@@ -0,0 +1,26 @@
+# 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 = right
+
+
+class Solution:
+    def maxDepth(self, root: TreeNode | None) -> int:
+        """주어진 binary tree의 최대 깊이를 찾는 함수
+
+        방법:
+        1. 재귀함수를 생각함. 인자로 현재 head node와 현재의 depth를 받는 재귀함수를 만들어 재귀 반복
+        2. 이 함수 자체가 재귀가 될 수 있다고 판단, 별도의 재귀함수를 삭제함.
+            depth를 넘겨주지 않아도, 앞에 +1을 함으로써 depth가 계산됨.
+
+        Args:
+            root (TreeNode | None): binary tree
+
+        Returns:
+            int: 최대 깊이
+        """
+        if root is None:
+            return 0
+        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
diff --git a/maximum-subarray/kangdaia.py b/maximum-subarray/kangdaia.py
@@ -0,0 +1,52 @@
+class Solution:
+    def maxSubArray(self, nums: list[int]) -> int:
+        """리스트의 이어진 문자열로 구성된 subarray중 최대 합을 찾는 함수
+
+        방법:
+        1. brute force. 다만 O(n)으로 만들 수 없어 탈락!
+        2. 전역 최대합과 로컬 최대 합을 분리해서 생각하기.
+            연속된 문자열이기 때문에, 현재 값이 이전의 합보다 크면 앞의 값을 버리는 방식
+            => 시간 복잡도 O(n), 공간 복잡도 O(1)
+        3. divide and conquer (Follow up)
+
+        Args:
+            nums (list[int]): 정수 문자열
+
+        Returns:
+            int: 최대 합
+        """
+        max_sum = nums[0]
+        local_sum = nums[0]
+        for i in range(1, len(nums)):
+            if local_sum < 0 and local_sum < nums[i]:
+                local_sum = nums[i]
+            else:
+                local_sum += nums[i]
+            max_sum = max(max_sum, local_sum)
+        return max_sum
+
+    def maxSubArraySubtle(self, nums: list[int]) -> int:
+        def divConq(left: int, right: int) -> int:
+            if left == right:
+                return nums[left]
+            mid = (left + right) // 2
+
+            left_max = divConq(left, mid)
+            right_max = divConq(mid + 1, right)
+
+            curr_sum = 0
+            left_suffix_max = -float("inf")
+            for idx in range(mid, left - 1, -1):
+                curr_sum += nums[idx]
+                left_suffix_max = max(left_suffix_max, curr_sum)
+
+            curr_sum = 0
+            right_prefix_max = -float("inf")
+            for idx in range(mid + 1, right + 1, 1):
+                curr_sum += nums[idx]
+                right_prefix_max = max(right_prefix_max, curr_sum)
+
+            cross = left_suffix_max + right_prefix_max
+            return max(left_max, right_max, cross)
+
+        return divConq(0, len(nums) - 1)
diff --git a/merge-two-sorted-lists/kangdaia.py b/merge-two-sorted-lists/kangdaia.py
@@ -0,0 +1,37 @@
+# Definition for singly-linked list.
+class ListNode:
+    def __init__(self, val=0, next=None):
+        self.val = val
+        self.next = next
+
+
+class Solution:
+    def mergeTwoLists(self, list1: ListNode | None, list2: ListNode | None) -> ListNode | None:
+        """두개의 링크드 리스트를 합쳐서 하나의 sorted 링크드 리스트를 만드는 함수
+
+        방법:
+        1. 각각의 리스트 head에서 값을 비교하면서,
+            1번보다 2번의 값이 작으면 1번의 head를 움직이고,
+            반대의 경우 2번의 head를 움직이도록 함.
+            움직이면서 합치는 리스트에 tail.next로 붙여줌
+
+        Args:
+            list1 (ListNode | None): 정렬된 양수 링크드 리스트
+            list2 (ListNode | None): 정렬된 양수 링크드 리스트 2
+
+        Returns:
+            ListNode | None: 하나로 합쳐진 정렬된 링크드 리스트
+        """
+        final = ListNode()
+        tail = final
+        curr1, curr2 = list1, list2
+        while curr1 and curr2:
+            if curr1.val < curr2.val:
+                tail.next = curr1
+                curr1 = curr1.next
+            else:
+                tail.next = curr2
+                curr2 = curr2.next
+            tail = tail.next
+        tail.next = curr1 if curr1 else curr2
+        return final.next
diff --git a/word-search/kangdaia.py b/word-search/kangdaia.py
@@ -0,0 +1,39 @@
+class Solution:
+    def exist(self, board: list[list[str]], word: str) -> bool:
+        """m*n 사이즈 보드가 주어졌을 때, word를 만들 수 있는지 true/false로 return 하는 함수
+
+        1. bfs로 queue에 모든 element를 추가하고, 매번 path를 파악해서 word인지 판단하도록 함
+        -> 시간 효율이 안나옴
+        2. dfs 방식 적용. 현재 탐색 중일때, 보드를 #으로 치환해서, 이미 방문한 곳임을 체크
+            - 시작점이 word[0]와 같을 때만 시작
+            - dfs는 전체 path를 기록하지 않고, word가 볼 index를 인자로 받도록 함.
+
+        Args:
+            board (list[list[str]]): 글자를 element로 가진 2d array
+            word (str): 찾아야 할 글자 목록
+
+        Returns:
+            bool: word가 board에 있는지 여부
+        """
+        m, n = len(board[0]), len(board)
+
+        def dfs(row, col, idx):
+            if board[row][col] != word[idx]:
+                return False
+            if idx == len(word) - 1:
+                return True
+            visited = board[row][col]
+            board[row][col] = "#"
+            for r, c in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
+                if 0 <= r < n and 0 <= c < m:
+                    if dfs(r, c, idx + 1):
+                        board[row][col] = visited
+                        return True
+            board[row][col] = visited
+            return False
+
+        for ir in range(n):
+            for ic in range(m):
+                if board[ir][ic] == word[0] and dfs(ir, ic, 0):
+                    return True
+        return False
