[종만북][알고스팟] 수열의 빠른 합 - 재귀(Recursive) + 완전탐색(BruteForce) + 분할정복(DivideandConquer) JAVA

출처 : 종만북 07 분할정복 - 예제 : 수열의 빠른 합과 행렬의 빠른 제곱

코드설명

수열의 빠른 합을 구하는 방식입니다.

 

1+2+3+4+5+ ... N 까지의 수열이 존재한다고 가정합니다.

 

총 4가지 방법이 가능합니다.

 

첫번쨰는, 일반적인 반복문입니다. 너무 간단한 방법이기에 넘어갑니다.

 

두번째, 재귀로 구현한 방식입니다.

더이상 쪼개지지 않을떄까지, 즉 숫자가 1이 될때까지 계속해서 recursiveSum(n-1)을 호출하며, 마지막에는 n 을 반환합니다.(사실상 1 이겠지요.) 

시간복잡도는 각 부분문제의 시간복잡도는 O(1) (상수 시간 작업) 이고, 부분 문제의 개수는 'n'개입니다. 즉 O(n)입니다.

 

세번쨰, 일반 분할정복입니다.(네번쨰 방법보다 느립니다.)

호출과정은, 분할정복이니 배열을 반으로 나누는 과정들을 계속해서 진행합니다.

호출은 아래와 같이 진행될 것 입니다.

왼쪽 절반 : divideAndConquerSum(A, left, mid)
오른쪽 절반 : divideAndConquerSum(A, mid+1, right)

시간복잡도는 O(log N)입니다. 문득 보면 O(N LOG N) 처럼 보일 수 있지만, 각 부분 문제 내에서의 시간복잡도가 O(1)이기에 O(1) * O(LOG N)으로 전체 시간복잡도는 O( LOG N ) 입니다. (시간복잡도 계산 방법은, 부분문제의 개수 * 부분 문제의 시간복잡도),

 

네번째는, 수학식을 이용한 분할정복입니다. 분할정복은 두번째 방식인 재귀를 문제를 2개로 나누어서 부분문제로 푸는 방식입니다.

분할정복 구현을 위해 fastSum() 함수를 구현합니다. 

fastSum()은 1부터 n까지의 합을 n개의 조각으로 나눈뒤, 이들을 반으로 뚝 잘라 n/2개의 조각들로 만들어진 부분 문제 두 개를 만듭니다. ( 편의상 n은 짝수라고 가정합니다. )

fastSum() = 1 + 2 + 3 +  ... n  

= (1 + 2 + ... + n / 2) + ( (n/2 + 1) + (n/2 + 2) + (n/2 + 3) + ... + (n/2 + n/2))

로 두가지 부분문제로 나눌 수 있습니다.

 

첫번쨰 부분 문제인  (1 + 2 + ... + n / 2)는 fastSum(n/2)로 나눌 수 있습니다.

두번쨰 부분문제인 ( (n/2 + 1) + (n/2 + 2) + (n/2 + 3) + ... + (n/2 + n/2) ) 는 fastSum() 함수를 통해서 표현할 수 없습니다. 이유는 fastSum(k)은 1부터 k까지의 합을 의미하는 숫자입니다.

 

문제를 재귀적으로 풀기 위해서는 각 부분 문제를 '1부터 n까지의 합' 꼴로 표현해야하는데, 위의 분할에서 두번째 조각은 'a부터 b까지의 합' 형태를 가지고 있습니다. 따라서 다음과 같이 두번쨰 부분문제를 fastSum(k)를 포함하는 형태로 바꿉니다.

( (n/2 + 1) + (n/2 + 2) + (n/2 + 3) + ... + (n/2 + n/2)) 

= n/2 * n/2 + (1 + 2 + 3 + ... + n/2) 

= n/2 * n/2 + fastSum(n/2)

 

공통된 항 n/2을 따로 빼내면 놀랍게도  fastSum(n/2)이 나타납니다. 

따라서 다음과 같이 쓸 수 있습니다.

fastSum(n) = 2 x fastSum(n/2) + n^2 / 4 ( n이 짝수일때)

 

이러한 아이디어를 구현하면 다음과 같습니다.

//필수 조건 : n은 자연수
//1 + 2 + 3 + ... + n 을 반환한다.
public static int fastSum(int n) {
    //기저 사례
    if(n == 1) return 1;
    if(n % 2 == 1) return fastSum(n-1) + n; //홀수인 입력이 주어질때는 짝수인 n -1 까지의 합을 재귀호출로 계산하고 n을 더해 답을 구합니다.
    return 2*fastSum(n/2) + (n/2) * (n / 2);
}

 

 

입력 예시 1

1부터 10까지의 수열 합을 구하라는 의미입니다.

10

 

결과 예시 1

55

 

입력예시 2

24

결과 예시 2

300

 

시간복잡도 비교

 

fastSum() : 분할정복을 활용한 코드와  recursiveSum() : 재귀함수를 활용한 코드 의 시간은 어떤것이 더 빠를까요?

