Seong Ui-Je


기초 수학

자료구조와 알고리즘을 공부하기 전 기초 수학에 대한 정리를 하고자 한다.

이러한 수학은 실제로 많은 방법으로 사용되는데 그 중 몇 가지를 알아보자.


집합(Set)

  • 어떤 조건에 의하여 원소(집합을 이루고 있는 각각의 대상)들의 모임

  • 집합의 표현방법

    1. 원소나열법 : 집합에 속하는 원소를 { } 안에 모두 나열하여 나타내는 방법
    2. 조건제시법 : 집합에 속하는 원소를 { x|x에 대한 조건 } 의 꼴로 나타내는 방법
    3. 벤 다이어 그램 : 그림을 이용하여 집합을 나타내는 방법


교집합(A∩B)

두 집합이 공통으로 포함하는 원소로 이루어진 집합

retainsAll() 메소드를 사용

1
2
3
4

HashSet a = new HashSet(Arrays.asList(1, 2, 3, 4, 5));
HashSet b = new HashSet(Arrays.asList(2, 4, 6, 8, 10));
a.retainAll(b);
System.out.println("교집합: " + a);


합집합(A∪B)

어느 하나에라도 속하는 원소들을 모두 모은 집합

addAll() 메소드를 사용

1
2
3
4

HashSet a = new HashSet(Arrays.asList(1, 2, 3, 4, 5));
HashSet b = new HashSet(Arrays.asList(2, 4, 6, 8, 10));
a.addAll(b);
System.out.println("합집합: "+a);


차집합(A - B)

  • A(or B)에만 속하는 원소들의 집합

  • removeAll() 메소드를 사용

1
2
3
4

HashSet a = new HashSet(Arrays.asList(1, 2, 3, 4, 5));
HashSet b = new HashSet(Arrays.asList(2, 4, 6, 8, 10));
a.removeAll(b);
System.out.println("차집합:" +a);


여집합(Ac)

  • 전체 집합(U) 중 A의 원소가 아닌 것들의 집합

ArrayList를 이용한 배열 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

class MySet {
    // ArrayList
    ArrayList<Integer> list;

    // 생성자
    MySet() {
        this.list = new ArrayList<Integer>();
    }

    // 원소 추가(중복 X)
    public void add(int x) {
        for (int item : this.list) {
            if (item == x) {
                return;
            }
        }
        this.list.add(x);
    }

    // 교집합
    public MySet retainAll(MySet b) {
        MySet result = new MySet();

        for (int itemA : this.list) {
            for (int itemB : b.list) {
                if (itemA == itemB) {
                    result.add(itemA);
                }
            }
        }
        return result;
    }

    // 합집합
    public MySet addAll(MySet b) {
        MySet result = new MySet();

        for (int itemA : this.list) {
            result.add(itemA);
        }

        for (int itemB : b.list) {
            result.add(itemB);
        }
        return result;
    }

    // 차집합
    public MySet removeAll(MySet b) {
        MySet result = new MySet();

        for (int itemA : this.list) {
            boolean containFlag = false;

            for (int itemB : b.list) {
                if (itemA == itemB) {
                    containFlag = true;
                    break;
                }
            }
            if (!containFlag) {
                result.add(itemA);
            }
        }
        return result;
    }
}


경우의 수

  • 어떤 사건(일)이 일어날 수 있는 경우의 가짓수를 수로 표현한 것


합의 법칙

  • 사건 A 또는 사건 B가 일어날 경우의 수

  • n(A∪B) = nA + nB - n(A∩B)

  • 예제 : 두 개의 주사를 던졌을 때 합이 3 또는 4의 배수일 경우의 수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

int[] dice1 = {1, 2, 3, 4, 5, 6};
int[] dice2 = {1, 2, 3, 4, 5, 6};

int nA = 0;
int nB = 0;
int nAandB = 0;

