[정리] 알고리즘에 유용한 계산 정리

수학

• 10 진수 -> N진법 변환

string ConvertBinaryNumber(int n/*10진수*/, int k/*진법*/)
{
    string str;
    for (int i = n; i > 0; i /= k)
    {
        str += to_string(i % k);
    }
    reverse(str.begin(), str.end());
    return str;
}

• 비트 연산으로 홀수 & 짝수 계산

void OddEven()
{
    int odd = 1001;
    int even = 1000;
    
    int a = odd & 1;
    int b = even & 1;
}

• 이진수 변환

string ToBinary(int n, int num)
{
    // n 자리수만큼만 string 추가
    string str;
    for (int i = n - 1; i >= 0; --i) 
    {
        int result = num >> i & 1;
        str += to_string(result);
    }
    return str;
}

2D Array 두 점 사이의 거리 계산

2차원 배열에서 두 점 사이의 거리를 계산하기 위한 방식은 3가지가 있다.

• 유클리드 거리

// 피타고라스의 정리 활용
int distance = sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));

• 맨헤튼 거리

// x,y 좌표의 절대값 차이를 더하면 최소 거리가 된다.
int distance = abs(x1 - x2) + abs(y1 - y2);

• 헤밍 거리 : 두 개의 길이가 같은 문자열 거리 측정

// 서로 다른 문자열의 개수 측정 다음의 결과는 3이다.
string str1 = "abcdef";
string str2 = "abdgez";
int distance = 0;
for (int i = 0; i < str1.length(); i++)
{
    if (str1[i] != str2[i])
        distance++;
}

최대 공약수 / 최소 공배수

• 유클리드 호제법

• GCD (최대 공약수)

// GCD(m,n) = GCD(m, m%n)
int GCD(int m, int n)
{
    while (n > 0)
    {
        int temp = m;
        m = n;
        n = temp % n;
    }
    return m;
}

• LCM (최소 공배수)

int LCM(int m, int n)
{
    return (m * n) / GCD(m, n);
}

소수 판별

• 단일 숫자 소수 판별 : 특정 숫자의 제곱근까지만 검증 Time Complexity = O(N^(1/2))

bool IsPrimeNumber(int value)
{
	int nCount = (int)sqrt(value);
    for (int i = 2; i <= nCount; i++)
    {
    	if (value % i == 0)
        	return false;
    }
    return true;
}

• 에라토스테네스의 체 : 대량의 소수를 빠른 속도로 한꺼번에 판별할 때 사용

vector<int> PrimeNumberSieve(int count)
{
    vector<int> numbers(count+1, 0);
    for (int i = 2; i <= count; i++)
    {
        numbers[i] = i;
    }

    for (int i = 2; i <= count; i++)
    {
        if (numbers[i] == 0)
            continue;

        for (int j = i + i; j <= count; j += i)
        {
            numbers[j] = 0;
        }
    }
    vector<int> answer;
    for (int value : numbers)
    {
        if (value != 0)
            answer.push_back(value);
    }
    return answer;
}

 

트리

• 트리 1차원 array에서 Index 계산

• Parent : (자식 idx - 1) / 2
• Left Child : 2 * (부모 idx) + 1
• Right Child : 2 * (부모 idx) + 2

Value	1	8	5	4	3
Index	0	1	2	3	4

트리

• 트리의 지름

 

그 외

• 문자열 공백 기준으로 나누기 : stringstream 사용

vector<string> Split(string s)
{
    vector<string> res;
    istringstream ss(s);
    string str;
    while (ss >> str) 
    {
        res.push_back(str);
    }
    return res;
}

 

• 문자열 탐색

• 트라이 자료구조 : O(M)

1. 부분 문자열이 아닌 완전한 문자열 검색
2. 접두사 검색

• KMP 알고리즘 : O(N+M)
• 라빈-카프 알고리즘 O(N) (실제 사용은 라빈카프를 쓰면된다. 구현이 더쉽고 간단하다.)

bool RabinKarp(std::string const& strWhole, std::string const& strFind)
{
	int swLen = strWhole.length();
	int sfLen = strFind.length();
	int swHash = 0; 
	int sfHash = 0;
	int power = sfLen - 1; // 제곱수
	for (int i = 0; i <= swLen - sfLen; i++)
	{
		if (i == 0) // 0번째 값 계산
		{
			for (int j = 0; j < sfLen; j++) // 순회하면서 해시 값 계산후 더해준다.
			{
				sfHash += (strFind[j] * pow(2, power));
				swHash += (strWhole[j] * pow(2, power));
				power--; // 제곱수 빼기
			}
		}
		else // 이전 해시 값을 이용하여 계산한다.
		{
			// 전체 문자열이 ABCD 인데 BCD(Length : 3)를 찾는 경우
			// ABC부터 해시값을 계산한다. 문자열이 같지 않으므로 B로 이동하는데 
            // 이때 전체 해시값을 다시 계산할 필요없이 이전 해시값을 사용해 계산에 이용한다.
			// 지정한 수 * (이전에 계산했던 해시값 - 이전 첫째 문자 해시값) + 추가될 문자값
			// 이전 첫째 문자 해시값 = A(문자열)*2^(findStrLength-1), 
            // 추가될 문자값이 그냥 D인 이유는 어차피 2의 0승이므로 1을 곱해주기때문.
			swHash = 2 * (swHash - (strWhole[i - 1] * pow(2, sfLen - 1))) 
            + strWhole[sfLen - 1 + i];
		}

		if (swHash == sfHash)
		{
			bool isSame = true;
			// 혹시나 문자열 값이 다를 때 해시 값이 충돌날 수도 있다. 
            // (이 때는 진짜 같은지 모두 비교해준다.)
			for (int j = 0; j < sfLen; j++)
			{
				if (strWhole[i + j] != strFind[j])
				{
					isSame = false;
					break;
				}
			}
			if (isSame)
				return true;
		}
	}
	return false;
}

1. 원본 문자열 내 부분 문자열 검색
2. 텍스트 검색어 1 : 1 매칭

• 아호 코라식 알고리즘 : O(N + M1 + M2 + M3 ...)

1. 부분 문자열 검색 가능
2. 텍스트 검색어 1 : N 매칭