알고리즘 교안 학습 -2 [순열, 조합, 정수론]

[순열 - 재귀 방식]

재귀 방식 커스텀 순열은 지겹도록 반복해서 코드를 외워버렸다.

이해하는 손 디버깅에도 반복했던 시간을 다하면 못해도 2시간이상은 할당했던것 같다.

 

void permutation(int n, int r, int depth)
{
	if (depth == r)
    {
		permutationPrint();
		return;
    }

	for (int i = depth; i < n; ++i)
    {
        swap(a[i], a[depth]);
        permutation(n,r,depth+1);
        swap(a[i], a[depth]);
    }
 }
    
void permutationPrint()
{
	for (int i = 0; i < (sizeof(a) / sizeof(int)); ++i)
		cout << a[i] << " ";

	cout << '\n';
}
    
void main()
{
	permutation(3,3,0);
}

[next_permutation ,prev_permutation] - include<algorithm>

사실 알고리즘 헤더에 있는 순열은 너무나도 사용하기 쉽다.

단, do-while 문만 기억하면 되기 때문에!

사용하기 어려운건 없다. 단 항상 기억할 것은 선정렬 후에 사용해야 한다.

// 먼저 next_permutation을 진행하기전에 정렬을 수행한다. 
// 이는 prev_permutation도 동일하다. 단, prev 는 반대로 내림차순으로 정렬한다.

// next_permutation

public: int a[3] = { 1,2,3 };
void algorithm_permutation()
{
	do
	{
		permutationPrint();// 이건 재귀순열 코드에 있다.
	} while (next_permutation(a, a + (sizeof(a) / sizeof(int))));
}
    
void main()
{
	algorithm_permutation();
}

// prev_permutation

public: int a[3] = { 1,2,3 };
void algorithm_permutation()
{
	sort(a, a + 3, std::greater<int>());
	do
	{
		permutationPrint();// 이건 재귀순열 코드에 있다.
	} while (prev_permutation(a, a + (sizeof(a) / sizeof(int))));
}

void main()
{
	algorithm_permutation();
}

[조합]

조합은 순서에 상관없이 뽑는것이다.

조합 구현은 2가지 방법이 있다.

 

// 두 케이스 모두 값은 아래로 가정한다.
// a[5] = {1,2,3,4,5} , n = 5, r = 3; 

// Case 1. 재귀방식
public void Combi(int start, vector<int> v)
{
    if(v.size() == r) return;
	// 사용자가 원하는 조건식, 출력이나, 저장 등등
        
    for(int i = start+1; i < n; ++i)
    {
    	v.push_back(i); // 인덱스를 넣는 방식인데, a[i] 로 값을 넣는 방식으로 진행해도 무방
        Combi(i,v);
        v.pop_back(i); // 인덱스를 넣고, 다 순회한후에 다시 원상태로 돌려야 함.
    }
}

int main()
{
    vector<int> b;
    Combi(-1,b);
    return 0;
}

// Case 2. 중첩 for문
public void Combi()
{
    for(int i= 0; i < n; ++i)
	    for(int j = i+1; j < n; ++j)
		    for(int k = j+1; k < n; ++k)
			    cout << i << j << k << '\n';
}

int main()
{
    Combi();
    return 0;
}

두 가지 모두 장단점이 있는데 코딩테스트 용으로는 전자가 인자로 넣기 용이할 것 같다.

구현은 귀찮을 수 있지만 외워서 구현해도, 이해한다음 구현해도 문제는 없어보인다.

 

[정수론 - 최대 공약수, 최소 공배수]

예전에는 구현하기 까다로웠다고 느꼈던 문제들이다.

교안에는 각자 공식들이 존재하는 것으로 보인다.

손디버깅을 진행하면서 확인해야 할 필요성이 있어보인다.

// 최대공약수 gcd
int Getgcd(int a, int b)
{
    if(a == 0) return b;
    return Getgcd(b % a, a);
}

// 최소공배수 => (두 수의 곱) / (두 수의 최대 공약수)

int Getlcm(int a,b)
{
    return (a*b) / Getgcd(a,b);
}

int main()
{
    int a = 12 , int b = 15;
    cout << " gcd :: " << Getgcd(a,b) << '\n';
    cout << " lcm :: " << Getlcm(a,b) << '\n';
    return 0;
}

[정수론 - 모듈러 연산]

어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산.

* a ≡ b mod n , b ≡ c mod n , a ≡ c mod n 을 의미 // 셋이 모두 같은 수로 나눠진다면 같은 값이다.
덧셈 :: [(a mod n)+(b mod n)] mod n = (a+b) mod n
뺄셈 :: [(a mod n)-(b mod n)] mod n = (a-b) mod n
곱셈 :: [(a mod n)*(b mod n)] mod n = (a*b) mod n

[정수론 - 에라토스 테네스의 체]

- 업데이트 예정

 

[정수론 - 등차수열의 합]

등차수열의 합은 아래와 같다. 이를 기준으로 코드를 작성해보면,

// a = 1, n = 5 로 가정한다.

int main()
{
    int ret = 0;
    
    for(int i = 0; i <= n; ++i
    	ret += i; // 비교군


    int summary = (5(5+1))/2; // summary = n(n+1)/2
    
    cout << ret << '\n';
    cout << summary << '\n';
    
    return 0;
}

그러나 한번에 구할 수 있는 다른 공식이 있는데, 아래 공식이다. 아래 공식을 사용해보면,

// 5,10,15,20,25 => 75

int main()
{
    int summary = 5(5+25)/2; // summary = n(a+l)/2 공식 사용
    
    cout << ret << '\n';
    cout << summary << '\n';
    
    return 0;
}

여기서 원리는 등차일때 적용하는 것인데, 어디선가 수를 1,2,3,4,5,6,7,8,9 가 있을 때, 1 9 , 2 8, 3 7, 4 6, 5 이렇게 계산해서 내는 것을 본적이 있는데, 그러한 원리와 비슷하거나 동일한 것 같다

 

[정수론 - 등비수열의 합]

등비수열의 공식은 아래와 같다.

등비 배열의 합을 구하라는 문제를 아직 접한적이 없지만, 코테에선 나올 가능성이 제로에 수렴하는 것은 거의 없기때문에 알아두면 좋다.

int main()
{
    int a = 1, r = 2, n = 4; // 라고 가정
    vector<int> temp;
    cout << a * (int)pow(r,n) / (r-1) << '\n'; // 등비합 공식 사용
    
    for(int i = 0; i < n; ++i)
    {
    	temp.push_back(a);
        a *= r;
	}
    
    for(auto i : temp)
    	cout << i << '\n';
        
	return 0;
}

 

[정수론 - 승수, 제곱근]

- 업데이트 예정