[sw정글 2주차] 분할하고 정복해버리기

Date: 2022.10.04 Updated: 2022.10.04

카테고리: swjungle survive

태그: Algorithm swjungle

📚SW정글 2.9주

✂️분할정복

분할정복이란 무엇일까?

분할정복이란 문제를 분할-정복-결합 과정을 통해 풀어나가는 방법이다. 따라서 아래와 같이 3가지 개념은 간략히 정의한다.

분할
- 현재의 문제와 동일하되 입력의 크기가 더 작은 다수의 부분 문제로 분할
정복
- 부분 문제를 재귀적으로 풀어서 정복한다. 부분 문제의 크기가 충분히 작으면 직접적인 방법으로 푼다.
결합
- 부분 문제의 해를 결합해 원래 문제의 해가 되도록 만든다

그렇다. 분할정복은 재귀로 푸는것이다.

⭕️점근적 표기법

점근적 표기법(asymptotic notation)이란 무엇일까?

일반적으로 우리는 Time-complexity를 O(n)과 같은 방법으로 표기한다. 이러한 방법을 Big-O 라고 하는데, 이는 점근표기법 중 하나인 것이다. 그 외에도 오메가(Ω) 표기법, 대문자 세타(Θ) 표기법, 소문자 o 표기법, 소문자 오메가(ω) 표기법 등 다섯 종류가 있다. 하지만 최악의 순간에 대해 가정하는 Big-O가 사용할일이 많고 이는 가장 자주쓰이는 점근표기법이 된것이다.

🚀점화식을 푸는 3가지 방법

그럼 점화식을 어떻게 풀면 좋을까? 좋은 추측식을 통해, 분할정복 문제를 점화식으로 멋있게 풀어 낼 수 있는 절대적 방법이 있으면 좋겠지만… 그런 방법은 존재하지 않는다. 1000쪽짜리 전공서적에서도 말한다. 수많은 경험과 창의력으로 문제 해결방법을 찾아낼 수 있겠지만, 이를 해결하기 위한, 찾아내기 위한 절대적 방법은 없다고 한다.

그럼에도 불구하고 점화식을 풀기 위해 도움을 줄 수 있는 3가지 방법을 소개하고자 한다.

치환법
재귀트리방법
마스터 방법

🎅🏽치환법

점화식을 풀기 위한 치환법은 다음의 두 단계를 거친다.

해의 모양을 추측한다.

상수들의 값을 알아내기 위해 수학적 귀납법을 사용하고, 그 해가 제대로 동작함을 보인다.

단계 2에서 수학적 귀납법을 사용할 때, 더 작은 문제에 대하여 단계 1에서 추측한 해로 치환한다. 그렇기 때문에 이 방법의 이름이 치환법인 것이다.

아주 강력한 방법이다. 하지만 이를 적용하기 위해서는 해의 모양을 추측할 수 있어야 한다. 또한, 특정 한계 조건, 예를들어 n=1일때, n=0일때 등 특수한 조건에 대해서도 수식이 들어맞을 수 있음을 알아야 한다.

🎄재귀트리방법

재귀트리(recursion tree)는 각 노드가 재귀호출의 레벨에 따른 비용을 나타내도록 만든 트리이다. 총 비용을 결정하기 위해 모든 레벨당 비용을 합해야 한다. 이는 각 레벨당 비용을 알아야 하는데, 이 비용을 트리의 레벨별 모든 노드의 비용을 합함으로써 얻을 수 있다.

🔐마스터 방법

마스터 방법이다. 말 그대로 master이다. 아주유용하다. 세가지 경우에 대한 암기가 필요하지만 한 번만 기억해두면 비용을 계산하는데 최고의 방법을 보여준다.

그 세가지 방법

g(n)이 더 무거우면 g(n)이 수행시간을 결정한다
f(n)이 더 무거우면 g(n)이 수행시간을 결정한다
g(n)과 f(n)이 같은 무게이면 g(n)에 logn을 곱한 것이 수행시간이 된다

마스터방법이란 T(n) = aT(n/b) + f(n) 과 같은 형식으로 된 점화식의 답을 제시해 주는 방법이다. 고급 알고리즘 문제들을 풀어 나갈 때, 알고리즘 해결에 소요되는 비용을 측정할 수 있기 때문에 사용한다. 사실 위의 두가지 방법들 모두 그 비용을 계산하는데 쓰인다. 따라서 설명을 이어나가는 세 가지 방법들 모두 점화식을 풀 수 있는 창의적인 아이디어를 준다기 보다는, 생각 해 볼 수 있는 아이디어들의 비용을 계산 할 수 있도록 도와주는 방법들인 것이다.

