코딩테스트 필수 수학 개념

1. 나머지 연산(Modulo Operation)

나눗셈의 나머지를 구하는 연산. 표기는 mod로 하고 프로그래밍 언어에서는 대부분 %연산자로 사용한다. 
나머지 연산의 경우 아래와 같이 분배법칙이 가능한데 사칙 연산 중 나눗셈 연산을 제외하고 적용된다.

(A+B)%C = (A%C + B%C)%C

(A-B)%C = (A%C - B%C)%C

(A*B)%C = (A%C * B%C)%C

/**
 * 나머지 연산
 */
public static void modulo() {
    System.out.println(" 5 % 3 = " + 5 % 3);
    System.out.println("10 % 3 = " + 10 % 3);
    System.out.println("10 % 2 = " + 10 % 2);

    int A = 24;
    int B = 15;
    int C =  7;

    System.out.print("(A+B)%C, (A%C + B%C)%C = " + (A+B)%C);
    System.out.println(" " + (A%C + B%C)%C);
    System.out.print("(A-B)%C, (A%C - B%C)%C = " + (A-B)%C);
    System.out.println(" " + (A%C - B%C)%C);
    System.out.print("(A*B)%C, (A%C * B%C)%C = " + (A*B)%C);
    System.out.println(" " + (A%C * B%C)%C);
}

1. 분배법칙은 알겠는데, 얼핏 보면 나머지 연산을 두 번 하게 되는 것 아닌가요? 
-> 나머지는 나누는 수 즉, 제수보다 클 수 없다. 하지만 두 번의 연산으로 생성된 나머지들을 더하거나 곱하게 되면 제수보다 커질수가 있기 때문에 한 번더 나머지 연산을 해줘야 합니다!

2. 문제에서는 어떻게 활용되나요? 
-> 1차원 선형 배열의 시작과 끝을 논리적으로 이어야 하는 원형배열을 생각하는 경우 배열의 인덱스를 다룰때 나머지 연산을 많이 사용합니다.
-> 특히 백준문제에서는 결과를 10007로 나눈 나머지를 제출하라 등의 형식의 문제가 많은데요! 정답의 크기가 int나 long으로도 처리가 안 될 정도로 클 경우엔 나머지 연산의 분배법칙을 활용하도록 합니다!

---

2. 집합 (Set)

프로그래밍에서 집합은 중복되는 원소가 없고, 순서가 존재하지 않는 배열
집합을 구현할 때는 파이썬은 set을 자바는 HashSet 혹은 TreeSet 자료 구조를 사용하면 된다. 
자바의 경우 HashSet은 넣은 순서가 보장되지 않고, TreeSet은 넣은 순서가 보장된다. 
내부 구현체가 HashMap과 TreeMap(Red-Black-Tree)로 다르기 때문에 객체에 삽입 삭제시 연산과정이 다르다. 
일장일단이 있기 때문에 상황에 맞게 필요한 자료구조를 사용하도록 한다. 

/**
     * 집합의 연산
     */
    public static void setOperation(){
        HashSet<Integer> setA = new HashSet<Integer>(Arrays.asList(new Integer[]{1, 2, 3, 4, 5}));
        HashSet<Integer> setB = new HashSet<Integer>(Arrays.asList(new Integer[]{4, 5, 6, 7, 8}));

        setA.addAll(setB);
        System.out.println("Union : " + setA);
        setA.retainAll(setB);
        System.out.println("intersection : " + setA);
        setA.removeAll(setB);
        System.out.println("difference : " + setA);
        setB.removeAll(setA);
        System.out.println("difference : " + setB);
    }

합집합, 교집합, 차집합을 구하는 각 메서드의 반환 값은 boolean 값이다. 
직접 결과를 찍어보면 알겠지만, 연산의 결과가 setA에 바로 반영되기 때문에 메서드 사용시 유의하자.

---

3. 약수 (Divisor)

어떤 수 N을 나누어 떨어지게 하는 수를 약수라고 한다. 
약수를 구하는 방식은 심플하다. N보다 작은 모든 자연수를 탐색하면서 나머지 연산을 하여 나머지가 0인 수를 찾는다. 

