본문 바로가기

(비정기) Mr.K's Post/Weekly paper

Matrix : Part 5 안녕하십니까 Mr. K입니다 어제 저녁 내내 친구와 놀고 늦게 들어온 덕분에 포스팅하다가 피로를 이기지 못하고 자고 씁니다 -_-; 시작할게요! 여러분은 다음과 같은 식을 보면 □를 구할 수 있습니까? [그림 1] 아마 중학교를 졸업한 수준의 학생들이라면 대부분 답을 구할 수 있을 것입니다 ( 답은 1이죠 ) 이제 위 그림의 □를 x로 바꿔보겠습니다 [그림 2] 이제 이것을 방정식이라고 부를 수 있을 것입니다 ( 사실 그림1, 2 모두 방정식이지만, 그림1과 같은 식을 통해서 배울 때는 방정식이라는 말을 보지 못했을 수도 있으므로 ) 미지수 x의 차수가 1이므로 이것은 일차방정식입니다 이런 일차방정식이 두 개 이상 묶여있는 경우엔 그것을 연립일차방정식( 이하 연립방정식이라고 하겠습니다 )라고 합니다 ( .. 더보기
Matrix : Part 4 안녕하십니까 Mr. K입니다 여기에 글을 쓰는것도 오랜만이군요 -_-; 원래 어제 올렸어야 되는데 수정된 ubint를 올려놓고 딴짓좀 하다보니 잊어버렸지 뭡니까; 그래서 공지를 띄우고 며칠 더 있다 올릴까, 지금 올릴까 하다가 지금 올립니다 -_-; 이번 포스트는 역행렬에 대해서 얘기해보겠습니다 이전까지 우리는 행렬의 기본적인 정의, 행렬간 덧셈·뺄셈의 정의, 행렬간 곱셈의 정의 등을 배웠습니다 행렬은 나눗셈의 개념은 없지만, 역행렬이라는 것이 있습니다 실수를 다룰 때, 다음과 같은 관계에서 a가 0이 아니라면 x, 즉 a의 역수를 생각해볼 수 있습니다 마찬가지로 행렬에서도, 다음과 같은 관계를 만족하는 행렬 A에 대해서는 X, 즉 A의 역행렬을 생각해볼 수 있습니다 [그림 2] A와 X 사이에 교환법칙.. 더보기
[Bigfloat 지원사격?] 자연수부터 해봅시다 :) ※ 발행할까 말까 고민좀 했는데, 내 정기 포스트가 아니라 일단 발행에 체크 안함 - to 관리자 안녕하십니까 Mr. K입니다 원래 오늘 제 포스트( 행렬 )를 끄적이기로 했던 날입니다만 환타님이 Bigfloat 만드신 것을 보고서 왠지 불타올라서(?) 개인적인 의견도 끄적이고 구현까지 해버렸습니다 -_-; 일단 저는 Talk에 끄적여놓았듯이 Bigfloat을 만들기 위한 기반은 Bigint라는 생각이 들고, Bigint를 만들기 위한 기반은 Unsigned Bigint라는 생각이 들어서 자연수의 역할을 하게 될 Unsigned Big INTeger를 먼저 만들어보았습니다 클래스의 정의부분입니다 #ifndef UBINT_H #define UBINT_H #include using std::ostream; .. 더보기
Matrix : Part 3 안녕하십니까 Mr. K입니다 지난 포스트에서도 언급했듯이 사정이 좀 생겨서 군대 안가고 약 1년정도 휴학할 예정이나, 그동안 돈을 벌어야 하는 관계로 Matrix의 포스팅이 끝나면 한동안 주간포스트를 접어야 할수도 있겠습니다 오늘 다룰 내용은 행렬의 연산, 그중에서도 곱셈에 대해 다루고자 합니다 영희의 어머니는 할머니의 생신을 맞아 송편과 인절미를 만들려고 한다. 송편과 인절미를 각각 1000g씩 만드는 데 필요한 재료의 양과 각 재료의 1g당 가격은 다음 표와 같다. 아래의 물음에 … 위의 글상자에서 송편과 인절미를 만드는 데 필요한 비용을 구하는 식은 송편 : 650×2 + 300×3 + 50×1 = 2250 (원) 인절미 : 780×2 + 200×3 + 20×1 = 2180 (원) 임을 알아보았습니.. 더보기
Matrix : Part 2 안녕하세요 Mr. K입니다 사정이 좀 생겨서 아마 matrix의 포스팅이 끝나고나면 한동안 주간 포스트를 접어야 할지도 모르겠습니다; (하지만 문제는 시간 나는대로 풀어서 올릴 예정) 오늘 다룰 내용은 행렬의 연산입니다 다음 표는 영희네 옷가게에서 어제까지 보유한 물량과 오늘 구입한 물량을 나타낸 것이다. 이 표를 보고 … 위의 글상자에서 어제까지 영희네 옷가게에서 보유한 물량과 오늘 구입한 물량을 각각 아래와 같이 행렬로 나타내기로 합니다 그러면 영희네 옷가게에서 현재 보유하고 있는 각 옷의 물량은 아래 표와 같습니다 이 때, 이 표의 성분은 A와 B의 대응하는 성분의 합이고, 이것을 행렬로 나타내면 다음과 같습니다 이처럼 행렬 A와 행렬 B의 대응하는 성분의 합을 성분으로 갖는 행렬을 A + B로 나.. 더보기
Matrix : Part 1 안녕하십니까 Mr. K입니다 어제 그제 노느라 제대로 포스팅을 못했습니다 -_-; 오늘도 간이 나빠져서 입원하신 부친 병문안 다녀오는 일이 있어서 그냥 다음주로 미룰까 하다가 하루종일 병원에 있는 것도 아니고 해서 늦게나마 포스팅합니다/ 지난번 포스트에도 Matrix에 대한 내용을 적어놓고 왜 또 이번에 Matrix를 다루는지 의아해 하실 분들이 있겠습니다만 (있나?) 이 팀블로그에서 하는 일이 주간 포스트만 있는 것이 아니지요, 바로 알고리즘 대회 기출문제.. 라고 생각되는 것들을 임의로 골라서 같이 풀어보고 토론(..)하는 일도 하고 있습니다만 번역되는 문제들을 보면 (혹은 개인적으로 문제 리스트를 훑어볼 때에도) 종종 문제 자체에서 Matrix를 이용하거나 Matrix를 이용해서 풀면 쉬울듯한, 그.. 더보기
Matrix Decomposition 안녕하십니까 Mr. K입니다 어쩌다보니 처음같지 않게 포스팅이 뜸해지는군요 -_-; 본 내용은 PKU 3685 : Matrix 와는 전혀 관계없는 내용이므로 해당 내용을 보시고자 하는 분들은 뒤로가기를 눌러주세요 오늘 소개할 내용은 행렬 분해법입니다 그 중에서도 LU-분해법(LU-Decomposition)에 대해서 소개하도록 하겠습니다 예전에 소개했던 Interpolation : part 1 에서 N차 다항식을 구하기 위해 N+1개의 점들을 행렬의 원소로 갖는 Vandermonde matrix를 사용했었습니다 그래서 아래와 같은 꼴의 문제로 바뀌게 되었지요 그러나 당시 포스트에도 언급했듯이, 구하고자 하는 다항식의 차수가 커지면 그만큼 오래걸린다는 단점이 존재했습니다 이번에 소개할 LU-분해법은 그 시간.. 더보기
무리수 √2의 값을 구해보자! : Part 5 안녕하십니까 Mr. K입니다 오랜만의 포스팅이군요 -_-; 지난주에 예고했던 것 처럼 √2에 대한 얘기를 하나 끄적이도록 하겠습니다 아, 그 전에 이번 포스트의 경우 도함수에 대한 얘기가 있으니, √2를 구하는 방법을 하나만 알아도 된다 하시는 분들은 패스하셔도 됩니다 Fixed Point Iteration Most of the techniques we will discuss are iterative in nature and the first one is called the fixed point iteration scheme. Instead of looking for a zero of the function f(x), it determines a fixed point of an equivalent equ.. 더보기
Interpolation : Part 3 안녕하십니까 Mr. K입니다 목요일에 글을 쓰기 시작하는것도 오랜만이군요 과연 목요일이 끝나기 전에 글을 올릴 수 있느냐가 문제지만 -_-; 지난 두 포스트에 이어서 계속 같은 데이터( 3개의 점: (1, 2), (2, 3), (3, 6) )를 가지고 얘기해보겠습니다 …. We remark that various conclusions can be drawn from the data by using the forward differences; for instance whether it was generated using a polynomial (in which case the differences truncate). We now construct a polynomial which goes through a.. 더보기
Interpolation : Part 2 안녕하십니까 Mr. K입니다 지난주에 한회 쉬었음에도 제 날짜에 포스팅을 하지 못해 뭐라 할 말이 없습니다 -_-; 지난 포스트(Interpolation : Part 1)에 이어서 같은 데이터( 3개의 점: (1, 2), (2, 3), (3, 6) )를 가지고 얘기해보도록 하겠습니다 이번에 얘기할 주제는 Newton Forward Differences 입니다 We shall now discuss the operation of fitting an Nth order polynomial through N + 1 points and remark again this will yield a unique answer. We consider the set of data points: (x_0, f_0), (x_1, f.. 더보기
Interpolation : Part 1 안녕하십니까 Mr. K입니다 2주 전까지 쓴 소재는 적당히 접기로 결정을 내린 터라, 다른 소재를 찾아야 하는데 소재가 없어서 늦게 찾았다기보단 그저 학교일이 바쁘네요 -_-; 그리고, 이전 소재에서 제목 앞에 붙여놓았던 R.A.M. 이 별로 의미가 없는 것 같아서 (R.A.M. = Realizable Abstract Matter or Material 이었으나, 이런걸 달아놓지 않더라도 수학적인 것에 대해 얘기를 하다보면 무의식중에 무한대나 무리수 등등, 컴퓨터에서 똑같이 따라하지만 실수에서 되는 계산이 깔끔하게 떨어지지 않는(예외는 있습니다, Maple이라는 프로그램은 √2를 입력하고 엔터를 치면 결과값에 그대로 √2가 출력이 됩니다) 경우가 많기 때문에 그냥 그때그때 해당하는 주제가 나오면 언급하기로.. 더보기
R.A.M. #1. 무리수 √2의 값을 구해보자! : Stage 4 부제(?) : 글쓰는건 목요일에 시작했다는 -_-; 안녕하십니까 많이 늦었습니다// 원래 저녁먹고 한숨 잤다가 깨서 포스트를 미루는 공지를 썼었는데 잠이 다 깨고 나니 오늘 안에도 쓸 수 있을 것 같아(& 댓글 달린것도 없어서) 올렸던 공지를 내렸습니다 ..만; 결국 자정을 넘기고 마네요 -_-; Bisection Method(RAM 1-1)에서 Dlbo군이 댓글로 Newton's Method(이하 뉴턴메소드)를 언급해서 그것에 대해 쓸까 했지만 그건 도함수가 필요하니 환타군이 쓰기엔 아직 좀 무리가 있을 수 있지요; 또, 도함수를 쉽게 구할 수 없는 함수도 많습니다 -_-; 그리고 뉴턴메소드의 경우, 함수가 잘생겼다면 상관없지만 함수가 못생겼다면, 초기값(x0)을 실근의 추정값에서 멀리 잡을수록 발산할.. 더보기
[Let's Play!] 1. Coinproblem 부제 : 나라면 10개를 다 갖겠어! (?) 어느 날, 조금 수상해보이는 남자가 당신에게 금화 10개를 주면서 "이 중에 가짜가 하나 있는데, 양팔저울을 3번만 사용해서, 가짜가 어느 것인지 그리고 가짜의 무게가 다른 것들에 비해 어떠한지 맞추면 9개의 진짜를 드리겠습니다" -라고 말했다면, 당신은 이 문제를 어떻게 풀어낼 것인가? (이런 스토리가 있어야 왠지 당위성이 있을 것 같아서.. -_-;) 안녕하십니까 Mr. K입니다 다음주가 시험이라 딱히 자료수집같은 것을 하지 못한 관계로, 이번 주는 '놀이'로 대체합니다 같은 이유(시험)로, 다음주 목요일에는 포스팅을 하지 못할 것 같습니다 이 문제는 제가 고등학교 다니던 때, 친구한테 물음을 받아서 하루이틀정도 머리를 굴리게 만들었던 문제입니다 작년에 C.. 더보기
R.A.M. #1. 무리수 √2의 값을 구해보자! : Stage 3 부제 : 글올리기도 바쁜데 부제는 무슨 부제 ㅋㅋㅋ Continued Fractions … from Section 2.5, (√5 + 1)/2 and √2 can be written as continued fractions. In fact, this is true for any real number. But to begin with, there are a number of types of continued fractions. We will briefly study simple continued fractions, that is, expressions of the type denoted by , where x0 ∈ Z and xn ∈ N ∪ {0} for n ∈ N. If xn = 0 for all n >.. 더보기
R.A.M. #1. 무리수 √2의 값을 구해보자! : Stage 2 부제 : IE 7.0으로 바꿨는데 이미지 업로드가 안되네. 제곱근의 계산법 피타고라스에 의해 알려진 무리수 √2는 1.41421356…이다. 이 숫자를 쉽게 암기하는 방법은 각자의 요령에 달려 있다. 그런데 이 숫자가 어떻게 나오게 되었을까? 여기에서 제곱근의 계산방법을 알아보기로 하자. 0. 나눗셈의 그것과 비슷하도록 제곱근 기호를 길게 그리고 그 안에 2를 쓴다. 1. 제곱해서 2가 되거나, 모자르지만 그에 가깝게 되는 최대의 수는 1. 그러므로 B1과 C1(그림에 적어놓진 않았지만 몫부분에 해당함, 이하 Ck)에 1을 넣고 B1과 C1을 곱한 결과를 A2에 쓴다. 2. (A1-A2)는 1. 따라서 A3에 1을 넣고 00을 내려오게 한다. 3. B1 밑의 B2에 C1과 같은 1을 넣고 B1과 B2를 .. 더보기
R.A.M. #1. 무리수 √2의 값을 구해보자! : Stage 1 부제 : 미정 Location of Roots Theorem Let I = [a, b] and let f : I → R be continuous on I. If f(a) 0 > f(b), then there exists a number c ∈ (a, b) such that f(c) = 0. (위 내용은 INTRODUCTION TO REAL ANALYSIS 3/e에서 일부 발췌했음을 알려드립니다) 안녕하십니까 Mr. K입니다 지난 주까지 무사히(?) '재귀 vs. 반복'의 포스팅을 끝내고 새로운 주제를 가지고 돌아왔습니다 포스팅 계획서에 언급해두었던 '무한의 범주에 있는 것을 유한하게 구현'하는 것을 하려고 합니다 그 첫 대상은 '무리수'가 되겠습니다 무리수라는.. 더보기
Recursion vs. Iteration : Round 3 부제 : 말이나 못하면 밉지나 않지. (?) 자, 이번에는 "Round 1"에서의 피보나치 수열을 나름 "개량된" 재귀함수로 구현해보도록 하겠습니다 ... // #include 외 unsigned improvedRecursion( unsigned, unsigned * ); void main() { ... // 선언부 unsigned count; unsigned *fibonacciSequence; cout > count; fibonacciSequence = ( unsigned * )calloc( 1+count, sizeof( unsigned ) ); ... // 시간 측정 시작 improvedRecursion( count, fibonacciSequence ); ... // 시간 측정 끝 free( fibo.. 더보기
Recursion vs. Iteration : Round 2 부제 : 컴퓨터조차 세상의 끝을 보기가 쉽지 않아. 하노이 탑 19세기경 유럽에서는 "창세기부터 지금까지 브라마 사원에서 계속되고 있다"는 선전용 문구와 함께 유명했던 "하노이 탑"이라는 게임이 있었다. 전설에 의하면 아직도 계속되고 있다는 이 게임은 창세기에 그 사원의 사제가 하나님으로부터 다이아몬드로 된 세 개의 말뚝에 꽂혀 있는 구리 제단을 받았는데, 첫 번째 말뚝에는 금으로 된 64개의 원반이 쌓여 있었고, 각 원반은 바로 밑에 있는 원반보다 조금씩 작았다. 사제는 모든 원반을 두 번째 말뚝을 이용하여 세 번째 말뚝에 옮기는 임무를 부여 받았는데, 다음과 같은 규칙이 있었다. 1. 원반은 한번에 하나씩만 옮겨야 한다. 결국 가장 작은 맨 위의 원반만 옮길 수 있다. 2. 위에 놓인 원반은 아래의 .. 더보기
Recursion vs. Iteration : Round 1 부제 : 그대, 피보나치 수열이라고 들어보았는가? Fibonacci Numbers Consider the following sequence of numbers, which begins with two 1's and where each successive term is equal to the sum of the preceding pair of terms. These numbers, called Fibonacci numbers, are arranged in the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... . If F1 = 1, F2 = 1, F3 = 2, F4 = 3, and so on, then this sequence can b.. 더보기
포스팅 계획서 안녕하세요 Mr.K입니다// 수학과 소속이고, 프로그래밍을 배우는 것도 이제 곧 3학기째에 들어갑니다만 어쩌다보니 스카웃되어 이렇게 팀블로그의 초석을 다지는 데 한몫 하게 되었습니다 제가 앞으로 포스팅 할 분야는 딱히 어느것이다- 라고 말하긴 그렇고, 수학적으로 정의되어있는 것을 프로그래밍으로 구현해본다거나 '무한'의 범주에 들어있는 것들을 어느정도 끌어내려서 '유한'하게 구현해본다거나 기타 등등, 책을 찾아보고 프로그래밍과 연관시킬 수 있는 것이라 생각되면 전부 시도해볼 생각입니다 그리고 PKU나 UVa에 대해 미리 얘기를 해두자면.. 저같은 경우 '얼마나 빠른가'는 제쳐두고 '얼마나 정확한가'에 신경을 쓰는 편이기 때문에 문제에서 요구하는 답을 내는 것에 집중할 생각입니다 그때문에 전체적인 코드의 형.. 더보기

티스토리툴바