유니유니

#include<iostream>
#include<fstream>
using namespace std;

struct node { //노드 
	int key;
	node* left = nullptr;
	node* right = nullptr;
};
int height(node* root)
{
	if (root == nullptr)
		return 0;
	int max_h = (height(root->right) > height(root->left)) ? height(root->right) : height(root->left);
	return 1 + max_h;
}
node* getNode()
{
	node* newnode = (node*)malloc(sizeof(node));
	return newnode;
}
node* insertBST(node* root, int newKey)
{
	node* p = root;
	node* q = nullptr;	//부모 노드

	//(1) 삽입 위치(q) 탐색
	while (p != nullptr)
	{
		q = p;
		if (newKey == p->key)
		{
			cout << "i " << newKey << " : The key already exists" << endl;
			return root;
		}
		else if (newKey < p->key)
			p = p->left;
		else
			p = p->right;
	}

	//(2) 새로운 노드 할당
	node* newnode = getNode();
	newnode->key = newKey;
	newnode->right = newnode->left = nullptr;

	//(3) q의 자식 노드로 newkey 삽입
	if (q != nullptr) //루트노드가 null인 경우
	{
		if (newKey < q->key)
			q->left = newnode;
		else
			q->right = newnode;
	}
	if (root == nullptr)		return newnode;
	return root;
}
int noNodes(node* root, int* num)
{
	if (root == nullptr)
		return 0;
	else if (root->right != nullptr)
	{
		(*num)++;
		noNodes(root->right, num);
	}
	else if (root->left != nullptr)
	{
		(*num)++;
		noNodes(root->left, num);
	}
	else
		(*num)++;
	return *num;
}
node* maxNode(node* root)
{
	node* p = root;
	while (p->right != nullptr)
		p = p->right;
	return p;
}
node* minNode(node* root)
{
	node* p = root;
	while (p->left != nullptr)
		p = p->left;
	return p;
}
node* deleteBST(node* root, int deleteKey)
{//삭제 알고리즘 ;; (1) 삭제할 데이터 위치 탐색 (2) 데이터 이동 (3) 이동한 데이터의 node 삭제
	node* p = root;		//삭제할 노드
	node* q = nullptr;	//p의 부모 노드

	//(1)삭제 위치 p 탐색
	while ((p != nullptr) && (p->key != deleteKey))
	{
		q = p;
		if (deleteKey < p->key)
			p = p->left;
		else
			p = p->right;
	}

	//노드가 존재하지 않는 경우
	if (p == nullptr)
	{
		cout << "d " << deleteKey << " : The key does not exist" << endl;
		return root;
	}

	//차수가 0인 경우의 삭제 ;; (1) p=root (2) p!=root
	if (p->left == nullptr && p->right == nullptr)
	{
		if (q == nullptr)
			root = nullptr;
		else {
			if (q->left == p)		q->left = nullptr;
			else						q->right = nullptr;
		}
		delete(p); //p 삭제
	}
	//차수가 1인 경우의 삭제 ;; (1) p=root (2) p!=root
	else if (p->left == nullptr || p->right == nullptr)
	{
		//현재 갖고 있는 자식 노드를 저장
		node* child = (p->left != NULL) ? p->left : p->right;
		if (q == nullptr)
			root = child;
		else
		{
			if (q->left == p)
				q->left = child;
			else
				q->right = child;
		}
		delete(p); //p 삭제
	}
	//차수가 2인 경우의 삭제 ;; 
	else
	{
		char flag;				//flag 변수 (삭제할 데이터의 위치 탐색)
		node* n = root;

		if (height(p->left) > height(p->right))
		{
			n = maxNode(p->left);
			flag = 'L';
		}
		else if (height(p->left) < height(p->right))
		{
			n = minNode(p->right);
			flag = 'R';
		}
		else
		{//양쪽 서브트리의 높이가 동일한 경우 --> 트리의 노드 개수 비교
			int Lnode = 0, Rnode = 0;
			if (noNodes(p->left, &Lnode) >= noNodes(p->right, &Rnode))
			{
				n = maxNode(p->left);
				flag = 'L';
			}
			else
			{
				n = minNode(p->right);
				flag = 'R';
			}
		}

		p->key = n->key; //데이터 이동

		if (flag == 'L')
			p->left = deleteBST(p->left, n->key);
		else
			p->right = deleteBST(p->right, n->key);
	}
	return root;
}
void inorderBST(node* root)
{
	if (root == nullptr)
		return;
	inorderBST(root->left);
	cout << root->key << " ";
	inorderBST(root->right);
}

int main()
{
	ifstream file;
	file.open("BST-input.txt");

	char mode;
	int key;
	node* p = nullptr;
	node* root = p;

	while (!file.eof())
	{
		file >> mode >> key;
		if (mode != 0)
		{
			if (mode == 'i')
			{
				p = insertBST(p, key);
				inorderBST(p);
				cout << endl;
			}
			else
			{
				p = deleteBST(p, key);
				inorderBST(p);
				cout << endl;
			}
			mode = 0;
		}
	}
	return 0;
}

구현을 위한 순서도 작성 

최대공약수 (GCD, Greatest Common Divisor) 구현 함수 int GCD

최소공배수 (LCM, Least Common Multiple) 구현 함수 int LCM

#include <iostream>

using namespace std;

int GCD(int a, int b)
{
   if(b==0)
      return a;
   else
      return GCD(b, a%b);
}

int LCM(int a, int b)
{
   return a*b/GCD(a, b);
}

