Merge pull request DaleStudy#2451 from gcount85/main

jamiebase · web-flow · commit 33dc6e9e38fb · 2026-03-20T10:24:46.000+09:00
diff --git a/combination-sum/gcount85.py b/combination-sum/gcount85.py
@@ -0,0 +1,37 @@
+"""
+# Intuition
+backtracking
+
+# Complexity
+- Time complexity: N을 깊이만큼 곱한다. 따라서 아래와 같을 때, O(N^(T/M))
+    N = candidates 개수
+    T = target
+    M = candidates 중 최소값
+
+- Space complexity: O(T/M)
+"""
+
+
+class Solution:
+    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
+        candidates.sort()
+        answer = []
+        output = []
+
+        def dfs(cur_i, cur_sum):
+            if cur_sum == target:
+                answer.append(output[:])
+                return
+
+            for i in range(cur_i, len(candidates)):
+                num = candidates[i]
+
+                if cur_sum + num > target:
+                    break
+
+                output.append(num)
+                dfs(i, cur_sum + num)
+                output.pop()
+
+        dfs(0, 0)
+        return answer
diff --git a/decode-ways/gcount85.py b/decode-ways/gcount85.py
@@ -0,0 +1,29 @@
+"""
+# Intuition
+dp[n]은 s의 n번째 글자까지 디코딩할수 있는 경우의 수
+dp[n] = dp[n-1](if can be decoded) + dp[n-2](if can be decoded)
+
+# Approach
+i-1 ~ i까지의 숫자, i-2 ~ i까지의 숫자가 각각 디코딩 될 수 있는지 확인한다.
+디코딩 가능하면 그 위치의 dp 배열의 값을 각각 더하고, 디코딩 불가능하면 더하지 않는다.
+
+# Complexity
+- Time complexity: N을 s의 길이라고 할 때, 반복문으로 O(N)
+
+- Space complexity: dp 배열 만드는 데에 O(N)
+"""
+
+
+class Solution:
+    def numDecodings(self, s: str) -> int:
+        n = len(s)
+        dp = [0] * (n + 1)
+        dp[1] = 1 if s[0] != "0" else 0
+        if dp[1] == 0 or n == 1:
+            return dp[1]
+        dp[2] = 1 if int(s[1]) > 0 else 0
+        dp[2] += 1 if int(s[:2]) > 9 and int(s[:2]) < 27 else 0
+        for i in range(3, n + 1):
+            dp[i] = dp[i - 1] if s[i - 1 : i] != "0" else 0
+            dp[i] += dp[i - 2] if s[i - 2 : i] > "09" and s[i - 2 : i] < "27" else 0
+        return dp[n]
diff --git a/maximum-subarray/gcount85.py b/maximum-subarray/gcount85.py
@@ -0,0 +1,19 @@
+"""
+# Intuition
+max(전 위치까지의 sum + 지금 위치 값, 지금 위치의 값)
+
+# Complexity
+- Time complexity: nums의 길이를 N이라고 할 때 O(N)
+
+- Space complexity: O(1)
+"""
+
+
+class Solution:
+    def maxSubArray(self, nums: List[int]) -> int:
+        a = nums[0]
+        best = a
+        for i in range(1, len(nums)):
+            a = max(a + nums[i], nums[i])
+            best = max(a, best)
+        return best
diff --git a/number-of-1-bits/gcount85.py b/number-of-1-bits/gcount85.py
@@ -0,0 +1,18 @@
+"""
+# Intuition
+n을 n-1과 AND 비트 연산하면서 1을 제거해나가며 카운트한다.
+
+# Complexity
+- Time complexity: n의 이진수 변환에서 1의 개수를 K라고 할 때, O(K)
+
+- Space complexity: O(1)
+"""
+
+
+class Solution:
+    def hammingWeight(self, n: int) -> int:
+        count = 0
+        while n:
+            n &= n - 1
+            count += 1
+        return count
diff --git a/valid-palindrome/gcount85.py b/valid-palindrome/gcount85.py
@@ -0,0 +1,27 @@
+"""
+# Approach
+양 끝에 포인터를 두고 파이썬의 isalnum(), lower() 문자열 메소드로 검사합니다.
+
+# Complexity
+- Time complexity: s의 길이를 N이라고 할 때, O(N)
+
+- Space complexity: O(1)
+"""
+
+
+class Solution:
+    def isPalindrome(self, s: str) -> bool:
+        l = 0
+        r = len(s) - 1
+        while l < r:
+            if not s[l].isalnum():
+                l += 1
+                continue
+            if not s[r].isalnum():
+                r -= 1
+                continue
+            if s[l].lower() != s[r].lower():
+                return False
+            l += 1
+            r -= 1
+        return True
