수학1-1(나머지, 최대공약수, 최소공배수, GCD의 합, 진법)

[kdomo]

이론 정리 (10월 11일 까지)

• 최대공약수(GCD)를 구하는 방법 '유클리드 호제법'의 개념
• 최대공약수를 이용하여 최소공배수(LCM)를 구하는 방법
• 기본적인 아스키코드
• 10진수 <-> 2진수, 8진수, 16진수 변환 시 Integer API 사용

숙제 (10월 16일 까지)

[2501번] 약수구하기
[3460번] 이진수
[10818번] 최소,최대
[2460번] 지능형 기차 2
[10870번] 피보나치 수 5
[2309번] 일곱 난쟁이
[2609번] 최대공약수와 최소공배수
[2693번] N번째 큰 수
[1978번] 소수 찾기
[1292번] 쉽게 푸는 문제
[2581번] 소수

[jinjinhee]

최대공약수(GCD)를 구하는 방법 '유클리드 호제법'의 개념

숫자 a, b가 있을 때, a를 b로 나눈 나머지와 b 의최대 공약수 는 a 와 b 의 최대 공약수 가 같다는 것을 의미한다.

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

최대공약수를 이용하여 최소공배수(LCM)를 구하는 방법

def lcm(a, b):
    return a * b / gcd(a, b)

기본적인 아스키코드

#ord(문자) : 아스키 코드를 반환해준다
#chr(숫자) : 숫자에 맞는 아스키 코드를 반환한다
chr(65) #A
ord("A") #65

10진수 <-> 2진수, 8진수, 16진수 변환 시 Integer API 사용

#10진수->2진수, 8진수, 16진수 변환
bin(20) #0b10100
oct(20) #0o24
hex(20) #0x14
#10진수<-2진수, 8진수, 16진수 변환
int('0b10100',2)
int('0o24',8)
int('0x14',16)

[josuehyeon]

유클리드 호제법

1. 큰 수를 작은 수로 나눈다.

2. 나누는 수를 나머지로 계속 나눈다.

3. 나머지가 0이 나오면 나누는 수가 최대공약수

import java.util.Scanner;

public class gcdLcm {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();

	//최대공약수
	int c = bcd(Math.max(a, b), Math.min(a, b));
	System.out.println(c);
	
	//최소공배수구하기
	int d = (a/c)*(b/c)*c;
	System.out.println(d);
	
}
static int bcd(int bn, int sn) {
	int r = bn % sn;
	
	if(r == 0 ) {
		return sn;
	}
	else {
		return bcd(bn, r);
	}
}

}

기본적인 아스키코드

10진수 <-> 2진수, 8진수, 16진수 변환

public class binary {
public static void main(String[] args) {
int i = 123;

	//2, 8, 16 진수로 바꾸기 
	String binaryString = Integer.toBinaryString(i);
	String octalString = Integer.toOctalString(i);
	String hexString = Integer.toHexString(i);
	
	System.out.println(binaryString); //1111011
	System.out.println(octalString); //173
	System.out.println(hexString); //7b
	
	//10진수로바꾸기
	int binaryToDecimal = Integer.parseInt(binaryString, 2);
	int octalToDecimal  = Integer.parseInt(octalString, 8);
	int hexToDecimal    = Integer.parseInt(hexString, 16);
	
	System.out.println(binaryToDecimal); 
	System.out.println(octalToDecimal);
	System.out.println(hexToDecimal); 
	//123
}

}

[jonggking]

유클리드호제법

숫자 a, b가 있을 때, a를 b로 나눈 나머지와 b의 최대 공약수는 a 와 b 의 최대 공약수와 같음.
계속해서 a 를 b로 나누어서 b를 a에 나눈 나머지를 b 에 대입시켜서 b가 0이 될 때까지 반복 하면, 남는 a 값이 바로 최대 공약수

    
    while b > 0:
        a, b = b, a % b 
    return a

이를 이용한 최소공배수
def lcm(a, b):
    return a * b / gcd(a, b)

기본적인 아스키코드

ord("A")
아스키코드 -> 문자
chr(65)

10진수 <-> 2진수, 8진수, 16진수 변환

파이썬 자체 내장함수 이용
2진수 : Binary
8진수 : Octal
16진수 : Hexadecimal

bin(value) : 10진수 => 2진수 변환
oct(value) : 10진수 => 8진수 변환
hex(value) : 10진수 => 16진수 변환