// 기본 풀이 : 3,4,12 배수의 경우의 수를 모두 구한 후 (3의경우의수 + 4의경우의수 - 12경우의수)로 결과 확인
for (int item1 : dice1) {
    for (int item2 : dice2) {
        if ((item1 + item2) % 3 == 0) {
            nA += 1;
        }

        if ((item1 + item2) % 4 == 0) {
            nB += 1;
        }

        if ((item1 + item2) % 12 == 0) {
            nAandB += 1;
        }
    }
}
System.out.println("결과 : " + (nA + nB - nAandB));	//결과 : 20

// HashSet 이용 : Set은 중복값을 포함할 수 없으므로 12경우의수를 계산할 필요가 없다. 
HashSet<ArrayList> allCase = new HashSet<>();
for (int item1 : dice1) {
    for (int item2 : dice2) {
        if ((item1 + item2) % 3 == 0 || (item1 + item2) % 4 == 0) {
            ArrayList list = new ArrayList(Arrays.asList(item1, item2));
            allCase.add(list);
        }
    }
}
System.out.println("Set 결과 : " + allCase.size());	//결과 : 20


곱의 법칙

  • 사건 A와 사건 B가 동시에 일어날 경우의 수

  • n(AxB) = n(A) + n(B)

  • 예제 : 두 개의 주사위 a, b를 던졌을 때 a는 3의 배수, b는 4의 배수인 경우의 수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int[] dice1 = {1, 2, 3, 4, 5, 6};
int[] dice2 = {1, 2, 3, 4, 5, 6};

int nA = 0;
int nB = 0;

for(int item1 : dice1){
    if(item1 % 3 == 0 ){
        nA++;
    }
}

for(int item2 : dice1){
    if(item2 % 4 == 0 ){
        nB++;
    }
}

System.out.println("결과 : " + nA*nB);


약수

  • 약수는 어떤 수를 나누었을 때 나누어 떨어지게 하는 자연수

    • 4의 약수는 (1,2,4) 이고 12의 약수는 (1,2,3,4,6,12) 이다.
1
2
3
4
5
6
7
8
9
10
11
12

public ArrayList getDivisor(int num) {
    ArrayList result = new ArrayList();

    for (int i = 1; i <= (int) num / 2; i++) {
        if (num % i == 0) {
            result.add(i);
        }
    }
    result.add(num);
        
    return result;
}


최대 공약수(GCD)

  • 공약수: 두 수의 약수 중 공통된 약수를 공약수라고 부릅니다.

  • 최대 공약수(Greatest Common Divisor: GCD): 가장 큰 공약수

    • 4와 12의 약수 중 공약수는 ( 1,2,4 ) 이고 최대 공약수는 4이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public int getGCD(int numA, int numB) {
    int gcd = -1;
    
    ArrayList divisorA = this.getDivisor(numA);
    ArrayList divisorB = this.getDivisor(numB);

    for(int itemA : (ArrayList<Integer>) divisorA){
        for (int itemB : (ArrayList<Integer>) divisorB){
            if(itemA == itemB){
                if(itemA > gcd){
                    gcd = itemA;
                }
            }
        }
    }
    return gcd;
}

//재귀 함수로 구현
static int gcd(int a, int b) {
    if (a % b == 0) {
        return b;
    }

    return gcd(b, a % b);
}


최소 공배수(LCM)

  • 공배수: 두 수의 배수들 중 공통된 배수
  • 최소 공배수(Least Common Multiple: LCM): 가장 작은 공배수
    • 2와 3의 배수는 ( 6, 12, 18 …) 인데 이중 최소 값인 6이 최소 공배수다.
  • 최소 공배수는 A * B / 최대 공약수(GCD) 
1
2
3
4
5
6
7
8
9
10

public int getLCM(int numA, int numB) {
    int lcm = -1;

    int gcd = this.getGCD(numA, numB);
    if (gcd != -1) {
        lcm = numA * numB / gcd;
    }

    return lcm;
}


