[LeetCode] 39. Combination Sum (파이썬)

< 39. Combination Sum - 파이썬 풀이 >

• 해당문제 링크

  목차

1. 문제풀이 아이디어
2. 구현코드

문제풀이 아이디어

• 먼저 문제에서 요구하는 내용부터 알아보자. target 숫자가 주어졌을때, candidates 안에 존재하는 숫자들로 순서를 고려하지 않은 모든 경우의 수들 중에 합해서 target이 되는 조합들을 반환하라. 라는게 문제에서 요구하는 사항이다.
• 그렇다면 모든 경우의 조합을 구해야한다. 조합을 구하는 시간 복잡도를 생각하면 O(2^N)이다. 해당 문제에서 가장 큰 N은 30으로 주어지는데 그럼 시간 복잡도가 O(2^30)이 된다. 원하는 시간 안에 답을 구할 수 없을 것 같다. 그리고 백트래킹을 이용할 수도 있는데 백트래킹은 가지치기를 얼마나 잘하느냐에 따라 성능이 좌우되지만 최악의 경우 조합의 시간 복잡도와 같다. 그래서 다른 방법을 생각하려고 한다. 조합을 잘 생각해보면 중복되는 경우가 많다. 예를 들어, [2,2,2]와 [2,2,3]은 [2,2]가 겹친다. 이런 경우가 너무 많아서 시간 복잡도가 느려지는 것이다.
• 그럼 작은 부분문제가 중복되는 것을 이용해서 시간을 줄일 수 있는 DP( Dynamic Programming )을 생각해볼 수 있을 것 같다. DP는 memorization을 이용한 탑다운 방식과 tabulation을 이용한 바텀업 방식이 있다. 탑다운은 큰 문제를 작은 문제로 쪼개가면서 연산의 결과를 저장을 하고 중복되는 연산을 요구할 때 이미 얻은 결과를 이용하여 시간을 줄이는 방식이고 바텀업 방식은 작은 문제부터 큰 문제로 커지면서 작은 문제에서 나왔던 결과를 이용하여 큰 문제를 푸는 방법이다. 필자는 바텀업 방식이 더 편해서 이를 이용하겠다.
• 바텀업은 작은 문제에서 큰 문제로 커져가야한다고 했다. 그래서 작은 문제를 찾는 것이 되게 중요하다. 해당 문제에서 작은 문제는 무엇일까? 해당 문제를 풀기 위해서 값이 변했을 때 큰 영향을 끼치는 변수가 무엇인지 찾아보면 target과 candidates 정도를 생각할 수 있다. 예를 들어, target = 0이라면 반환되는 값은 []일 것이다. candidates가 없다면 반환되는 값은 []일 것이다.
• 그렇다면 저것들을 이용해볼 생각이다. 우리의 목표는 결국 합쳐서 target이 되는 조합을 구하느 것이니까 candidates를 변해가는 방식은 이용하지 않아도 될 것 같다. 왜냐하면 target으로 가기 위해서 candidates를 적게 사용하거나 전부 사용하거나는 해당 문제의 요지와 맞지 않기 때문이다. 그래서 seed 값으로는 target이 0일 때를 생각해서 [[]]으로 넣어줄 생각이다. 그 이유는 0일 때부터 올라가면서 [[2,2,3], [2,3,5]] 이와 같이 조합의 갯수를 늘려주기 위해서이다. 그리고 초기화는 []으로 할 것이다. 그 이유는 조합이 존재하지 않을 때, []를 반환해야 하기 때문이다.
• 이젠 iterate를 생각해야하는데 iterate를 할 때 조합이기 때문에 가장 마지막에 들어온 숫자보다 이제부터 넣어야하는 숫자가 크면 안된다. 이것을 생각해서 처리하면 될 것 같다.

구현코드

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        dp = [[] for _ in range(target+1)] # 초기화하는 부분
        dp[0].append([]) # seed 값을 넣는 부분

        for i in range(target+1): # iterate하는 부분
            if len(dp[i]) != 0: # seed값을 넣었기 때문에 len이 0인 경우는 접근하지 않아야 한다. 그 경우는 조합을 만들 수 없는 인덱스이기 때문이다.
                for c in candidates:
                    if i + c <= target: # candidates 요소 하나의 값과 현재 인덱스의 값 ( 조합의 합 )을 더했을 때 target을 넘으면 안된다.
                        temp = []
                        for index in dp[i]:
                            if len(index) > 0: 
                                if index[-1] <= c: # 마지막 원소와 비교하여 같거나 새로운 원소가 크거나 같은 경우만 값을 추가한다.
                                    temp.append(index.copy() + [c])
                            else:
                                temp.append(index.copy() + [c])
                        dp[i+c] = temp if len(dp[i+c]) == 0 else temp + dp[i+c]
        return dp[target]