KAIST 단일서비스 로그인
Language

생활정보(이전)


> 정보 > 생활정보(이전)

042-350-2071

통화 가능 시간

평일 13:00-17:00

메일 | 건의게시판

?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 수정 삭제 스크랩
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 수정 삭제 스크랩

안녕하세요 밀린 연재를 명절 연휴 기간 동안 어떻게든 따라잡아보고자 하는 독거노인입니다. 저번 포스팅이 이미 2페이지로 넘어갔다는 사실이 저의 게으름을 대변해주는 것 같아 씁쓸하네요. 밀린 연구는 또 언제 따라잡을지 생각하니 가슴 한구석이 먹먹해집니다. 그나저나 킹스맨 보세요 두 번 보세요.

 

저번 포스팅에서는 유클리드 호제법에 대해서 얘기를 하면서 지붕이 어쩌고 장판이 어쩌고 이런저런 비유를 들었던 것 같은데요 기억이 잘 안나시는 분들은 잠깐 틈을 내어 다시 읽어보고 오시면 좋을 것 같습니다. 사실 저도 잘 기억이 안 나서 새 창에 띄워놓고 보면서 쓰고 있는 중이거든요.

 

지난 번 포스팅을 굳이 찾아보기 귀찮은 분들을 위해서 저번 포스팅에서 다룬 내용들을 요약하자면, 첫째, 유클리드 호제법의 도움으로 우리는 원래의 수에서 적절한 수만큼을 덜어내거나 더할 수가 있다. 둘째, 이러한 과정에서 배수인지 아닌지 여부가 보존되려면 이 적절한 수는 우리가 약수임을 판별하고자 하는 수 p의 배수여야 한다. 셋째, 그렇다면 얼마만큼을 덜어내거나 더하는 것이 효율적으로 소인수분해를 도와줄 수 있을 것인가.

 

이번 포스팅에서는 지난 시간에 비유를 들어가면서 얘기했던 부분들을 구체적으로 좀 더 짚어가고자 합니다. 가장 기본이 되는 끝자리 소거법부터 Split method까지 살펴보도록 하겠습니다.

 

1) 0을 적절히 활용하자.

 

0은 본질적으로 소인수분해를 쉽게 만드는 기능을 합니다. 1980을 소인수분해 하는 것과 198을 소인수분해하는 것에는 별 난이도 차이가 없어요. 1980이 17의 배수인지 알아보는 것은 198이 17의 배수인지 알아보는 것과 다름이 없지요. 따라서 끝자리 수를 0으로 만들면 문제가 상당히 쉬워집니다. 예를 들면 2187이라는 숫자가 13,17,19,..., 등의 숫자로 나누어 떨어지는지를 알고 싶을땐 다음과 같이 손쉽게 뒷자리만 조정을 해주면 됩니다.

 

2187 + 13 = 2200 <===13을 더했지만 13의 배수 아님. 따라서 13의 배수가 아님.

2187 - 17 = 2170  <===17을 뻿지만 17의 배수 아님. 따라서 17의 배수가 아님.

2187 - 57 = 2130  <=== 19의 3배인 57을 뺏지만 19의 배수 아님. 따라서 19의 배수가 아님.

2187 + 23 = 2210 <=== 23을 더했지만 23의 배수가 아님. 따라서 23의 배수가 아님.

 

이런 식으로 배수여부를 쉽게 판별할 수가 있는거죠. 핵심은 끝자리를 0으로 맞춰줌으로 해서 4자리 수가 아닌 3자리 수에 대한 배수판별로 바꿔주는 것입니다. 217은 7*31이니까 당연히 17의 배수가 아니고 213은 3*71이니까 당연히 19의 배수가 아니게 되는 거죠. 221이 13*17이라는 것은 앞의 두 경우에 비해 상대적으로 관찰하기가 힘들 수 있습니다. 보통 두 자리 소수의 곱 같은 경우는 외우고 있지 않은 한 자칫 소수로 보이는 경우가 많습니다. 221, 247, 323, 361 이런 소수처럼 보이는 합성수들은 귀찮더라도 외워놓으면 유용하게 사용되며 소인수분해에 걸리는 시간을 많이 단축시켜줍니다(사실 굳이 외우지 않더라도 많이 하다보면 자연스럽게 외워지니 크게 신경쓸 필요는 없습니다.)

 