int main()
{
   int numTest;
   cin >> numTest;
   
   for(int i=0; i<numTest; i++)
   {
      int a, b;
      cin >> a >> b;
      cout << GCD(a,b) << " " << LCM(a,b) << endl;
   }
   
   return 0;
}

최대공약수 (GCD)는 재귀함수 return GCD(b, a%b)를 이용하고

최소공배수는 두 수의 곱이 최대공약수와 최소공배수의 곱과 같음을 이용하였다.

a * b = LCM(a,b) * GCD(a,b) 이므로 LCM(a,b) = a * b / GCD(a,b)

#include <iostream>

using namespace std;

int main()
{
   int testcase, year;
   cin >> testcase;
   
   for(int i=0;i<testcase;i++){
      cin >> year;
      
      if((year%4 ==0 && year%100 !=0) || year%400==0)
      {
         cout << "윤년" << endl;
      }
      else
      {
         cout << "아님" << endl;
      }
   }
   
   return 0;
}

testcase 횟수 입력 받고, 년도 입력 받은 다음

해당 년도가 윤년인지 아닌지 출력해줌

* 핵심 : (year%4 ==0 && year%100 !=0) || year%400==0

#include <iostream>

using namespace std;

int main()
{
   int s_year, e_year;
   
   cin >> s_year >> e_year;
   
   for(int i= s_year; i<= e_year; i++)
   {
      if((i%4 ==0 && i%100 !=0) || i%400==0)
      {
         cout << i << endl;
      }
   }
   
   return 0;
}

위의 알고리즘을 응용하여

시작년도와 끝년도를 입력받아, 두 년도 사이의 모든 윤년을 출력해주는 프로그램 작성

[출력 예시]

# Visual Studio 2019

# 가장 간단한 정수해를 구하는 프로그램

# 선형방정식 : 미지수의 최고차항의 차수가 1을 넘지 않는 다항 방정식. 변수는 하나일 수도, 둘 이상일 수도 있다.

본문에서는 미지수가 2개(x, y)인 선형방정식을 다루고자 하며, 모두 다음과 같은 꼴로 표현된다.

ax + by = c

이 식은 미지수가 2개이기 때문에, 한 쌍의 근을 구하려면 2개의 식이 필요하다. (연립방정식)

따라서, 이 부정방정식에서 알아낼 수 있는 것은 해들의 일반화 식이다.

부정방정식의 풀이는 해의 형태를 제시하는 게 일반적이다. 정수론에서는 무수한 해 중에서도 '정수해'만을 취급하기로 한다. 

# 부정방정식 : 식의 개수보다 미지수의 개수가 많아, 근이 무수히 많은 방정식

예를 들어, 부정방정식 x+y=10 의 해를 구한다고 생각해보자,

순서쌍으로 나타내면 ... (-2,12) (-1,11) (0,10) (1,9) (2,8) ... 로 무수히 많다는 것을 알 수 있다.

('자연수해'로 범위를 축소한다면 유한개의 해를 가질 수 있다)

# 선형방정식의 가장 간단한 정수해 구하기

하나의 정수해를 구하면, 일반화 식을 만들어 낼 수 있다. 선형방정식에서 간단한 정수해를 구하는 프로그램을 작성했다.

여기서 '간단한'은 두 해의 절댓값의 합이 가장 작은 것을 의미한다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int main() {

	int a, b, result;
	int cnt1 = 0, cnt2;

	printf("Input A, B, result (Ax + By = result) (A < B) \n");
	scanf("%d %d %d", &a, &b, &result);

	for (int i = a;i < 100000; i += a) {
		cnt1 += 1; cnt2 = 1;
		for (int j = b;j > -100000;j -= b) {
			if (i + j == result) {
				printf("%d * %d + %d * %d = %d \n", a, cnt1, b, cnt2, i + j);
				exit();
			}
			cnt2 -= 1;
		}
	}

	getchar();
	return 0;
}

단순히 for문을 돌려 간단한 정수해를 찾아내는 프로그램이다.

유의할 점이 있다면 입력 형태에서 A<B 를 맞춰줘야 한다는 점이다. 비교해서 바꾸는 코드를 추가한다면 더 완벽한 프로그램

# 프로그램 이용 예시

(1) 7x + 17y = 60  을 풀고자 한다 (Ctrl + F5)

     Input A, B, result (Ax + By = result) (A < B)
     7 17 60

    7 * 11 + 17 * -1 = 60

(2) 11x + 4y = 21 을 풀고자 한다. 입력 조건이 A<B 이므로 4를 먼저 입력하고 11을 입력해준다.

 => 4x + 11y = 21 을 풀게 되는 것

      Input A, B, result (Ax + By = result) (A < B)
      4 11 34
      4 * 14 + 11 * -2 = 34

(3) 103x + 1001y = 1 을 풀고자 한다. 큰 숫자이다.

      이 방정식은 무리없이 계산되지만, 만약 값이 안나온다면 for 문 안의 '100000 / -100000' 를 조정하면 된다.

      Input A, B, result (Ax + By = result) (A < B)
      103 1001 1
     103 * 311 + 1001 * -32 = 1 

(5) 2x + 4y = 5 를 풀고자 한다 (Ctrl + F5)

      Input A, B, result (Ax + By = result) (A < B)
      2 4 5

     결과가 나오지 않는다.

     숫자가 크지도 않고, A<B 의 조건에도 위배되지 않았는데 왜일까?

     그 이유는 바로 정수해가 존재하지 않기 때문이다.