접근 방식 변경 | 동일한 문제를 해결하는 다양한 방법

우리가 문제에 접근하는 방식에 따라 문제 해결에 필요한 노력이 결정됩니다. 당연한 것처럼 보일 수도 있지만 때때로 우리 엔지니어들은 한 방향으로만 생각하고 다른 방향을 볼 수 없습니다.

오늘 예를 들어 설명하려고 합니다.

이 간단한 leet 코드 예제Contains Duplicate를 살펴보겠습니다.

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

첫 접근

아마도 마음속에 있는 첫 번째 해결책은 모든 요소를 ​​다음 항목과 비교하여 동일한지 확인한 다음 거기에서 true를 반환할 수 있도록 항목을 반복하는 것입니다. 합리적이고 실행 가능해 보입니다. 여기에서 코드를 살펴보겠습니다.

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:

        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if nums[i] == nums[j]:
                    return True

        return False

이 솔루션은 실제로 작동하며 더 작은 어레이가 이를 수행하는 데 문제가 되지 않지만 짐작할 수 있듯이 이것은 무차별 대입 솔루션이며 이 솔루션의 시간 복잡도는 N-Square의 BigOO(n^2)입니다. 왜냐하면 두 루프를 모두 실행할 것이기 때문입니다. n-1번.

두 번째 접근법

두 번째 접근 방식은 첫 번째 접근 방식과 완전히 다르며 알고리즘을 크게 개선합니다.
이 접근 방식에서는 모든 요소를 ​​나머지 요소와 비교하는 대신 방문한 모든 요소를 ​​추적하고 방문/추적한 요소를 만날 때마다 배열에 중복 항목이 있음을 이미 알고 있습니다.
간단한 파이썬 코드를 사용하면 정말 쉽게 해결할 수 있습니다.

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        visitedHashMap = {}

        for num in nums:
            if num in visitedHashMap.keys():
                return True

            visitedHashMap[num] = num

        return False

이 접근 방식은 첫 번째 접근 방식보다 훨씬 효율적이지만 방문한 요소를 저장하기 위한 해시 맵을 생성하므로 더 많은 메모리O(n)를 사용합니다.

두 번째 접근법 - 약간의 변형

num 키가 hashMap에 존재하는지 확인하는 대신 단순히 키를 가져오려고 시도할 수 있으며 키가 없는지 알 수 있습니다. 파이썬은 KeyError를 발생시키고 우리가 알고 있는 대로 이 예외를 전달할 수 있습니다. 처음으로 확인되는 키입니다.

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        visitedHashMap = {}

        for num in nums:
            try:
                visitedHashMap[num]
                return True
            except KeyError:
                visitedHashMap[num] = num

        return False

어떤 접근 방식이 더 나은지 판단은 여러분에게 맡기지만 여러분과 공유하고 싶었던 실제 문제에 대한 배경을 구축하기 위해 위의 시나리오를 설명했습니다.

실제 문제

주어진 목표에 더해지는 정수 배열에서 가능한 모든 조합의 수를 제공하라는 요청을 받는 비교적 유명한 문제가 있습니다.
문제 진술은 다음과 같습니다.

Given an array nums of positive integers, provide count for all the possible combinations which adds up to a given target. The combinations should have at least two elements and should be in descending order.

Input: nums = [1,2,3,4], target=5
Output: 2

설명

주어진 대상5에 대해 위 조건을 만족하는 가능한 조합은 다음과 같습니다.

[4,1]
[3,2]

저와 같은 사람이라면 주어진 대상에 대해 위의 조건을 만족하는 모든 가능한 조합을 생성한 다음 해당 조합의 수를 반환하려고 할 것입니다.

이것도 유효한 접근 방식이고 작동할 수 있지만 약간의 문제가 있습니다.

대상이 300이고 주어진 nums 배열이 [1,2,3,4,5,6,7,8,9,........199]라고 상상해 보십시오.
이 경우 얼마나 많은 유효한 조합을 가질 수 있는지 상상할 수 있습니까? 많이 말하자!!!

일부 동적 프로그래밍 기술을 사용하여 Python으로 솔루션을 작성했지만 여전히 더 큰 숫자에 대한 조합을 계산할 수 없었습니다.

약간의 투쟁 후 나는 휴식을 취했습니다. 정원에 앉아 내 접근 방식을 반영하고 현재 접근 방식이 어느 정도만 솔루션을 제공할 수 있다면 유효한 솔루션이 될 수 없기 때문에 접근 방식을 변경해야 한다는 것을 깨달았습니다.

마지막으로 간단히 말하자면, 여러 수학 포럼을 읽은 후 이 문제가 partition이라는 수학 도메인과 관련되어 있다는 것을 알게 되었고 문제를 정말 최소한으로 해결하는 파이썬 코드를 작성하는 것이 정말 쉽다는 것을 이해했습니다. 시각.