CodeupCoder's Blog

안녕하세요,,

오늘은 나눗셈 정리에 대해서 알아볼까 합니다.

나눗셈 정리는 정수의 가장 기초적인 정리입니다.

정수는 상당히 어려울 수 있는(그리고 귀찮을 수 있는) 분야입니다.

그리고 제가 설명할 정수는 수(상) 까지는 수학이 되어 있어야 이해할 수 있는 부분입니다.

그럼 시작해 보겠습니다.

 **나눗셈 정리**

나눗셈 정리는 아마 여러분이 다 알지만 증명을 해 보지는 않은 그런 정리일 것입니다.

정리는 매우 간단합니다.

정리) 어떤 수를 다른 한 수로 나누었을 때의 몫과 나머지는 하나이다.

 - 이걸 좀 더 멋있게 쓰면...

   "임의의 정수 a, b (단, b>0)에 대하여 a=bq+r,0≤r<b 인 q,r 이 유일하게 존재한다." 정도가 되겠네요.

증명해 보겠습니다.

pf)

i) 존재성 증명

집합 S를 다음과 같이 정의하겠습니다.

S = {b-aq | b-aq>=0, q는 정수}

이때 자연수의 정렬성(S가 정수집합이고, 공집합이 아니면 S의 최소원소가 존재한다.)에 의해

S가 공집합이 아님을 증명하면 q와 r이 존재함을 증명할 수 있습니다.

여기서 자연수의 정렬성 증명은 생략하겠습니다.(자연수의 정렬성 증명만 한판을 써야되요 ㅋㅋㅋ)

q = -|b| 라 하면

b-aq >= b-(-|b|) >= b + |b| >=0

따라서 S는 0이 아닙니다.

by 자연수의 정렬성, S의 최소원소 r이 존재한다고 할 수 있습니다.

여기서 만약 r이 0이라면 0이 최소원소입니다.

하지만 r이 0이 아니라면 r < a 라는 것을 증명해야 합니다.

귀류법 사용하면

r >= a라 하자.

r > r-a  = b-aq-a = b-a(q+1) = S의 원소 이므로 r이 최소원소임에 모순이다.

-> r<a

이제 존재성이 증명되었습니다.

ii) 유일성 증명

b = aq1 +r1, b = aq2 + r2라고 합시다.(귀류법)

0<=r1, r2 < a 이므로

-a < r1 - r2 < a

r1 - r2 = a(q2 - q1) 이므로

-1 < q2-q1 < 1, q2, q1 은 정수이므로 q2-q1은 0이다.

-> q2 = q1, r2 = r1 이므로 q와 r은 유일하다

이렇게 증명이 끝났습니다.

다음에는 유클리드 호제법과 유클리드 알고리즘에 대하여 설명하겠습니다.

오타와 잘못된 점 지적은 환영입니다.

problem number. 1012

모범소스)

#include<stdio.h>

int main()
{
	float x;
	scanf("%f", &x);
	printf("%f", x);
	return 0;
}

모범소스 2)

#include<stdio.h>

int main()
{
	double x;
	scanf("%lf", &x);
	printf("%lf", x);
	return 0;
}

숏코딩)

main(float x){scanf("%f",&x);printf("%f",x);}

한 줄 평가 : 쉬운 문제입니다. 숏코딩도 쉽습니다.

problem number. 1013

모범소스)

#include<stdio.h>

int main()
{
    int a, b;
    scanf("%d %d", &a, &b);
    printf("%d %d", a, b);
    return 0;
}

숏코딩)

main(a,b){scanf("%d%d",&a,&b);printf("%d %d",a,b);}

한 줄 평가 : 쉬운 문제입니다. 숏코딩도 쉽습니다.

problem number. 1014

모범소스)

#include <stdio.h>

int main()
{
    char a,b;
    scanf("%c %c", &a, &b);
    printf("%c %c", b, a);
    return 0;
}

숏코딩)

main(){char a,b;scanf("%c %c",&a,&b);printf("%c %c",b,a);}

한 줄 평가 : 매우 쉬운 문제이다. 숏코딩은 더 할 수 있는데 걍 귀찮아서 조금만 했다.

+) 숏코딩 더 하는 방법 궁금한 분들은 댓글 남겨 주세요. 코드업에서 쪽지를 보내 드리던지 알아서 답해 드리겠습니다.

지난번에 IDE를 추천해 드린 이후 오늘은 문제를 풀 수 있는 사이트인 OJ를 추천해 드리겠습니다!!
OJ는 Online Judge의 약자로 채점을 해 주는 사이트라고 생각하시면 됩니다.

이미 저지 사이트에서 문제를 풀고 계실 것이지만(이 아니라 그렇다고 희망하지만...) 한 가지 사이트 말고 두세 가지 사이트에 계정을 만들어 푸는 것이 실력 향상에 도움이 될 것이라는 생각에 추천드립니다!

1. 코드업(CODEUP)

이 사이트는 개인적으로 제가 가장 좋아하는 사이트입니다.

문제가 체계적으로 정리되어 있고, 채점 속도도 뒤에 설명드릴 OJ들보다 빠른 것 같습니다.

https://codeup.kr/index.php

사이트입니다!!

2. 백준(BAEKJOON)

위에서 말씀드린 코드업은 개인이 운영하는 사이트라 문제가 엄청 많지는 않습니다.

하지만 이 사이트는 스타트 링크라는 엄연한 기업이 운영하고 있어서 문제 번화가 10000번을 넘어갑니다.

(그래서 처음 풀 때 뇌정지가 오죠 ㅋㅋ)

문제 수가 많다 보니 순위판 안에 들어가는게 매우 힘듭니다 ㅠ

https://www.acmicpc.net/

사이트입니다!!

3. KOISTUDY

이 사이트는 코드업과 매우 깊은 연관이 있다고 전해지는 사이트입니다.

(저도 왜인지는 모르겠습니다.)

근데 사이트가 좀 오래된 티가 팍팍 납니다(저만 그런가요..)

그리고 채점할 때 시간이 좀 오래 걸리는 편이라 많이 선호하진 않습니다만 문제는 계속 열심히 풀고 있네요.

(백준보다 순위판에 오르기가 훨씬 쉬워서 열심히 풀고 있다는 여담이...)

http://www.koistudy.net/

사이트입니다!!

4. JUDGEON

저도 여기서는 문제를 풀어 본 적이 없어서 잘 모르는 OJ입니다.

사이트 주소만 올릴게요~

http://www.judgeon.net/

글을 읽어주셔서 감사합니다!!

코딩 공부 열심히 하세요~!