플리나를 위하여

Smallest multiple

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

1~20까지의 연속된 수에 대한 최소공배수를 구하는 문제다. 

1. n은 소수인가?
2. n이 소수라면 20 이하의 가장 큰 n^m을 구해서 결과에 곱한다.
3. 1~2를 20까지 반복

이와 같이 진행하면 결과에는 순서대로 16, 9, 5, 7, 11, 13, 17, 19가 곱해진다.

long long int Problem005(int number)
{
	long long int ret = 1;
	long long int factor;
	for (int i = 2; i <= number; i++)
	{
		factor = 1;
		if (IsPrime(i))
		{
			while (factor <= number)
			{
				factor *= i;
			}
			factor /= i;
			ret *= factor;
		}
	}
	return ret;
}

bool IsPrime(int number)
{
	bool ret = true;
	for (int i = 2; i * i <= number; i++)
	{
		if (number % i == 0)
		{
			ret = false;
			break;
		}
	}
	return ret;
}

Largest palindrome product

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

세 자리 수끼리 곱해서 구할 수 있는 가장 큰 대칭수 구하기

int Problem004(int digit)
{
	int ret = -1;
	int start = 1;
	for (int i = 1; i < digit; i++)
	{
		start *= 10;
	}
	int end = start * 10;
	for (int i = start; i < end; i++)
	{
		for (int j = start; j < end; j++)
		{
			if (SymmetryChecker(i * j) && ret < i * j)
			{
				ret = i * j;
			}
		}
	}
	return ret;
}

int GetDigit(int number)
{
	if (number == 0)
	{
		return 0;
	}
	if (number < 0)
	{
		number *= -1;
	}
	int ret = 1;
	while (true)
	{
		number /= 10;
		if (number == 0)
		{
			break;
		}
		ret++;
	}
	return ret;
}

bool SymmetryChecker(int number)
{
	int digit = GetDigit(number);
	char* numArr = new char[digit];
	for (int i = 0; i < digit; i++)
	{
		numArr[i] = number % 10;
		number /= 10;
	}

	bool ret = true;
	for (int i = 0; i < digit / 2; i++)
	{
		if (numArr[i] != numArr[digit - i - 1])
		{
			ret = false;
			break;
		}
	}
	delete[] numArr;
	return ret;
}

Largest prime factor

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

600,851,475,143 의 소인수 중에서 가장 큰 소인수를 구하기.

long long int Problem003(long long int number)
{
	long long int ret = number;
	long long int i = 1;
	while (i * i <= number)
	{
		i++;
		if (number % i == 0)
		{
			ret = i;
			number /= i;
			i = 1;
			if (number == 1)
			{
				break;
			}
		}
	}
	return ret;
}

Even Fibonacci numbers

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

400만까지의 범위에서 짝수인 피보나치 수의 합을 구하기

int Problem002(int first, int second, int scope)
{
	int ret = 0;
	int third = first + second;

	if (first % 2 == 0)
	{
		ret += first;
	}
	if (second % 2 == 0)
	{
		ret += second;
	}

	while (true)
	{
		if (third > scope)
		{
			break;
		}
		if (third % 2 == 0)
		{
			ret += third;
		}
		first = second;
		second = third;
		third = first + second;
	}
	return ret;
}

Multiples of 3 and 5

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

below 1000이므로 1000 미만까지의 수에서 3 or 5의 배수인 수의 합을 구하는 문제

// 일반적인 구현
int Problem001(int num1, int num2, int scope)
{
	int ret = 0;
	for (int i = 1; i < scope; i++)
	{
		if (i%num1 == 0 || i % num2 == 0)
		{
			ret += i;
		}
	}
	return ret;
}

// 수학 공식을 통한 구현
int Problem001(int num1, int num2, int scope)
{
	scope--;
	return sumUpToScope(num1, scope) + sumUpToScope(num2, scope) - sumUpToScope(num1 * num2, scope);
}