2) 꼭 마지막 자리를 0으로 맞출 필요는 없다. 첫째 자리를 0으로 맞추는 것도 한 방법이다.

 

위에선 2187의 23에 대한 배수판별을 위하여 뒤에 23을 더해서 2210을 만드는 방법을 위해서 사용하였습니다. 하지만 앞자리를 조정하는 게 때때로는 더 쉬운 경우도 많습니다. 앞자리를 사용할 경우에는 다음과 같은 방식으로 사용합니다.

 

2300 - 2187 = 113 = 소수 <==== 2300에서 뺏지만 23의 배수가 아님. 따라서 23의 배수가 아님.

2187 - 1900 = 287 <=== 1900을 뺏지만 19의 배수가 아님. 따라서 19의 배수가 아님.

 

즉 일의자리를 조정하는 게 아니라 큰 수를 더하거나 빼서 자릿수를 낮출 수 있다면 천의 자리수를 조정하는 것도 좋은 방법입니다.

 

3) 1)과 2)에 대한 선구안

 

1)은 결국 일의자리 숫자를 0으로 조절해주는 방법이고 2)는 천의 자리 숫자를 0으로 조절해주는 방법이라고 볼 수 있을 것입니다.

1)에서 0을 만드는 방법은 어떤 수를 더해서 0을 만들거나 어떤 수를 빼서 0을 만드는 방법이 있습니다. 비슷하게 2)에서도 어떤 수를 빼서 0을 만들거나 어떤 수에서 빼서 0을 만드는 방법이 있을 것입니다. 이 네 가지 갈림길에 있어서 어느 길이 제일 편할지를 직관적으로 빠르게 판단하는 것이 위의 1),2)를 사용하는 데에 있어 가장 중요한 키포인트가 아닐까 합니다. 예를 들어 4541이라는 숫자가 있고 23의 배수인지 여부를 알고 싶다고 합시다 그렇다면 다음과 같은 세가지 길 정도가 있을 것입니다.

 

4541 + 69  = 4610으로 만든 다음 23의 배수인지 살펴본다

4541 - 161 = 4380으로 만든 다음 23의 배수인지 살펴본다

4600 - 4541 = 59 로 만든 다음 23의 배수인지 살펴본다.

 

결과론적인 얘기처럼 보일 수도 있지만 제가 보기엔 세번째 방법이 제일 효과적으로 보입니다. 하지만 위의 세가지 길을 전부 시도해보지 않더라도 직관적으로 세번째 길이 제일 지름길이라는 것을 파악할 수 있다면  1)과 2)를 능숙하게 사용할 수 있을 겁니다.

 

 

4)위의 과정에서 생기는 찌꺼기들을 잘 기억해두자.

 

4자리 숫자를 소인수분해하기 위해서는 최악의 경우 97까지 약수배수여부를 판별해야 되는데 이는 매우 긴 여정입니다. 하지만 앞의 소수들을 분해하면서 나오는 찌꺼기들을 잘 기억해놨다가 뒤 소수들을 분해하는 데에 있어 속도를 높일 수 있으면 좋겠죠. 아까의 2187을 예로들어 보겠습니다. 2187 - 17 = 2170이 되었고 2170은 17의 배수가 아니니까 17의 배수는 아니라는 결론을 냈었죠. 그런데 2170은 31의 배수이기도 합니다. 그렇다면 2187 = 2170 + 17 인데 한 쪽은 17의 배수이면서 다른 쪽은 17의 배수가 아니고, 또한 한 쪽은 31의 배수이면서 다른 쪽은 31의 배수가 아닙니다. 따라서 2187은 17의 배수가 아닐 뿐만 아니라 31의 배수도 아니다 라는 결론을 낼 수가 있습니다. 소인수분해계의 일타쌍피라고 할 수 있겠네요. 비슷하게 일타쓰리피가 되는 경우도 있습니다. .