두 함수 모두 내부에 반복문이 없기에 fastSum()과 recursiveSum()이 종료하는데 걸리는 시간은 순전히 함수가 호출되는 횟수에 비례하게 됩니다. recursiveSum()의 경우 n번의 함수 호출이 필요하다는 것을 쉽게 알 수 있습니다. 반면 fastSum()은 호출될 때마다 최소한 두번에 한번 꼴로 n이 절반으로 줄어듭니다. (홀수의 경우는 1번 줄어들기에 그렇습니다 예로 들면 10 이 들어올경우 10 : 짝수 5 : 홀수 4 : 짝수 2 : 짝수 1 : 반환 1) . 그러니 fastSum()의 호출횟수가 훨씬 적으리란 것을 알 수 있습니다.

 

fastSum(11)을 실행할때 재귀호출의 입력이 어떻게 변화하는지 표현합니다.

 

- fastSum 내의 숫자는 2진수입니다.

fastSum(1011) = fastSum(1010) + 11 // 11은 홀수이므로 짝수로 변환합니다.

fastSum(1010) = fastSum(101) x 2 + (5*5) // 10은 짝수이므로 2*fastSum(10/2) + (10/2)*(10/2)

fastSum(101) = fastSum(100) + 5 // 5은 홀수이므로 짝수로 변환하고 5(홀수를 더합니다)

fastSum(100) = fastSum(10) x 2 + (4/2)(4/2) // 4는 짝수이므로 2*fastSum(4/2) + 2*2

fastSum(10) = fastSum(1) x 2 + (2/2)(2/2) // 2는 짝수이므로 2*fastSum(2/2) + 1

fastSum(1) = 1 // 1일경우 return 1 합니다.

 

재귀호출을 할떄 n의 이진수 표현의 마지막 자리가 1이면 0 으로 바뀌고,  ( 마지막 자리가 1이라는 의미는 홀수라는 의미입니다. ), 마지막 자리가 0 이면 끝자리가 없어집니다.( 마지막 자리가 0 이라는 의미는 짝수라는 의미이고, 반으로 나누기에 그렇습니다. >> 오른쪽으로 시프팅한개를 하면 나누기가 되는 것과 같은 원리입니다. )

따라서 fastSum()의 총 호출 횟수는 n의 이진수 표현의 자릿수(>> 오른쪽 시프팅 횟수, 즉 나누기 횟수)  + 첫 자리를 제외하고 나타나는 1의 개수(첫자리를 제외하는 이유는 마지막에 가장 맨 앞 자리는 1이 되기에 멈추기에 그렇습니다)가 됩니다. 

두 값의 상환은 모두 lg n 이므로 이 알고리즘의 실행 시간은 O(lg n)입니다.

코드

두번쨰 방법인, 간단히 재귀로 구하는 함수입니다. 시간복잡도는 O(N)입니다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.security.Timestamp;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M, H, W;
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		System.out.println(recursiveSum(N));
	}
	public static int recursiveSum(int n) {
		if(n == 1) return n;
		return recursiveSum(n-1) + n;
	}
}

 

세번쨰 방법인, 일반 분할정복입니다.(다음 방법의 분할정복보다 느립니다. 시간복잡도는 O(logn))입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.security.Timestamp;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M, H, W;
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		System.out.println(recursiveSum(N));
		
		System.out.println(divideAndConquerSum(1, N));

	}
	public static int divideAndConquerSum(int left, int right) {
		if(left == right) {
			return right;
		}
		int mid = (left + right) / 2;
		int leftSum = divideAndConquerSum(left, mid);
		int rightSum = divideAndConquerSum(mid+1, right);
		return leftSum + rightSum;
	}
	
}

 

네번쨰, 수식을 이용한 분할정복.시간복잡도는 O(log N)

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int N, M, C;
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		answer = getSum(N);
		System.out.println(answer);
		System.out.println(recursiveSum(N));
	}
	//일반 반복문입니다.
	public static int getSum(int n) {
		int sum = 0;
		for(int i=1; i<=n;i++) {
			sum += i;
		}
		return sum;
	}

	//Top-Down 방식의 재귀입니다.
	public static int recursiveSum(int n) {
		if(n == 1) return n; //더이상 쪼개지지 않을떄
		return n + recursiveSum(n - 1);
	}
    
    public static int divideAndConquerSum(int left, int right) {
        if(left == right) {
            return right;
        }
        int mid = (left + right) / 2;
        int leftSum = divideAndConquerSum(left, mid);
        int rightSum = divideAndConquerSum(mid+1, right);
        return leftSum + rightSum;
	}
	
	
	//필수 조건 : n은 자연수
	//1 + 2 + 3 + ... + n 을 반환한다.
	public static int fastSum(int n) {
		//기저 사례
		if(n == 1) return 1;
		if(n % 2 == 1) return fastSum(n-1) + n; //홀수인 입력이 주어질때는 짝수인 n -1 까지의 합을 재귀호출로 계산하고 n을 더해 답을 구합니다.
		return 2*fastSum(n/2) + (n/2) * (n / 2);
	}
	
	
	
}