순열(Permutation)

  • 서로 다른 n개 중에 r 개를 순서와 선택하는 경우의 수(순서O, 중복X)

    • 예시1) 5명을 3줄로 세우는 방법

    • 예시2) 서로 다른 4명 중 반장, 부반장을 뽑는 방법

$ nPr = \frac {n!}{(n - r)!} = n(n - 1)(n - 2) .... (n - r + 1) $
1
2
3
4
5
6
7
8
9
10

// 5!
int n = 5;
int r = 3;
int result = 1;
        
for (int i = n; i >= n - r + 1; i--) {
    result*=i;
}

System.out.println(result);	//결과 : 60


중복 순열

  • 서로 다른 n개 중에 r 개를 순서와 선택하는 경우의 수(순서O, 중복O)

    • 예시1) 서로 다른 4개의 수 중 2개를 뽑는 방법(중복 허용)

    • 예시2) 후보 2명, 유권자 3명일 때 기명 투표 방법

$ n\Pi r = n^r $
1
2
3
4
5
6
7
8
9
10
11

int n = 4;
int r = 2;
int result = 1;

for (int i = 0; i < r; i++) {
    result*=n;
}

System.out.println(result);	//결과 : 16
//Math이용
System.out.println(Math.pow(n, r));


원 순열

  • 원 모양의 테이블에 n개의 원소를 나열하는 경우의 수

    • 예시) 원 모양의 테이블에 3명을 앉히는 경우
$ \frac{n!}{n} = (n-1)! $
1
2
3
4
5
6
7

int n = 3;
int result = 1;

for (int i = 1; i < n; i++) {
    result *= i;
}
System.out.println(result);


팩토리얼(Factorial)

  • n! 로 나타내며 1부터 n까지의 자연수를 모두 곱하는 것
$ n! = n(n-1)(n-2)....1 $
1
2
3
4
5
6
7
8
9
10
11

//5!
int n = 5;
int result = 1;

for (int i = 1; i <= n; i++) {
    result*=i;
}
System.out.println(result);	//결과 : 120

//스트림
System.out.println(IntStream.range(2,6).reduce(1,(x,y) -> x*y));


조합(Combination)

  • 서로 다른 n개 중에서 r개를 선택하는 경우의 수입니다.(순서X, 중복X)

    • 예시) 서로 다른 4명 중 주번 2명 뽑는 방법
$ nCr = \frac{n!}{(n-r)!r!} = \frac{nPr}{r!} $ (단(0<r≤n) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

 static int getCombination(int n, int r) {
     int pResult = 1;
     int rResult = 1;

     //nPr
     for (int i = n; i >= n - r + 1; i--) {
         pResult *= i;
     }

     //r!
     for (int i = 1; i <= r; i++) {
         rResult *= i;
     }

     return pResult / rResult;
 }


public static void main(String[] args) {
    //후보 4명, 유권자 2명일 때 무기명 투표 경우의 수
    int n = 4;
    int r = 2;

    System.out.println(getCombination(n,r));		//조합 ( 결과 : 6 )
    System.out.println(getCombination(n+r-1,r));	//중복 조합 ( 결과 : 10 )
}


중복 조합

  • 서로 다른n개 중에서 r개를 선택하는 경우의 수입니다.(순서X,중복O)

    • 예시) 후보2명,유권자 3명일 때 무기명 투표방법
$ nHr = n + r - 1Cr $


점화식과 재귀함수


점화식(Recurrence)

  • 어떤 수열의 일반항을 그 이전의 항들을 이용하여 정의한 식

    • 예시) 피보나치 수열 : 앞의 두 수의 합이 바로 뒤가 되는 수의 배열
1,1,2,3,5,8,13, ...
F1 = F2 = 1, Fn+2 = Fn+1 + Fn


재귀 함수(Recursive Function)

어떤 함수가 자신을 다시 호출하여 작업을 수행하는 방식

  • 문법
1
2
3
4
5

반환타입 함수이름 (매개 변수) {
    종료조건
        ...
    함수이름(...)
}
  • 재귀 함수 변환 예제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