그럼에도 불구하고 많은 분할정복(재귀문제)에 속하는 문제들을 대표 할 수 있는 두가지 문제를 소개하고자 한다.

(1)최대-부분배열 문제와 (2)행렬의-곱 문제를 마스터 방법으로 풀어낼 것이다.

✂️분할정복의 대표적인 예1

주식을 사고 팔아서 우리는 이윤을 남길 수 있다. 그렇다면 어떠한 경우에 최대의 이윤을 남길 수 있을까? 매일 매일 가격변동에 대한 데이터들이 있을 것이고, 우리는 “이쯤에서 팔아서 저 때 팔면 좋았을 텐데…” 라는 생각을 할 수 있을 것이다.

주식의 등락폭에 대한 데이터가 주어져 있을 때, 이를 구할 수 있는 최대 부분배열은 어떻게 구할 수 있을까?

전공서적에서는 먼저 주먹구구식 풀이를 설명한다. 모든 날에 대하여 nC2 를 함으로써 최대 부분배열 중 하나를 얻을 수 있을 것이다. 그렇다면 O(n²) 이 나올 것이다. 그렇다면 어떻게 분할정복 문제로 풀 수 있을까?

이를 분할정복 문제로 풀면 O(n_logn)의 시간복잡도로 풀어낼 수 있다.

행렬을 A[low, mid]와 A[mid+1, high]로 분할하는 것이다. 이를 통해, 왼쪽에서의 최대 부분배열과 오른쪽에서의 최대 부분 배열을 통해 값을 알아 낼 수 있는 것이다. 이에대한 코드를 아래에 첨부한다.

부분 배열 문제 코드 스니펫(분할정복)

def Find-Max-Crossing-Subarray(): #FMCS
	for i = mid downto low
		sum 구하기
		max-left = i
	
	for j = mid+1 to high
		sum 구하기
		max-right = j
	
	return (max-left, max-right, left-sum + right-sum)

def Find-Max-Crossing-Subarray(): #FMCS
for i = mid downto low
sum 구하기
max-left = i
for j = mid+1 to high
sum 구하기
max-right = j
return (max-left, max-right, left-sum + right-sum)

그렇다. 왼쪽의 최대부분배열과 오른쪽의 최대부분배열을 합친다고 새로운 최대값을 보장하지 않는다. 따라서 cross-row 와 cross-high로 합성해낸 값이 더욱 큰 값인지 확인하여야 하는 것이다.

시간복잡도는 다음과 같다.

T(n)
- n = 1: O(1)
- n > 1: 2T(n/2) + O(n)

따라서 결과적으로, T(n) = O(n_logn) 이 된다.

✂️분할정복의 대표적인 예2

두번째 예시는 행렬곱셈을 위한 스트라센 알고리즘 이다.

일단 행렬의 곱셈은 다음과 같이 분할시킬 수 있다.

그리고 이를 다음과 같이 한번 더 분할할 수 있고, 이어서 계속 분할 해 나갈 수 있다.

그렇다면 O(n³)이나 걸리던 문제는, 분할정복으로 아름답게 풀면 얼마로 줄어들까?

위의 연산을 다 더하면 => 8T(n/2) + O(n^2) 이 된다. 이를 마스터 방법으로 계산하면.. Time-complexity는 O(n³) 이 된다.

그렇다면… 시간도 줄어들지 않는 스트라센 알고리즘을 왜쓸까요? 그렇다 여기서 이제 진가가 발휘된다.

방금 나누었던 연산들은 다음과 같이 표현할 수 있다. 4부분으로 나누었던 행렬들은 7가지 종류의 다항식들의 합으로 표현될 수 있다.

고로, 8번 연산해야할 행렬의 곱이 7번으로 줄어들게 되고, T(n) = O(n^log_ba) = O(n^2.81) 이 된다.

보다시피 3제곱을 약 2.81제곱으로 바꾸긴하였으나… 구현 방법이 복잡해진다. 따라서 여러가지 조건을 이유로, 행렬의 크기 N이 충분히 커야 실 사용시간이 개선된다고 한다.

😵배우면서 깨달은 내용을 정리해 보았습니다. 오개념을 아래 댓글에 달아주시면 감사하겠습니다😵

🌜 Thank you for reading it. Please leave your comments below😄

맨 위로 이동하기

Sunny Yoon