int sumUpToScope(int num, int scope)
{
	return (((1 + (scope / num)) * (scope / num)) / 2) * num;
}

아래와 같은 소스를 실행하였을 때 화면에 출력되는 값은 무엇인가.

즉, *(*(pptr_int_array+3)+2) 에 해당하는 값은 무엇인가.

int i = 0, j = 0, value = 0;

int row = 4, col = 5;

int **pptr_int_array = (int **)malloc(sizeof(int *) * row);

for (i = 0; i < row; i++) {

pptr_int_array[i] = (int *)malloc(sizeof(int) * col);

}

for (i = 0; i<row; i++) {

for (j = 0; j<col; j++) {

value++;

pptr_int_array[i][j] = value;

}

}

printf("%d\n", *(*(pptr_int_array + 3) + 2));

답은 18

값을 대입하기 전에 value++;를 하였으므로 최초 입력 값은 1

pptr_int_array[3][2]에 저장이 되므로 col이 5개짜리인 row를 3번 거친 후의 3번째 배열이므로 18번째 배열이다. 

따라서 화면에 출력되는 값을 18이다. 

다음 소스 수행 결과로 예상되는 변수들의 구조를 그림으로 그리시오.

int int_value_A = 100;

int int_value_B = 200;

int *ptr_int1 = &int_value_A;

int *ptr_int2 = &int_value_B;

*ptr_int1 = *ptr_int2;

ptr_int1 = ptr_int2;

*ptr_int1 = *ptr_int2;에 의해 int_value_A의 값이 200이 된다. 

ptr_int1 = ptr_int2;에 의해 ptr_int1은 int_value_B를 가리키게 된다. 

따라서 소스에 의한 수행 결과는 아래와 같다. 

구조체를 이용해 5명의 국영수의 평균을 구하시오

struct student
{
	char	name[30];
	float	korean;
	float	english;
	float	math;
	float	avg;
};

int main()
{
	struct student *ptr_student_new = NULL;
	int students = 5;

	ptr_student_new = (struct student*) malloc(sizeof(struct student) * students);

	*(ptr_student_new + 0) = { "Lee", 81, 79, 99, 0 };
	*(ptr_student_new + 1) = { "Kim", 80, 82, 78, 0 };
	*(ptr_student_new + 2) = { "Park", 79, 85, 75, 0 };
	*(ptr_student_new + 3) = { "Hong", 75, 87, 82, 0 };
	*(ptr_student_new + 4) = { "Jung", 90, 89, 65, 0 };

	struct student average = { 0, };

	for (int i = 0; i < students; i++) 
	{
		average.korean = average.korean + (ptr_student_new + i)->korean;
		average.english = average.english + (ptr_student_new + i)->english;
		average.math = average.math + (ptr_student_new + i)->math;
	}

	average.korean = average.korean / 5;
	average.english = average.english / 5;
	average.math = average.math / 5;

	cout << "국어 평균: " << average.korean << "\n";
	cout << "영어 평균: " << average.english << "\n";
	cout << "수학 평균: " << average.math << "\n";

	free(ptr_student_new);

	return 0;
}

 malloc으로 동적할당할 한 후의 활용에 대한 연습문제. 문제를 푸는 것 자체는 어렵지 않았으나 malloc의 크기를 따로 구해서 for문을 돌리려는 삽질을 하느라 시간이 조금 걸렸다. 생각해보면 동적할당은 애초에 어느정도로 할당할지에 대한 값이 있을테니 해당 값을 별도로 저장해서 관리하면 될 일이었다. _msize(void)라는 함수를 알아내긴 했지만 비표준이라 사용하기도 곤란한 함수였다. 애초에 동적할당은 변수를 이용해서 하거나 특정 값을 이용해서 할테니 그 값만 따로 관리해주면 될 일이어서 결과적으로 삽질을 한게 되었다.