public class main{
    public static void main(String[] args) {
        //문제1) 1, 3, 9, 27, ... 의 n번째 수
        int n = 4;
        int result = 1;
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                result = 1;
            } else {
                result *= 3;
            }
        }
        System.out.println(result);

        //문제2) 1, 2, 3, 4, 5, 6, ... 의 n번째 까지의 합
        n = 5;
        result = 0;
        for (int i = 1; i < n + 1; i++) {
            result += i;
        }
        System.out.println(result);

        //문제3) 1, 1, 2, 3, 5, 8, 13, ...의 n번 째 수
        n = 6;
        result = 0;
        int a = 1;
        int b = 1;

        if (n < 3) {
            result = 1;
        } else {
            for (int i = 2; i < n; i++) {
                result = a + b;
                a = b;
                b = result;
            }
        }
        System.out.println(result);
    }
    
    //1번문제 > 재귀함수로 변환
    static int recursion1(int n) {
        if (n == 1) {
            return 1;
        }
        return 3 * recursion1(n - 1);
    }
    
    //2번문제 > 재귀함수로 변환
    static int recursion2(int n) {
        if (n == 1) {
            return 1;
        }
        return n + recursion2(n - 1);
    }
    
    //3번문제 > 재귀함수로 변한
    static int recursion3(int n) {
        if (n < 3) {
            return 1;
        }
        return recursion3(n - 2) + recursion3(n - 1);
    }
    
}


지수와 로그


제곱,제곱근,지수

  • 제곱 : 같은 수를 두 번 곱하는 것

  • 거듭제곱 : 같은 수를 거듭하여 곱함
  • 제곱근(Root, $ \sqrt{} $) : a를 제곱하여 b가 될 때 a를 b의 제곱근이라고 한다.
$ 2^3 = 2 x 2 x 2 $
$ \sqrt{4} = \sqrt{2^2} $
$ a^x $ -> a:밑, x:지수 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

//제곱
Math.pow(2,3);	//결과 : 8

//제곱근
Math.sqrt(4);	//결과 : 2
Math.pow(4,1.0/2);

//참고) 절대 값(양수)
Math.abs(-5);	//결과 : 5

//제곱을 Math 없이 구현하기
static double pow(int a, double b) {
    double result = 1;
    boolean isMinus = false;

    if (b == 0) {
        return 1;
    } else if (b < 0) {
        b *= -1;
        isMinus = true;
    }

    for (int i = 0; i < b; i++) {
        result *= a;
    }

    return isMinus ? 1 / result : result;
}
//제곱근을 Math없이 구현하기
static double sqrt(int a) {
    double result = 1;

    for (int i = 0; i < 10; i++) {
        result = (result + (a / result)) / 2;
    }

    return result;
}

로그

  • a가 b가 되기 위해 제곱 해야 하는 수
$\log_2 4 = 2$
$\log_{10} 1000 = 3$ 
1
2

double log2_4 = Math.log(4) / Math.log(2);
double log10_1000 = Math.log10(1000);


알고리즘 복잡도(Algorithm Complexity)

  • 알고리즘 복잡도란 알고리즘 성능을 나타내는 척도

  • 시간 복잡도와 공간 복잡도로 나뉘어지며 두 복잡도의 관계는 일반적으로 Trade-off 관계

시간 복잡도(Time Complexity)

  • 어떤 문제를 해결하기 위한 알고리즘의 필요 횟수

  • 빅오(Big-O) 표기법을 통해 나타냅니다.

biGO


공간 복잡도(Space Complexity)

  • 어떤 문제를 해결하기 위한 알고리즘의 필요 메모리 사용량
  • 빅오(Big-O) 표기법을 통해 나타낸다.
  • 일반적으로 메모리사용량은 MB단위이며 기술의 발전으로 시간 복잡도에 비해 덜 중요해졌다.
1
2

int[] a = new int[1000]; //4KB
int[][] a = new int[1000][1000]; //4MB

댓글남기기