을 토막글로 대충대충 써놓은 글귀들이다. 본격 지금까지 얼마나 이민혁이 멍청했나 복습하는 공부과정

• Hackers Rank에서의 학습

• 동적 기획법 - Dynamic Programming
• 분할 정복법 - Divide & Conquer

참고로, 문제해결법의 범위에 대해서는, 아래 그림과 같이 생각할 수 있다.

컴퓨터를 이용해서 최대 공약수를 구하는 알고리즘.

유클리드 알고리즘은 최대 공약수의 성질을 이용해 뺄셈과 두 값의 교환이라는 기본동작의 반복으로 최대공약수를 도출함.

두 수 A, B가 130, 20이라면.

A = a * GCD((Greatest common divisor , 최대 공약수)) (130 = 13 * 10)
B = b * GCD (20 = 2* 10)

위의 a, b 는 각각 A, B 에서 GCD 이외의 모든 인수들을 곱한 값을 의미하고, a, b는 서로 소인 경우다.

이때 A-B와 B의 최대 공약수는,

A-B = a * GCD - B * GCD = (A-B) * GCD;

(a-b)와 b는 서로 소. A-B와 B의 최대공약수 역시 GCD.

그러므로,

GCD(x, y) = GCD(x-y, y)

그리고 최대공약수는 두 정수의 순서에 관계없이 같으므로 다음성질도 갖는다.

GCD(x, y)= GCD(y, x)

0이 아닌 정수 k와 0과의 최대공약수는 0이다. 그래서 다음이 성립.

GCD(k, 0) = k

과정은 다음과 같다.

1. 임의 정수 2개 입력.
2. B가 A 보다 크면 두수를 교환한다.
3. A ← A-B
4. A가 0이면 B가 최대공약수, 0이 아니면 2로 돌아간다.

int main(){
 
    int a, b, tmp;
 
    scanf("%d %d", &a, &b);
 
    while(a != 0){
        if(b>a){//swap
            tmp = b;
            b = a;
            a =tmp;
        }
        a = a-b;
 
    }
 
    printf("%d\n", b);
 
    return 0;
}

양의 정수 A, B에 대해 아래 식을 만족하는 정수 X, Y가 존재하는 것이 확장 유클리드 알고리즘.

  AX + BY = D, D는 A, B의 최대 공약수.

• '약수'의 갯수가 홀수 인것들은 '제곱수'들 뿐이다. 신기하다. 내가 이렇게 멍청했다니.

#include <stdio.h>
#include <math.h>
int main(){
 
    int sum=0, a, b;
    int odd1=0, odd2=0;
    scanf("%d %d", &a, &b);
 
    odd1 = (int)sqrt(b); // 짝수개 개수
    odd2 = (int)sqrt(a-1); // 이 범위에서의 짝수개 갯수.
 
    sum =(b - odd1) - (a - odd2) + 1;
 
    printf("%d\n", sum);
 
}