/**
 * 약수 구하기
 * @param n
 * @return 약수 집합
 */
public static HashSet<Integer> getDivisors(int n) {
    HashSet<Integer> set = new HashSet<>();
    for (int i=1; i<=n; i++) {
        if (n % i == 0) set.add(i);
    }

    return set;
}

위의 방법으로 약수를 구하게 되면 N이하의 수를 모두 탐색해야 한다. 즉, N의 크기가 커질 수록 연산 횟수가 너무 많아진다는 단점이 있기 때문에 아래와 같이 최적화가 가능하다.

/**
 * 약수 구하기 최적화
 * @param n
 * @return 약수 집합
 */
public static HashSet<Integer> getDivisorsMoreOpt(int n) {
    HashSet<Integer> set = new TreeSet<>();
    for (int i=1; i<=(int)Math.sqrt(n); i++) {
        if (n % i == 0) {
            set.add(i);
            set.add(n/i);
        }
    }

    return set;
}

약수의 집합을 직접 구해보면, 대칭 되는 쌍이 존재하며, 해당 쌍을 곱하는 경우 N이 나오는 것을 볼 수 있다. 
예를 들어 12의 약수는 [1,2,3,4,6,12], 36의 약수는 [1,2,3,4,6,9,12,18,36]이다.
이 경우 약수 집합의 대칭 중심(=중간 값)이 √N이 된다.
따라서 √N보다 작은 자연수(a)가 약수라면 그에 대칭 되는 수(b) 또한 약수임이 자명하기 때문에 절반의 연산으로 약수를 구할 수 있다.

---

4. 소수 (Prime Number)

1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다. (약수의 개수가 2개.)

3에서 약수의 개수를 구하는 방법을 알았다면, 소수를 판정하는 방법은 훨씬 쉽다.
어떤수 N이 1보다 큰 자연수이면서, 약수의 개수가 2개이면 소수, 2개 이상이면 소수가 아니다. 

/**
 * 약수 구하기 최적화
 * @param n
 * @return 약수 집합
 */
public static TreeSet<Integer> getDivisorsMoreOpt(int n) {
    TreeSet<Integer> set = new TreeSet<>();
    for (int i=1; i<=(int)Math.sqrt(n); i++) {
        if (n % i == 0) {
            set.add(i);
            set.add(n/i);
        }
    }

    return set;
}

/**
 * 소수 판정
 * @param n
 * @return boolean
 */
public static boolean isPrime(int n) {
    return getDivisorsMoreOpt(n).size() == 2;
}

위의 소스는 어떤 수가 소수인지 아닌지 여부를 파악하는 코드이다. 
그렇다면 약수의 집합을 구하는 것처럼 어떤 수 N보다 작은 소수를 모두 구하는 방법은 무엇이 있을까?
간단하게 생각해보면 2~N의 자연수를 모두 탐색하면서 해당 수의 약수 개수가 2인 것만을 찾으면 될 것이다. 
하지만 이 방법 또한 N의 개수가 커질 수록 비효율적이기 때문에 "에라토스테네스의 체"라는 알고리즘을 사용한다.

/**
 * 에라토스테네스의 체
 */
public static void getPrimesByEratosthenes(int N) {
    boolean [] isPrime = new boolean[N+1];
    Arrays.fill(isPrime, true);
    isPrime[0] = false;
    isPrime[1] = false;

    System.out.println();
    for (int i=2; i<=(int)Math.sqrt(N); i++) {
        if(!isPrime[i]) continue;
        for(int j=2*i; j<=N; j+=i) {
            isPrime[j] = false;
        }
    }

    for (int i=0; i<isPrime.length; i++) {
        if(isPrime[i]) System.out.print(i + " ");
    }
}

 조금 복잡해보이지만 약수구하기 최적화 알고리즘을 조금만 응용하면 된다. 
