본문 바로가기
반응형

Programming/Algorithm35

Bitwise operation III 비트단위 연산은 알고리즘에서도 많이 사용할 수 있는데, 이제까지 봤던 간단한 형태의 연산에서 이제는 알고리즘이라는 것을 적용해보고자 합니다. 일단 보수라는 것을 살펴보도록 할께요. 보수(Complement)라는 것은 반대되는 수를 말합니다. 우리는 알게모르게 보수라는 개념을 많이 사용하고 있습니다. 34-16 을 계산할 때에도 보수라는 개념을 사용할 수 있습니다. 14-6=8 이라는 개념보다는 보수를 사용하면 뺄셈을 덧셈으로 대치할 수 있으니까요. 14-6=10+4-6=(10-6)+4=4+4=8 이란 개념이죠. 여기서 4는 6에 대한 10의 보수입니다. 이진수에서도 보수를 많이 사용하는데 크게 두가지의 보수를 많이 사용합니다. 1의 보수와 2의 보수입니다. 엄밀하게 이야기한다면 -1의 보수와 0의 보수라.. 2011. 9. 23.
Bitwise operation II 비트단위 연산자를 많이 사용하는 경우는 깃발 표시방법입니다. 이것을 일반적으로 비트 플래그(Bit flag)라고 합니다. 비트 플래그는 윈도즈 프로그램을 하다보면 아주 쉽게 찾아볼 수 있는데, 사용법도 간단해서 쉽게 이용할 수 있습니다. 비트 플래그는 각각의 비트가 1인 경우에는 플래그가 켜진 것으로, 0인 경우에는 플래그가 내려간 것으로 생각합니다. 빨간 깃발과 파란 깃발을 정의해서 해보도록 할께요. 빨간 깃발은 Bit 0 을, 파란 깃발은 Bit 1 을 차지하고 있습니다. 이것을 비트 연산으로 처리한다면, 다음과 같이 할 수 있습니다. 비트 플래그들은 모두 2의 멱승으로 구성됩니다. 추후 패킹에서는 보다 일반적인 방법을 설명하겠지만요. RedFlag = 1, BlueFlag = 2 1) 빨간 깃발 올.. 2011. 9. 22.
Bitwise operation I Bitwise operation 일반적으로 프로그램 하는 사람들이 의외로 비트단위(Bitwise)의 연산을 모르는 경우가 많더군요. 실제 테스트 삼아서 몇 가지 문제를 내면, 못 맞추는 경우가 많아서 의아해했습니다. 실무 영역에서는 많이 사용되고 있는데, 실제 그것을 이용해서 프로그램 짜는 경우는 드물어 보입니다. 우리가 부울 변수 x, y를 입력으로 어떤 함수를 작성한다면, 총 16가지의 함수를 만들 수가 있습니다. 이 함수들은 논리 함수(Logical function)라고 이야기를 하며, 교환법칙이 성립하는 경우는 총 8가지가 존재합니다. 이 8가지 중 2가지는 상수 함수이므로, 실제 우리가 사용하는 논리 함수는 6가지 뿐입니다. 상당히 적죠. 이것을 표로 작성하면 다음과 같습니다. x, y 0, 0.. 2011. 9. 21.
수, 거듭제곱, 로그 우리가 일반적으로 실수를 표현하는데에는 여러 가지 방법이 있겠지만, 가장 일반적인 방법은 소수전개(decimal expansion)를 사용하는 것입니다. 그렇지만 이 소수전개에는 일정량의 반올림 오차를 포함할 수 있습니다. 소수전개는 다음과 같이 표현할 수 있습니다. \[ x = n . d_1 d_2 d_3 … \] 여기서 n은 정수이고, 각 \( d_i \)는 0에서 9 사이의 숫자입니다. 물론 이것은 십진법에서 소수 전개입니다. 8진법이라면 0에서 7사이의 숫자이겠죠. 우리가 알고 있는 많은 실수들은 소수전개할 때 무한하게 이어집니다. 유리수의 경우에도 예외가 아닙니다. 일반적으로 컴퓨터에서는 2진법을 사용하고 있는데, 2진법의 경우 10진법의 유한 소수라 해도 무한 소수가 되는 경우가 많습니다. 0.. 2011. 9. 21.
수, 거듭제곱, 로그 1.2.2. 수, 거듭제곱, 로그 우리가 가장 먼저 접하는 수는 자연수(Natural number)란 것일텐데요. 수학이란 학문이 A→B로 가는 연산이 있다면, 항상 B→A 로 가는 방법을 따지죠. 꼭 반대(역)가 필요한 학문이고, 수학자들은 그래서 영원한 반대주의자들의 집단일 수밖에 없나 봅니다. 모 광고에서 모두다 "예"라고 할 때, "아니오"라고 답하는 사람.. 그러다 왕따 당하기 딱 좋죠. 그래서인지, 최근에 우리나라에서 수학은 왕따 당하는 듯 합니다. 그렇지만 다르게 생각한다면, 수학은 해를 구하는 학문이라는 것이죠. A→B 로 가는 연산이 있다면 어떤 경우에 해당 연산 결과가 B가 될 것인가죠. 그렇게 하다보니 그 해가 정말 맞는 것인지, 그리고 오직 그 해만 존재하는지를 따지게 된 것이라고 .. 2011. 9. 21.
Induction II 수학적 귀납법이 증명을 하는데 아주 유용한 도구라는 것은 어느정도 수학을 했던 사람이라면 잘 알고 있는 사실입니다. 실제 수학적 귀납법을 익히는 것은 어렵지 않지만, 많은 분들이 수학 증명이라는 말만 나오면 일단 겁부터 내는 듯합니다. 수학적 귀납법은 패턴이 정해져 있는 증명으로 몇 번 하면 수학에 재능이 없다고 하는 분들도 그다지 어렵지 않게 익힐 수가 있습니다. 물론 수식 계산에 자신이 없다면 어쩔 수 없겠지만요. 옛날 그리스 사람인 니코마소스(Nicomachus)의 정리를 보도록 하겠습니다. 세제곱의 수가 홀수들의 합으로 표시할 수 있다는 것이죠. \[ \begin{align} 1^3 &= 1 \\ 2^3 &= 3+5 \\ 3^3 &= 7+9+11 \\ 4^3 &= 13+15+17+19 \\ ..... 2011. 9. 20.
728x90