[SCCC 스터디] 5일차 분할정복

SCCC 스터디 5일차 1月 15日

오늘은 미세먼지로 인해 전날 스터디 모임이 취소가 됬다. 그래도 배울 내용은 적어 홈스터디로 진행됬다.

1. 분할정복

분할정복은 Divide and Conquer로 문제를 같은 유형의 여러 작은 문제들로 나눈 뒤, 그 작은 문제들의 답을 이용해서 문제를 해결하는 방식을 말한다.

분할정복을 이용하면 시간 복잡도를 줄일 수 있다.

예를 들어, 1부터 100까지 더하는 것을 공식을 이용하지 않고 더한다면 아주 간단하게 O(n)로 더할수는 있다. 하지만 분할정복을 이용하면 O(log n)으로 더 줄일 수 있다.

1 + 2 + 3 + ... + 51 + 52 + 53 + ... + 99 + 100

이를 한번 Divide(분할)을 해보자.

1 + 2 + 3 + ... + 50 + (50 + 1) + (50 + 2) + (50 + 3) + ... + (50 + 50) = (1 + 2 + 3 + ... + 50) + (1 + 2 + 3 + ... + 50) + 50 * 50

1부터 100까지 계산하는 것을 반으로 줄이면 1부터 50까지 계산하는걸로 줄여 더 효율적으로 계산할 수 있게 된다. 이를 n(짝수)를 이용해서 표현해보자. 

만약, n이 홀수이면 어떻게 될까.

일단 홀수 중 1일 때를 생각해보자. n이 1이라면 그 결과는 당연히 1이다.

1이 아닌 홀수 일땐 어떻게 해야할까? 

그냥 단순하게 n이 홀수이면 짝수로 만들어 위에서 만든 식을 적용하면 된다. 즉 sum(n) = n + sum(n-1)로 만들어 계산하면 된다. 이를 하나의 식으로 쓰면 아래와 같다.

1. 1부터 n까지 O(n)만에 계산하는 소스이다.

#include<iostream>
 
using namespace std;
 
int sum(int n)
{
    if(n == 1)return 1;
    else return n + sum(n - 1);
}
 
int main()
{
    int n = 100;
    cout << sum(n);
    return 0;
}
 

2. 분할정복을 이용하여 O(log n)만에 계산하는 소스이다.

#include<iostream>
 
using namespace std;
 
int sum(int n)
{
    if(n == 1)return 1;
    else if(n & 1)return n + sum(n-1);
    else
    {
        int result = sum(n / 2);
        return result * 2 + n * n / 4;
    }
}
 
int main()
{
    int n = 100;
    cout << sum(n);
    return 0;
}
 

1. 곱셈 - ●◐○○○

2. 숫자 카드 - ●◐○○○

3. 종이의 개수 - ●●◐○○

4. Z - ●●○○○

5. 쿼드트리 - ●●○○○

6. 부분배열 고르기 - 아직 안품

7. 별 찍기 - 10  - ●●○○○

8. 석판 자르기 - 아직 안품

9. 별 찍기 - 18 - 아직 안품

10. 별 찍기 - 11  - ●●◐○○