• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

leetCode - Two Sum 문제 Memory Limit Exceeded 에러

23.12.28 22:31 작성 23.12.29 10:30 수정 조회수 235

2

class Solution(object):
    def twoSum(self, nums, target):
        def backtrack(start, curr):
            # base case : 2개의 합을 더해서 target과 같으면
            if len(curr) == 2 and sum(nums[i] for i in curr) == target:
                return curr

            # recursion : 
            for i in range(start, len(nums)):
                curr.append(i)
                res = backtrack(i + 1, curr)
                
                if res:
                    return res
                
                curr.pop()
            return None
        return backtrack(0, [])

https://leetcode.com/problems/two-sum/submissions/1130560186/

 

이 코드로 작성해서 leet-code의 two sum 문제에 제출해봤을 때 Memory Limit Exceeded 에러가 나는건 어떻게 해결해야 할까요?

답변 1

답변을 작성해보세요.

1

안녕하세요 changonna님!!

오 이거 직접구현해서 돌려보셨군요.

이게 완전탐색을 설명하려다보니 우리가 배웠던 twosum을 가지고 온건데, 실제 이걸 돌려보면 재귀 호출과 추가 메모리 사용이 많아, 특히 큰 입력 배열에 대해서는 비효율적입니다.

그래서 우리가 반복문을 이용해서 완전탐색을 했던거에요~!

 

저희 처음에 twosum문제 배울 때 완전탐색 - 반복문 구현 (O(n^2))으로 구현했을 때에도 시간초과가 났잖아요. 근데 이걸 완전탐색 -재귀 구현(시간복잡도도 O(n^2)인데 재귀호출이 많아서 메모리사용이 엄청 많아짐)으로 구현하면 더 비효율적인 풀이가 되겠죠.

 

그래서 결국 우리 정렬을 하거나 dictionary 사용했던것처럼 풀이를 발전시켜야 합니다.

결론: 해당 문제의 제약조건 하에서는 완전탐색(더더욱 backtracking 구현)은 통과하기 힘들다.

하지만 구현자체는 굉장히 잘하셨어요!!

 

혹시 더 궁금한점 있으면 질문 남겨주세요 :)

changonna님의 프로필

changonna

질문자

2023.12.29

감사합니다!