1)의 예제에서 마지막 줄을 보면 2187  + 23  = 2210 이 되고 221 = 13*17입니다. 이로부터 2187은 13,17,23 세 숫자 모두 약수로 가지지 않는다는 점을 알 수가 있지요. 이러한 식으로 한 번에 여러 개의 소수에 대해서 판별을 하는 것이 4)의 핵심이고 이러한 아이디어는 5)의 split method로 넘어갑니다.

 

 5) SPLIT METHOD

 

거창하게 Split method 라고 이름붙였지만 별 다를 건 없고요, 위의 일타쌍피가 나오는 경우에 좀 더 포인트를 맞춘 방법입니다. 방법 자체는 매우 간단합니다. 주어진 네자리 숫자를 2개씩 나누면 됩니다. 2187같은 경우엔 21과 87로 나누어주면 되겠네요. 이 때 다음과 같은 얘기를 할 수 있습니다. 양쪽 모두의 약수, 지금 같은 경우엔3, 은 전체 수의 약수가 됩니다. 즉 3의 2187의 약수가 되죠. 반대로 어느 한 쪽만의 약수, 지금 같은 경우엔 7과 29, 는 원래의 숫자의 약수가 될 수 없습니다. 즉 7과 29는 자동으로 약수의 가능성이 있는 소수들에게서 소거되게 됩니다. 일반적으로 2개씩 나눴을때 제법 효과적이지만 사실 1개+3개나 3개+1개로 나눠도 상관은 없습니다. 예를 들어 3221이라는 숫자를 보죠

 

3221 -> 3 + 221 ===> 3과 13과 17로 나누어 떨어지지 않는다 (221 = 13*17)

3221 -> 322 + 1 ===> 7과 23으로 나누어 떨어지지 않는다.  (322 = 7*23*2)

 

Split method 는 위의 방법들과는 달리 주어진 소수에 대해 나누어 떨어지는지를 체크하기 보다는 주어진 숫자로부터 가장 쉽게 체크가 가능한 소수들을 걸러낸다고 보는 게 맞습니다. 따라서 잘 먹히는 숫자가 있고 잘 안먹히는 숫자가 있을 수 있습니다. 3221은 2~13까지의 배수판별법은 다 먹히지 않고 split method 에서 17과 23이 걸러졌으니 19,29,31,37,41,43,47,53 정도에 대해 체크를 해보면 될 것 같습니다. . 1),2),3)을 응용해보면

 

3221 + 19 = 3240 ==> 324 는 18의 제곱 따라서 19의 배수가 안됨

3221 -2900 = 321 ==> 29의 배수 아님

3221 -3100 = 121 ===> 31의 배수 아님

3330 - 3221 = 109 ===> 37의 배수 아님 (37의 경우 37*3=111임을 이용하여 3330같은 숫자를 만들어내어 더하거나 수 있습니다)

3221 - 41 = 3180 ===> 41의 배수 아님 (하지만 남은 3180이 53의 배수이므로 53 역시 약수가 될 수 없다)

3221 - 2820 = 401 ===> 47의 배수 아님

 

따라서 3221은 소수라는 결론을 내릴 수가 있겠죠.

 

뭔가 분량조절에 실패한 것 같은데 다음 포스팅에는 이번에 기술한 방법들을 토대로 예제들에 어떻게 적응하는지 모범답안을 만들어보고자 합니다. 10개 정도의 난수를 생성한 뒤 각각 어떻게 분해를 하였는지와 걸린 시간등을 나타내면 실마리를 잡을 수 있지 않을까 하네요. 그럼 다음 포스팅에서 찾아뵙도록 하겠습니다. 꾸벅

 

 

  • ?
    올드보이즈 2015.02.23 23:14 0/0
    다 읽기전에 첫째줄보고 먼저 남깁니다. 킹스맨 짱잼있어요!
  • ?
    올드보이즈 2015.02.23 23:17 0/0
    아... 잠깐만요... 읽다보니 독거노인님이 숫자를 대하는 logic자체가 일반인과 좀 차이가 많다는... 간극이 느껴집니다... 어렵네요ㅋㅋㅠㅠ

