[ C ] Greatest Common Divisor(최대공약수) 구하기 등

* 최대공약수 구하기

Write an algorithm that finds the greatest common divisor of two integers.

 

#include<stdio.h>

int main()
{
    int a, b; //2 integers
    int gcd;
    printf("Enter 2 int:");
    scanf_s("%d %d", &a,&b);
    for (int i = 1; i <= a; i++) {
        if (a % i == 0 && b % i == 0)
            gcd = i;
    }
    printf("%d", gcd);
    return 0;
}

 

[ Output ]

 

 

* output 예상하기, 구하기

#include <iostream>

using namespace std;
int main(void) {
	int i=1, j=0, n=6;
		while (j <= n / 2) {
			i = 1;
			while (i <= j) {
				cout << j << i;
				i++;
			}
			j++;
		}
	return 0;
}

 

[ Output ]

 

 

 

* O(log2n)인 지수 승 함수 (my_pow)

ive a algorithm that computes the remainder when is divided by . For simplicity, you may assume that is a power of . That is, for some positive integer .

-> 이 문제를 풀다가 pow는 double 일 때만 된다는 것을 알게되었다.

    pow(x,n)%p 를 하고 싶었으나 %연산은 int일 때만 된다고 해서 my_pow를 만들기로 했다.

 

#include<stdio.h>

int my_pow(int x, int n){
    if(n==0)    //exception(n = 2^k)
        return 1;
    else {
        int root_x = my_pow(x, n / 2);
        if (n % 2 == 0) //even exp(지수)
            return root_x * root_x;
        else            //odd exp(지수)
            return root_x * root_x * x;
    }
}

int main()
{
    int x = 3, n = 5;
    int result = my_pow(x, n); //x^^n

    int p = 4;
    int mod = result % p; //(x^^n) % p
    printf("%d", mod);
     return 0;
}

 

[ Output ]

 ( 243 % 4 = 3 )

 

[ 참고자료 ]

 

(참고 onsil-thegreenhouse.github.io/programming/problem/2018/03/29/problem_math_power/ )

 

 

 

* 배열을 둘로 나눴을 때 각 배열의 합의 차가 최소가 되도록 나누기

(사실 원래 문제는 이거다..ㅠ

Give an algorithm for the following problem. Given a list of distinct positive integers, partition the list into two sublists, each of size , such that the difference between the sums of the integers in the two sublists is minimized. Determine the time complexity of your algorithm. You may assume that is a multiple of .)

#include<stdio.h>
#include<stdlib.h>
#define arr_size 6
int main() {
	int left_sum=0, right_sum=0;
	int sum = 0;
	int num[arr_size] = { 5, 2, 1, 4, 6, 3 }; //array
	
	for (int i = 0; i < arr_size; i++)
		sum += num[i];
	//printf("%d", sum);

	right_sum = sum;
	int diff = 99999999;
	int diff_idx;
	for (int j = 0; j < arr_size; j++) {
		left_sum += num[j];
		right_sum -= num[j];
		if (abs(left_sum - right_sum) < diff) {
			diff = abs(left_sum - right_sum);
			diff_idx = j;
		}
		
	}
	printf("diff_idx: %d", diff_idx);
	return 0;
}


//원래는 딱 반을 나눴을 때 합의 차가 최소가 되도록 해야하는문제
//그냥 둘로 나눴을 때 합의 차가 최소가 되는 idx값 출력

 

[ Output ]

 

(참고 : m.blog.naver.com/PostView.nhn?blogId=puppy3698&logNo=221576346409&proxyReferer=https:%2F%2Fwww.google.com%2F )