feat: add prev week solutions

kangdaia · kangdaia · commit 394f06c37160 · 2026-03-27T20:40:59.000+09:00
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/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)
