↓Skip to main content

[Algorithm] 유용한 수학

Table of Contents



1부터 n까지의 합 #

  • $n$이 짝수일 경우
    • $a+b$가 $n/2$번 반복된다.
    • $(n+1) * (n/2)$
쌍 $a$ $b$ $a+b$
$1$ $1$ $n$ $n+1$
$2$ $2$ $n-1$ $n+1$
… … … …
$n/2$ $n/2$ $n/2+1$ $n+1$

  • $n$이 홀수일 경우
    • $a+b$가 $(n+1)/2$번 반복된다.
    • $n * (n+1)/2$
쌍 $a$ $b$ $a+b$
$1$ $0$ $n$ $n$
$2$ $1$ $n-1$ $n$
… … … …
$(n+1)/2$ $n/2-1$ $n/2$ $n$

  • 두 경우 모두 정리하면… $1$부터 $n$까지의 합은?
    • $$ \frac{n(n+1)}{2} $$



2의 승수의 합 #

  • $ 2^0 + 2^1 + 2^2 + … + 2^n $의 결과는?
    • 2진수로 생각해보자!
승수 2진수
$2^0$ 00001
$2^1$ 00010
$2^2$ 00100
$2^3$ 01000
$2^4$ 10000
$2^0 + 2^1 + 2^2 + 2^3 + 2^4 = 2^5 - 1$ 11111
  • 즉, 2의 승수의 합은 다음 공식과 같다.
    • $$2^{n+1} - 1$$



로그의 밑 #

  • $\log_2 k$를 $\log_{10} k$로 어떻게 바꿀 수 있을까?
    • $y = \log_x k$이고, $a = \log_b k$일 때,
    • $a = \log_b k$ 이것을 풀면, $b^a = k$ 이다. 이것을 두번째 식에 대입하면,
    • $$\log_x k = \log_x b^a$$
    • $$\log_x k = a \log_x b$$
    • $$a = \frac{\log_x k}{\log_x b} = \log_b k$$
    • 따라서 다음과 같이 구할 수 있겠다.
    • $$ \log_{10} k = \frac{\log_2 k}{\log_2 10} $$



순열과 조합 #

  • $n$개 중에 $r$개를 선택하는 경우의 수는?
순열 조합
설명 배치하기.
순서가 다르면 다른 경우이다.		 뽑기.
순서가 달라도 같은 경우이다.
중복불가 공식 $$_n P_r = \frac{n!}{(n-k)!} $$ $$ _n C_r = \frac{n!}{(n-k)!r!} $$
중복가능 공식 $$_n \pi _r = n^r $$ $$_n H _r = _{n+r-1} C _r $$ 

// 필요 변수 목록
int n = 5;
int r = 3;
int arr[] = { 1, 2, 3, 4, 5 };
bool visited[] = { false, false, false, false, false };
int print[] = { -1, -1, -1 };

순열 #

  • 중복 불가 순열
void Permutation(int count = 0)
{
    if (count == r)
    {
        for (int i = 0; i < r; i++)
            cout << print[i] << ' '; // 순서가 중요하므로 print배열을 사용해서 출력한다.
        cout << '\n';
        return;
    }
    
    // 늘 처음부터 살펴본다. 
    // 순서가 달라도 다른 경우이므로, 이전 경우에 뽑았던 숫자를 또 선택할 수 있기 때문이다. 
    for (int i = 0; i < n; i++)
    {
        if (selected[i] == true) continue; // 이미 선택한 건 쳐다보지도 않는다.
        
        selected[i] = true;
        print[count] = arr[i];
        Permutation(count + 1);
        selected[i] = false; // 끝까지 다 선택한 후 돌아왔다면, 다시 선택할 수 있는 상태로 바꾼다. 
    }
}

  • 중복 가능 순열
void PermutationWithRepetition(int count = 0)
{
    if (count == r)
    {
        for (int i = 0; i < r; i++)
            cout << print[i] << ' ';
        cout << '\n';
        return;
    }
    
    for (int i = 0; i < n; i++)
    {
        // selected가 사라졌다.
        
        print[count] = arr[i];
        Permutation(count + 1);
    }
}



조합 #

  • 중복 불가 조합
void Combination(int idx = 0, int count = 0)
{
    if (count == r)
    {
        for (int i = 0; i < n; i++)
            if (selected[i] == true) // 순서가 상관 없으므로 print배열이 필요없다.
                cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    
    // 현재 선택한 수의 위치(idx) 이후로 살펴보면서 추가로 선택한다.
    // 그래서 늘 현재 선택한 수 뒤로만 검사한다. 
    // 순서가 상관 없으므로, 이전 경우에 선택했던 숫자를 또 선택하면 안 되기 때문이다. 
    for (int i = idx; i < n; i++)
    {
        if (selected[i] == true) continue;
        
        selected[i] = true;
        Combination(i + 1, count + 1); // 다음 숫자(i + 1)부터 본다. 
        selected[i] = false;
    }
}

  • 중복 가능 조합
void CombinationWithRepetition(int idx = 0, int count = 0)
{
    if (count == r)
    {
        for (int i = 0; i < n; i++)
            if (selected[i] == true)
                cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    
    for (int i = idx; i < n; i++)
    {
        // selected가 사라졌다.
        
        print[count] = arr[i];
        Combination(i, count + 1); // 중복 가능이므로 지금 숫자(i)부터 본다. 
    }
}



Rabin-Karp 부분 문자열 탐색 알고리즘 #

  • 해싱(Hashing) 을 사용해서 문자열에서 특정 패턴과 일치하는지를 찾아주는 알고리즘이다.
  • 예를 들어, 각 문자의 아스키 코드와 자릿수를 곱해주는 해시 함수를 사용한다면…
    • ear → $101 \times 2^2 + 97 \times 2^1 + 114 \times 2^0$
void Rabin_Karp(string str, string pattern)
{
    int strLen = str.length();
    int patLen = pattern.length();
    int i, j;
    int strHash = 0, patHash = 0, base = 1;
 
    // 첫 해시 값 
    for (i = patLen - 1; i >= 0; i--)
    {
        strHash = strHash + str[i] * base;
        patHash = patHash + pattern[i] * base;
        
        if (i > 0) base *= 2;
    }
 
    for (i = 0; i < strLen - patLen + 1; i++)
    {
        if (patHash == strHash)
        {
            for (j = 0; j < patLen; j++)
                if(str[i + j] != pattern[j]) 
                    break;
                
            if (j == patLen)
                cout << "Pattern is found at index: " << i << endl;
        }

        // 다음 해시 값 
        // 첫번째 문자 제거, 한 칸씩 앞으로 이동(2곱하기), 마지막 새 문자 추가 
        strHash = (strHash - str[i] * base) * 2 + str[i + patLen];
    }
}



References #



↑