List of Articles
번호 분류 제목 글쓴이 날짜 조회 수
125 식도락 대전 둔산동 모모가든 후기 (★★★) 2 file latio 2015.03.15 1672
124 음악/스포츠 [능력자K] 2015 프리뷰: 우리 팀은 몇 등으로 골인할까 4 쿨럭 2015.03.01 1145
123 결혼/뷰티 [능력자K/뷰티] 내 몸을 보완할 수 있는 옷입기! 1 file ccomziracrac 2015.03.01 1254
122 취미 [능력자K] 투자는 돈을 벌기 위한 것이 아니라.... file kwon4711 2015.02.27 893
121 결혼/뷰티 [능력자K/결혼] EP05_신부의 로망, 드레스 살펴보기 file 새댁 2015.02.27 1264
120 음악/스포츠 [능력자K/음악] 궁금했지만 찾아보지 않았던 "음악"+과학이야기(음과 음색) file 크아홍 2015.02.27 1043
119 여행/사진 KAIST 내부의 사진 찍을만한 곳 (Photozone in KAIST) 4 file latio 2015.02.24 1426
118 음악/스포츠 [능력자K] ‘세이버메트리션’ 감독이 경기를 운영하는 방법 8 쿨럭 2015.02.23 966
117 식도락 [능력자 K] :::박가네 깐쇼새우::: 궁동에 있는 음료수가 100원인 새우 맛집. 3 file 행행나♥ 2015.02.23 1426
116 취미 [능력자K] 워렌 버핏? 세계 2위의 부자, 무엇이 다른 사람과 달랐을까? file kwon4711 2015.02.23 883
115 식도락 노은동 고깃집 file 비정상의장 2015.02.22 152
114 식도락 Premium buffet VESTA 만년동 뷔페 베스타 (Eng/한국어) 1 file 비정상의장 2015.02.21 1525
113 음악/스포츠 [능력자K/음악] 기덕이의 기타이야기 :: 7. 나의 소리를 너에게 더 잘 들려주고 싶어! 픽업이야기!! file 크아홍 2015.02.21 1191
» 취미 [능력자K/소인수분해]3. Main Dish (Part2) 2 독거노인 2015.02.21 972
111 결혼/뷰티 [능력자K/뷰티][피부지키기 립밤&핸드크림편] 립밤과 핸드크림은 무조건 싸고 양 많은걸 사라? 2 file ccomziracrac 2015.02.20 1330
110 결혼/뷰티 [능력자K/뷰티][피부지키기 클렌징편] 남 : 클렌징은 뽀독뽀독해야 씻은거같지! 여 : 이중세안을 꼭 해야 화장이 잘 지워지지! file ccomziracrac 2015.02.18 1082
109 음악/스포츠 [능력자K] FA는 왜 이렇게 비싸졌을까: (2) 공급을 스스로 막는 구단들 file 쿨럭 2015.02.17 873
108 취미 [능력자K] 피터 린치, 주변에서 투자 아이디어를 찾아 볼까요? file kwon4711 2015.02.17 712
107 여행/사진 [능력자K/여행] 2. 현지인집에서 '무료' 숙박 카우치서핑 (Couchsurfing) vs 현지인집을 '임대'하는 에어비앤비 (Airbnb) file 감자 2015.02.16 1162
106 식도락 [능력자K] :::거목::: 숨겨진 전민동의 참치 맛집 2 file 행행나♥ 2015.02.15 1652
Board Pagination 1 ... 2 3 4 5 6 7 8 9 10 11 ... 13
/ 13

포인트랭킹

순위
닉네임
포인트
1
카이**
5699
2
서**
5005
3
봐*
4810
4
동**
3897
5
대학원****
2414