[자료구조&알고리즘 | WEEK02] 분할 정복(Divide and Conquer)

분할 정복(Divide and Conquer)

---

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

 

 

분할 정복(Divide and conquer)은 직접 해결할 수 있을 정도로 간단한 문제가 될 때까지 문제를 재귀적으로 쪼개나간 다음, 그 하위 문제의 결과들을 조합하여 원래 문제의 결과로 만들어 낸다.

대표적인 분할 정복 알고리즘으로는 병합 정렬이 있다.

 

 

 

위의 이미지에 보이듯이 병합 정렬은

1. 상단에서 '분할' 하고,
2. 중앙에서 '정복' 하고,
3. 하단에서 '조합' 한다.

이를 좀 더 구체적으로 살펴보면 아래의 이미지와 같다.

 

 

 

중요 개념 정리

분할: 문제를 동일한 유형의 여러 하위 문제로 나눈다.

정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.
조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.

 

 

💡

분할 정복이란?

말 그대로 문제를 '분할'해서 '정복'한 다음 정답을 '조합'해 나간다는 의미이다.

 

분할 정복은 재귀를 활용하는 대표적인 알고리즘이다.

바로 문제를 풀어보면서 알아보자.

 

분할 탐색으로 문제 풀어보기

---

파이썬 알고리즘 인터뷰 책을 참고하여 풀이하였습니다.
문제 설명은 아래의 링크로 대체!

리트코드 - 169번

Majority Element - LeetCode

 

분할 정복 풀이

책에서 설명하는 이 문제의 풀이 방법은 병합 정렬처럼 문제를 분할, 정복, 조합의 풀이 방식과 달리,

분할, 정복(백트래킹 사용)으로 문제를 풀이하고 있다.

과반수 후보군에 해당하는 엘리먼트만 리턴하는 방식이다.

(문제에서 요구하는 바는 하나의 배열 안에 있는 엘리먼트들 중 과반수 후보군들을 뽑아내는 것임)

 

1. 분할 하기

먼저 문제를 잘게 쪼개는 '분할' 단계를 진행한다.

이렇게 분할할 시 a와 b는 각각 최소 단위까지 쪼개질 것이다.

