[알고리즘]수학 알고리즘: 소수와 약수, 조합과 순열 🚀✨

반응형

수학 알고리즘은 다양한 문제를 빠르고 정확하게 해결하는 열쇠예요. 오늘은 대표적인 수학 알고리즘들과 그 활용법을 살펴보며 수학적 사고를 한층 업그레이드해 보아요! ✨

1. 소수와 약수 🌟

소수는 1과 자기 자신만으로 나누어지는 수로, 컴퓨터 과학에서 암호학, 난수 생성 등 많은 곳에서 활용돼요. 이와 관련한 대표적인 알고리즘으로 에라토스테네스의 체와 유클리드 호제법이 있어요!

에라토스테네스의 체 🧹

소수를 찾는 효율적인 알고리즘으로, 2부터 특정 숫자까지의 소수를 한 번에 구할 수 있어요.

public void sieveOfEratosthenes(int n) {
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            System.out.println(i + " is a prime number!");
        }
    }
}

핵심 포인트:

• 시간 복잡도: O(n log log n)으로 매우 빠르답니다! 🚀
• 활용 사례: 암호화, 소수 테스트, 수 이론 문제 해결 등.

유클리드 호제법 🤝

최대공약수를 구하는 대표적인 알고리즘으로, 재귀적으로 두 수의 나머지를 계산하며 답을 찾아요.

public int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

핵심 포인트:

• 시간 복잡도: O(log(min(a, b)))
• 활용 사례: 분수 간소화, 최소공배수 계산, 수학적 증명 등.

2. 조합과 순열 🎲

조합과 순열은 경우의 수를 계산하는 기본 도구로, 다양한 문제를 해결하는 데 쓰여요.

기본 구현

순열 생성

순열은 특정 원소들을 나열하는 모든 경우의 수를 구하는 방법이에요.

public void generatePermutations(String str, String result) {
    if (str.length() == 0) {
        System.out.println(result);
        return;
    }

    for (int i = 0; i < str.length(); i++) {
        char ch = str.charAt(i);
        String remaining = str.substring(0, i) + str.substring(i + 1);
        generatePermutations(remaining, result + ch);
    }
}

조합 생성

조합은 순서와 상관없이 원소를 선택하는 경우의 수를 구해요.

public void generateCombinations(String str, int start, String result) {
    System.out.println(result);
    for (int i = start; i < str.length(); i++) {
        generateCombinations(str, i + 1, result + str.charAt(i));
    }
}

효율적인 계산법 🧮

이항 계수 (nCk) 계산은 조합의 핵심이에요.

public int combination(int n, int k) {
    if (k == 0 || k == n) return 1;
    return combination(n - 1, k - 1) + combination(n - 1, k);
}

핵심 포인트:

• 동적 프로그래밍을 활용하면 중복 계산을 줄일 수 있어요.
• 활용 사례: 게임 확률 분석, 그래프 이론, 최적화 문제 등.

3. 모듈러 연산 ⚙️

모듈러 연산은 큰 수 계산과 암호화 알고리즘에서 매우 중요해요.

빠른 거듭제곱 🚀

거듭제곱을 효율적으로 계산하기 위해 분할 정복을 사용해요.

public long modularExponentiation(long base, long exp, long mod) {
    long result = 1;
    while (exp > 0) {
        if ((exp & 1) == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

핵심 포인트:

• 시간 복잡도: O(log(exp))
• 활용 사례: RSA 암호화, 큰 수 연산 등.

페르마의 소정리 🔑

소수와 모듈러 연산의 관계를 활용해 역원 계산을 간단히 할 수 있어요.

public long modularInverse(long a, long p) {
    return modularExponentiation(a, p - 2, p);
}

핵심 포인트:

• 조건: p는 소수여야 해요.
• 활용 사례: 암호학, 해시 충돌 방지, 분수의 모듈러 계산.

4. 기하 알고리즘 📐

기하 알고리즘은 공간 데이터를 다루는 데 필수적이에요.

선분 교차 여부 판별

public boolean doIntersect(Point p1, Point q1, Point p2, Point q2) {
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);

    if (o1 != o2 && o3 != o4) return true;

    return false;
}

private int orientation(Point p, Point q, Point r) {
    int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
    return (val == 0) ? 0 : (val > 0 ? 1 : 2);
}

활용 사례: 로봇 경로 계획, 게임 충돌 감지 등.

볼록 껍질 (Convex Hull)

다각형의 외곽선을 구하는 알고리즘으로, 그라함 스캔이 유명해요.

public List<Point> convexHull(Point[] points) {
    Arrays.sort(points, (p1, p2) -> p1.x == p2.x ? p1.y - p2.y : p1.x - p2.x);
    
    Stack<Point> hull = new Stack<>();
    for (Point p : points) {
        while (hull.size() >= 2 && cross(hull.get(hull.size() - 2), hull.peek(), p) <= 0) {
            hull.pop();
        }
        hull.push(p);
    }
    return new ArrayList<>(hull);
}

private int cross(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

활용 사례: 지도 데이터 처리, 컴퓨터 그래픽스, 데이터 시각화 등.

마무리 🎉

수학 알고리즘은 복잡한 문제를 풀기 위한 강력한 도구예요! 에라토스테네스의 체로 소수를 구하고, 조합과 순열로 경우의 수를 계산하며, 모듈러 연산과 기하 알고리즘으로 더 멋진 문제를 해결해 보세요. 🌟 여러분의 창의적인 아이디어와 결합한다면 더 큰 가능성이 열릴 거예요!