[SCCC 스터디] 6일차 수학1

SCCC 스터디 5일차 1月 16日

(수학 어렵다.........................)

1. 수학1

에라토스테네스의 체 - N 이하의 소수를 빠르게 찾는 알고리즘이다. 

소수의 배수를 없애는 방식으로 진행한다. 자세한 내용은 여기에서 참고하면 될 것이다.

이 방법을 이용하면 시간복잡도는 O(n log log n)이다. 

유클리드 호제법 - 최대공약수(GCD)를 빠르게 구하는 알고리즘이다.

나머지 연산을 이용해서 빨리 구할 수 있는데 이에 대한 자세한 내용은 여기에서 참고하면 될 것이다.

에라토스테네스의 체 - 소수인지 판별하는 방식은 거의 동일하지만 소스코드를 작성할때 살짝 다른게 있다. 다른 곳에서 계산과정 중 오버플로우를 방지하기 위해서 사용한다고 들었다. 

- 에라토스테네스

1. 에라토스테네스의 체_1

#include<iostream>
 
using namespace std;
 
bool isprime[10005];
int main()
{
    int n = 10000;
    for(int i=2;i<=n;i++)isprime[i]=true;
    for(int i=2;i*i<=n;i++)
        if(isprime[i])
            for(int j=i*i;j<=n;j+=i)
                isprime[j]=false;
    return 0;
}
 

2. 에라토스테네스의 체_2

#include<iostream>
 
using namespace std;
 
bool isprime[10005];
int main()
{
    int n = 10000;
    for(int i=2;i<=n;i++)isprime[i]=true;
    for(int i=2;i<=n;i++)
        if(isprime[i])
            for(int j=i+i;j<=n;j+=i)
                isprime[j]=false;
    return 0;
}
 

3. 에라토스테네스의 체_3

#include<iostream>
 
using namespace std;
 
bool isprime[10005];
int main()
{
    int n = 5000;
    for(int i=2;i<=n;i++)isprime[i]=true;
    for(int i=2;i*i<=n;i++)
        if(isprime[i])
            for(int j=i+i;j<=n;j+=i)
                isprime[j]=false;
    return 0;
}
 

사실 아직 자세히 고민을 하지 못해봤다. (최근 백준에 자동 제출하고 AC가 뜨면 그 소스를 Github에 올리는 프로그램을 제작 중이다.)

- 유클리드 호제법

#include<iostream>
 
using namespace std;
 
int gcd(int a, int b)
{
    if(a<b)return gcd(b,a);
    if(!b)return a;
    return gcd(b,a%b);
}
 
int main()
{
    cout << gcd(10,4);
    return 0;
}
 

gcd함수에서 a가 b보다 항상 커야한다. gcd 함수를 불러오기 전에 미리 처리하면 되긴 하지만 난 함수 내에서 처리하게 해놨다.

1. 최대공약수와 최소공배수 - ◐○○○○

2. 소수 찾기 - ◐○○○○

3. 더하기 사이클 - ◐○○○○

4. 초콜릿 자르기 - ◐○○○○

5. 플러그 - ●○○○○

6. 수들의 합 - ●◐○○○

7. 검문 - ●●●○○

8. 연속합 - ●●●○○ (은근 어려울 수 있다.)

9. 16진수 - ◐○○○○

10. 8진수 2진수 - ●●◐○○

11. 행성 x3 - ●●◐○○

12. 기차가 어둠을 헤치고 은하수를 - ●◐○○○

13. 음식 평론가 - ●◐○○○

14. 엑셀 - 아직 안품

15. 콜라츠 - 아직 안품

16. 뒤집기 3 - 아직 안품