def majorityElement(nums):
	...
    
    # 재귀적으로 분할
    a = majorityElement(nums[:len(nums) // 2]) # 반으로 나눠서 왼쪽 분할
    b = majorityElement(nums[len(nums) // 2:]) # 반으로 나눠서 오른쪽 분할

	...

 

2. 재귀 함수의 필수 조건 | 종료 조건 추가

재귀 함수에서는 종료 조건을 지정해주지 않을 시 무한적으로 깊게 들어가므로 꼭 종료 조건이 필요하다.

(종료 조건이 없을 시 스택 오버 플로우 발생)

이제 이렇게 종료 조건을 추가해주면, 최소 단위로 쪼개질 때 해당하는 값을 리턴하게 될 것이다.

1주 차에 재귀 함수를 정리하지 못했는데 시간을 내서 꼭 정리해 봐야겠다!

def majorityElement(nums):
    # 종료 조건
    if not nums:
        return None

    if len(nums) == 1:
        return nums[0]

    # 재귀적으로 분할
    a = majorityElement(nums[:len(nums) // 2])
    b = majorityElement(nums[len(nums) // 2:])
	...

 

3. 정복(백트래킹 사용)

최종적으로 결과 값을 돌려주어 과반수 후보군을 뽑아내는 코드이다.

def def majorityElement(nums):
	...
	return [b, a][nums.count(a) > len(nums) // 2]

 

위의 코드에서 return 부분이 이해가 안되서 찾아보았다. [추가하기]

 

💡

return [b, a][True or False]의 의미

 

실습을 하면서 아래의 웹 사이트의 도움을 받았다.

아래의 사이트는 디버깅하는 과정을 시각적으로 표현해주는데,

아직 재귀적으로 동작하는 과정을 파악하기 어려운 것 같아 이용했다.

파이썬 디버깅 비주얼하게 확인하기

Python Tutor: Learn Python, JavaScript, C, C++, and Java programming by visualizing code

 

첫 번째로 분할 되는 과정 | 왼쪽

왼쪽의 빨간색으로 밑줄 친 부분에서 배열 전체에서 반을 잘라 왼쪽의 원소들이 분할된 모습(잘게 쪼개는 과정)

 

두 번째로 분할되는 과정 | 첫 번째 분할의 왼쪽

위의 if 문은 아직 조건에 만족하지 않기 때문에 그냥 지나쳤다.

따라서 아직 더 문제를 잘게 쪼갤 수 있다는 뜻!

위에서 반으로 쪼개진 배열에서 한번 더 왼쪽을 기준으로 쪼개졌다.

이제는 더이상 쪼갤 수 있는 원소가 없다.

 

종료 조건 실행

첫 번째로 종료 조건에 충족하고 return 되었다.

 

더 이상 분할이 불가능한 원소에 대해 종료 조건이 실행되었고 a의 변수에 할당된 모습

백트래킹 되어 a의 배열에서는 '2' 값이 과반수 후보군이 되었다.(최소의 단위에서 첫 번째로 '정복'한 모습)

 

세 번째로 분할되는 과정

왼쪽 분할을 마치고, 오른쪽을 최소한의 원소로 쪼개는 과정(분할)을 할 차례다.

아직은 쪼갤 원소가 있으니 한번 더 쪼개야 할 것 같다.

 

 

네 번째로 분할되는 과정

오른쪽으로 쪼개진 배열에서 원소는 2개였고, 한번 더 왼쪽으로 분할한다.

원소를 최소 단위까지 쪼개었고, a 변수에는 2가 들어간다.

 

다섯 번째로 분할 되는 과정

오른쪽 원소도 마침내 더이상 쪼갤 수 없을 때까지 쪼개었고, 분할을 완료하였다.

(배열 전체에서 반에 해당하는 왼쪽 부분만)

b 변수에 1이 들어감

 

최소로 쪼갠 원자들에서 첫 번째 return

return 문의 count함수를 사용해서 조건을 판단하였고, b = 1이라는 값이 도출되었다.

그 말은 최소로 쪼갠 원소들(현재는 오른쪽[2,1]을 바라보고 있음)에서 '1' 이라는 값이 과반수 후보군이라는 뜻이다.

코드로 나타내면 아래와 같다.

num = [2,1] # 현재 분할되어 (2,1) 원소 밖에 없음 - 오른쪽 배열

[nums.count(a) > len(num) // 2] # --> False

return b

 

정복과정

드디어 전체 배열 nums에서 왼쪽으로 반으로 쪼갠 부분이 해결되었다.

즉, 문제들을 잘게 쪼개어(분할) 해결해 봤더니(정복), 큰 문제가 풀리더라(조합)

자세한 설명은 이미지를 참고하면 될 것 같다.

 

 

오른쪽의 과정은 생략하겠습니다...

이렇게해서 최종적으로 '2'가 전체 배열에서 과반수 후보군으로 뽑혔다.

확실히 문제를 하나씩 시각적으로 풀어보니 그 복잡하던 재귀가 어느정도 이해가 된 것 같다.

전체 코드는 아래와 같다.

 

4. 전체 코드

def majorityElement(nums):
    # 종료 조건
    if not nums:
        return None

    if len(nums) == 1:
        return nums[0]

    # 재귀적으로 분할
    a = majorityElement(nums[:len(nums) // 2])
    b = majorityElement(nums[len(nums) // 2:])
	
    # a 값이 True면(과반수 후보군이라면) a 출력 / 아니면 b 출력
    return [b, a][nums.count(a) > len(nums) // 2]

 

 

 

---

Ref

위키백과 - 분할 정복 알고리즘
나무위키 - 분할 정복 알고리즘
파이썬 알고리즘 인터뷰