알고리즘의 기본 원리는 2~√N의 범위에서 나누어 떨어지는 수 i가 있다면, i를 제외한 i의 배수를 모두 삭제하면 된다. 여기서 범위가 √N인 이유는 위에서 잠깐 설명한 대로 대칭쌍의 중심값이기 때문이다. 
중심값보다 작은 값에서 나누어 떨어진다면, 대칭되는 큰 값은 이미 삭제된다. 
예) 12의 약수 중 대칭쌍(2*6), (3*4)  √12 = 약 3.xxx 정도의 값이다. 

(2*6)의 경우 6은 2의 배수로 이미 삭제된다. 
(3*4)의 경우 4는 3보다 작은 2의 배수로 이미 삭제된다.

---

5. 최대공약수 최소공배수 

최대공약수 (GCD : Greatest Common Divisor)

어떤 두 수 a, b의 최대 공약수는 a, b의 공약수(두 수의 공통 약수) 중에서 가장 큰 수
a와 b의 최대공약수를 구하는 방법은 두 수의 공약수 집합을 구한 후 가장 큰 값을 구하면 된다. 

/**
 * 약수 구하기 최적화
 * @param n
 * @return 약수 집합
 */
public static TreeSet<Integer> getDivisorsMoreOpt(int n) {
    TreeSet<Integer> set = new TreeSet<>();
    for (int i=1; i<=(int)Math.sqrt(n); i++) {
        if (n % i == 0) {
            set.add(i);
            set.add(n/i);
        }
    }

    return set;
}
/**
 * 최대공약수 구하기
 * @param a
 * @param b
 * @return 최대공약수
 */
public static int getGCD (int a, int b) {
    TreeSet<Integer> set_a = getDivisorsMoreOpt(a);
    TreeSet<Integer> set_b = getDivisorsMoreOpt(b);
    //두 약수 집합의 교집합 == 공약수 집합
    set_a.retainAll(set_b);

    return set_a.stream().max((Comparator.comparingInt(o -> o))).get().intValue();
}

최소 공배수 (LCM : Least Common Multiple)

어떤 두 수 a, b의 최소 공배수는 a, b의 공배수 중에서 가장 작은 수
두 수의 최대 공약수를 구하면 다음 식에 의해서 최소 공배수를 구할 수 있다. 
a x b = GCD x LCM

/**
 * 최소 공배수 구하기
 * @param a
 * @param b
 * @return 최소 공배수
 */
public static int getLCM(int a, int b) {
    return a*b/getGCD(a,b);
}

/**
 * 최대공약수 구하기
 * @param a
 * @param b
 * @return 최대공약수
 */
public static int getGCD (int a, int b) {
    TreeSet<Integer> set_a = getDivisorsMoreOpt(a);
    TreeSet<Integer> set_b = getDivisorsMoreOpt(b);
    set_a.retainAll(set_b);

    return set_a.stream().max((Comparator.comparingInt(o -> o))).get().intValue();
}

 

위의 개념을 응용한 알고리즘 말고 좀 더 최적화된 유클리드 알고리즘을 이용하면 로그 시간의 복잡도로 최대 공약수를 구할 수 있다. 유클리드 호제법을 코드로 구현해보자. 코드 자체는 상당히 단순하다. 

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

유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다. 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는다.
두 개의 자연수 a,b 에 대해서 (단, a>b)  a % b  == r 이라고 할 때, GCD (a, b) === GCD(b, r)의 성질을 이용한다.

---

6. 소인수분해

소인수분해는 어떤 수 n을 소수의 곱으로만 나타내는 것을 의미한다. 
어떤 수 n을 소인수 분해하는 방법은 2부터 N까지 살펴 보면서 소수로 나누어 보면 된다. 

/**
 * n을 소인수 분해하기
 * @param n
 * @return 소수 리스트
 */
public static ArrayList<Integer> getPrimes(int n) {
    ArrayList<Integer> list = new ArrayList<>();
    for(int i =2; i<=n; i++) {
        while(n%i==0) {
            list.add(i);
            n /= i;
        }
    }
    return list;
}

---