인프런 커뮤니티 질문&답변

우선 강사님께서 풀어주신 top-down 코드는 다음과 같습니다.

class Solution(object):
    def uniquePaths(self, m, n):
        memo = {}

        def dfs(r, c):
            if (r, c) == (0, 0):  # 출발점에 도달한 경우
                return 1
            if (r, c) not in memo:  # 메모이제이션에 값이 없는 경우 계산
                paths = 0
                if r - 1 >= 0:  # 위쪽 셀에서 오는 경우
                    paths += dfs(r - 1, c)
                if c - 1 >= 0:  # 왼쪽 셀에서 오는 경우
                    paths += dfs(r, c - 1)
                memo[(r, c)] = paths  # 결과 저장
            return memo[(r, c)]  # 결과 반환

        return dfs(m - 1, n - 1)

이 코드는 grid에 해당하는 함수만 호출하고, 중복되는 호출은 memo에 저장하기 때문에 총 O(M*N)이 됩니다.

다음은, 디스코드의 다른 사람이 올려주신 코드를 참고해서 조합론을 적용한 코드입니다.

class Solution(object):
    def uniquePaths(self, m, n):
        memo = {}
        def fact(x):
            if x <= 1:
                return 1
            if x not in memo: 
                memo[x] = fact(x - 1) * x # factorial의 결과값을 메모리에 저장
            return memo[x]
        return fact(m + n - 2) / (fact(m - 1) * fact(n - 1)) # fact(m + n - 2) 부분만 호출하고, 분모는 캐싱하므로 시간복잡도는 O(M+N)

분자에 해당하는 부분만 함수를 호출하기 때문에 시간복잡도는 O(M+N)이 됩니다.

우선 제가 궁금한 것은 2가지입니다.

1) 위의 두 코드를 비교했을 때, 수학적으로 접근한 코드가 시간복잡도가 더 낮은데요 항상 dfs, bfs를 먼저 쓰는게 좋은 것은 아닌가요?

2) 강의에서는 조합론을 이용한 방법이 198C99 = 약 2*10^58이여서 완전탐색은 안된다고 하셨는데, 실제로 제출했을 때는 제출이 됬습니다. 왜 이런 차이가 발생한건가요?