bin(100) #0b1100100
oct(100) #0o144
hex(100) #0x64

OR   

format(100,'b')  #1100100
format(100,'o')  #144
format(100,'x') #64

[kdomo]

최대공약수(GCD)를 구하는 방법 '유클리드 호제법'의 개념

• 유클리드 호제법의 개념
  • 유클리드 호제법은 두 개의 수가 주어졌을 때, 최대 공약수를 구하는 알고리즘
  • 두 개의 수 A, B가 존재하고, A를 B로 나눈 나머지를 C 라고 할 때(A>B) A와 B의 최대 공약수는 B와 C의 최대공약수와 같다
  • 이러한 성질을 이용하여 계속적으로 나눗셈을 진행해서 C가 0이 되었을 때, 즉 나머지가 0일 때의 나누는 수가 최대 공약수가 된다
• 예시
  • 72, 42 두 수를 유클리드 호제법을 사용하여 최대 공약수를 구하는 과정
    1.두개의 수 중에서 큰 수를 찾는다. (72)
    2.큰 수를 작은 수로 나누어 나머지를 구한다. ( 72 % 42 = 30)
    3.나머지를 가지고 앞에서 나눈 수를 다시 나눠서 나머지를 구한다. ( 42 % 30 = 12 )
    4.3번의 과정을 반복 ( 30 % 12 = 6 )
    5.3번의 과정을 반복 ( 12 % 6 = 0 )
    6.5번의 과정으로 인해 나머지가 0이 되었고 그 시점에 나눈 수가 최대 공약수가 된다. (6)
• Java 코드로 구현

// 재귀 함수 사용 - 구현이 간단하고 코드가 간결
// 시간 복잡도 O(logN)
int GCD(int a, int b){
    if (a % b == 0) {
        return b;
    }
    return GCD(b, a%b);
}

최대공약수를 이용하여 최소공배수(LCM)를 구하는 방법

• 최소 공배수 구하기
  • 두 자연수 A, B의 최대 공약수가 G, 최소공배수가 L 이라고 가정할 때
  • L = A * B / G 가 성립한다.
• Java 코드로 구현

int LCM(int a, int b) {
    // L = A * B / G
    // 0이 아닌 두 수의 곱 / 두 수의 최대 공약수
    return a * b / GCD(a, b);
}

기본적인 아스키코드

• 미국정보교환표준부호(American Standard Code for Infomation Interchange) 줄여서 ASCII는 1963년 미국 ANSI에서 표준화한 정보교환용 7비트 부호체계이다.
• 000(0x00)부터 127(0x7F)까지 총 128개의 부호가 사용된다.

// 기본적인 아스키 코드
char A = 65; // 또는 char A = 'A';
System.out.println(A); // A
System.out.println(A - 0); // 65

char a = 'a'; // 또는 char a = 'a';
System.out.println(a); // b
System.out.println(a - 0); // 97

10진수 <-> 2진수, 8진수, 16진수 변환 시 Integer API 사용

• 10진수 -> 2진수, 8진수, 16진수

Return Type	Class	Method	Description
static String	java.lang.Integer	toBinaryString(int i)	10진수 -> 2진수
static String	java.lang.Integer	toOctalString(int i)	10진수 -> 8진수
static String	java.lang.Integer	toHexString(int i)	10진수 -> 16진수

int decimal = 10;
System.out.println("10진수 : " + decimal); // 10진수 : 10
System.out.println("2진수 : " + Integer.toBinaryString(decimal)); // 2진수 : 1010
System.out.println("8진수 : " + Integer.toOctalString(decimal)); // 8진수 : 12
System.out.println("16진수 : " + Integer.toHexString(decimal)); // 16진수 : a

• 2진수, 8진수, 16진수 -> 10진수

Return Type	Class	Method	Description
static int	java.lang.Integer	Integer.parseInt(String s)	문자열(s)를 10진수로 읽어서 int로 반환
static int	java.lang.Integer	Integer.parseInt(String s, int radix)	문자열(s)를 변환할 진수(radix)로 읽어서 int로 반환

System.out.println("2진수(1010) -> 10진수 : " + Integer.parseInt("1010", 2)); // 2진수(1010) -> 10진수 : 10
System.out.println("8진수(12) -> 10진수 : " + Integer.parseInt("12", 8)); // 8진수(12) -> 10진수 : 10
System.out.println("16진수(a) -> 10진수 : " + Integer.parseInt("A", 16)); // 16진수(a) -> 10진수 : 10