본문 바로가기

Programming/알고리즘

분할 정복법과 동적 계획법 (feat. 피보나치 함수)

 

1. 반복문

 

반복문을 이용한 피보나치 함수.

 

시간 복잡도: O(n)

 

 

2. 재귀 호출

 

재귀적 호출을 이용한 풀이법. 시간 복잡도로 인해 Stack Overflow가 자주 발생한다.

 

* 참고 *

여기서 헷갈릴 수도 있는데, 피보나치에서 일반적인 재귀 호출은 엄밀히 말하면 분할 정복법이 아니다. 일반적으로 분할 정복법은 현재 문제를 어떤 원칙에 의해 개별적인 문제들로 분할한 뒤, 결과값을 적절히 합산 (정복)해야 하는데, 피보나치의 경우 기본적인 원칙도 세우지 않고 단순히 모든 경우의 재귀를 모두 호출하여 중복되는 경우를 모두 포함해서 다 더하기만 할 뿐이다. 따라서 문제를 분할하더라도 중복된 연산으로 인해 연산의 횟수가 줄어들지 않고, exponential한 시간 복잡도를 갖게 된다.

 

시간 복잡도: O(2n)

 

 

3. 동적 계획법

 

큰 문제를 작은 조각으로 나누어 풀 때, 작은 조각을 통해 얻은 정보로 더 큰 부분 문제를 해결하는 방법.

분할 정복법과의 핵심적인 차이는 Memoization에 있다.

 

* Memoization: 시간 비용으로 인해 발생하는 문제를 공간 비용(Cache)을 투입해 해결하는 기법이다. (Memorization X)

 

시간 복잡도: O(n)

 

그 외 대표적인 동적 계획법 문제에는 Knapsack, 편집 거리, 최장 공통 부분수열 (LCS), 최장 증가 부분 수열 (LIS) 등이 있다.

 

 

4. 분할 정복법

 

큰 문제를 작은 조각으로 나누어 푼 뒤 다시 합쳐서 문제를 해결하는 방법.

 

기본적으로 피보나치 수는 다음 점화식이 성립한다.

위에서 소개한 기법들은 모두 해당 점화식을 일일히 전개하는 방식으로 구현했다. 하지만 다음과 같이 행렬로도 규칙성을 표현할 수 있다.

 

 

이를 다음과 같이 정리할 수 있다.

 

이제 우리는 점화식이 아닌 행렬의 거듭 곱셈으로 표현되는 Fn의 일반항에 대한 공식을 구했으니, 행렬을 매번 거듭해서 곱하는 대신, 다음 공식을 이용해 분할 정복법으로 문제를 풀 수 있게 됐다.

 

수학적 개념이 굉장히 많이 나와서 당황했을텐데, 실제로 대회에서 이 정도까지 접근해서 푸는 것은 당연히 힘들 수 있다. 대신 이 문제는 꽤 유명한 접근법이기에, 지금은 공부한다고 생각하고 잘 익히는 데 초점을 두자.

 

관련 문제: BOJ 11444 피보나치 수 6

 

시간 복잡도: O(log n)

GitHub

 

그 외 대표적인 분할 정복법 문제에는 합병 정렬, 퀵 정렬, 연속 부분 최대합 문제 등이 있다.

 

 

참고 사이트

피보나치 수를 구하는 여러가지 방법