GODOG

C++ 유클리드 호제법을 이용하여 최대공약수/최소공배수 구하기.

[ 코 드 ]

#include <iostream>

using namespace std;

int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}

int main() {

	cout << gcd(25, 45) << "\n";
	cout << 15*45/gcd(15, 45) << "\n";

	return 0;
}

12라인 > gcd 함수는 회귀 함수로서 두 인수 a와 b를 주면 a와 b의 최대공약수를 리턴한다.

+) "b ? ㄱ : ㄴ" 은 삼항 연산자로 b가 참이면 ㄱ을 실행하고 거짓이면 ㄴ을 실행한다.

13라인 > 최소 공배수 = a*b / 최대공약수; 이다.

[ 결 과 ]

C++ 회귀를 이용하여서 조합(Combination) 구현.

[코 드]

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<vector<int>> result;
vector<int> v = { 1,2,3,4,5 };
int len = v.size();
vector<int> sub;

void ser(int k) {

    if (k == len  ) {
        result.push_back(sub);
    }
    else {
        sub.push_back(v[k]);
        ser( k + 1);
        sub.pop_back();
        ser( k + 1);
    }
}

int main()
{
    ser(0);

    for (int i = 0; i < result.size(); i++) {
        for (int k = 0; k < result[i].size(); k++) {
            cout << result[i][k];
        }
        cout << "\n";
    }

    return 0;
}

8라인 > 결과를 저장할 2차원 vector

9라인 > vector<int> v : 조합을 실행할 값의 집합

10라인 > int len : 조합을 실행할 값의 개수

[ 결 과 ]

C++ 회귀를 이용한 순열(permutation) 구현.

[ 코 드 ]

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<vector<int>> result;
vector<int> v = { 1,2,3,4 };
int len = v.size();
bool choose[4];
vector<int> temp;

void ser( int k) {
	if (k == len) {
		result.push_back(temp);
	}
	else {
		for (int i = 0; i < len; i++) {
			if (choose[i]) continue;
			choose[i] = true;
			temp.push_back(v[i]);
			ser(k + 1);
			temp.pop_back();
			choose[i] = false;
		}
	}
}

int main() {

	ser(0);
	for (int i = 0; i < result.size(); i++) {
		for (int k = 0; k < result[i].size(); k++) {
			cout << result[i][k] << " ";
		}
		cout << "\n";
	}

}

7라인 > 결과 값들을 저장할 2차원 vector

8라인 > vector<int> v : 순열을 실행할 값들

9라인 > int len : 값들의 개수

10라인 > len만큼의 크기를 갖는 bool 배열

[ 결 과 ]