분할 정복

 분할 정복은 다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임을 말한다.

 

 분할 정복(Divide and Conquer)은 직접 해결할 수 있을 정도로 간단한 문제가 될 때까지 문제를 재귀적으로 쪼개나간 다음, 그 하위 문제의 결과들을 조합하여 원래 문제의 결과로 만들어 낸다. 대표적인 분할 정복 알고리즘은 병합 정렬을 들 수 있는데, 병합 정렬 과정을 표현한 그림은 다음과 같다.

 

https://leetcode.com/problems/majority-element/submissions/

Majority Element - LeetCode

 

 

 1. 부르트 포스로 과반수 비교

 앞에서 부터 하나씩 과반수를 넘는지 일일이 체크하다가 과반수를 넘으면 바로 정답으로 처리하면 된다.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        for num in nums:
            if nums.count(num) > len(nums)//2:
                return num

 그러나 이 방법은 타임아웃이 발생한다.

 

 2. 다이나믹 프로그래밍

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        counts=collections.defaultdict(int)
        for num in nums:
            if counts[num] == 0:
                counts[num] = nums.count(num)
                
            if counts[num] > len(nums) //2:
                return num

 이 풀이는 메모이제이션을 이용한 매우 간단한 다이나믹 프로그래밍 풀이이다. 

 

 3. 분할 정복

 과반수 후보군에 해당하는 엘리멑느만 리턴하면서 다음 그림처럼 계속 위로 올려주면(즉, 백트래킹하면) 최종적으로 정답이 남게 된다.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        if not nums:
            return None
        if len(nums) == 1:
            return nums[0]
        
        half=len(nums) // 2
        a=self.majorityElement(nums[:half])
        b=self.majorityElement(nums[half:])
        print(nums,a,b)
        return [b,a][nums.count(a) > half]

 

 4. 파이썬 다운 방식

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return sorted(nums)[len(nums)//2]

 위 방법이 제일 빠르다.