1. Question 덕 타이핑이란 OOP에서 사용하는 개념 중 하나이다. 동적 언어 (Dynamic Langauge; 동적 타입)에서 사용하는 개념으로 클래스를 명명하는 것으로 타입을 결정하는 것이 아니라, 객체의 변수 및 메소드의 집합이 객체의 타입을 정하는 것을 의미한다. 어려운가? 일단 덕 타이핑에 대해 한 문장으로 표현한 말을 보도록 하자. "만약 어떤 새가 오리처럼 걷고, 헤엄치고, 꽥꽥거리는 소리를 낸다면 나는 그 새를 오리라고 부를 것이다." 이 말은 OOP에서 클래스와 인터페이스로 구분되는 기존 패러다임에서 벗어나, 객체를 미리 판단하지 않고 변수와 메소드가 사용되는 때에 객체를 판단하겠다는 의미이다. 덕 타이핑을 통해 개발자는 함수를 구현할 때 마치 제네릭이 기본인 것 같은 느낌을 받는..

1. Introduction 이번 포스팅에서는 호제법보다 빠른 최대공약수 식별 알고리즘을 소개한다. 스테인 알고리즘 (Stein's algorithm) 이라고도 불리는 알고리즘이며, 기존의 호제법보다 60%의 효율개선을 보이는 획기적인 알고리즘이다. 는 그렇게 대단한 알고리즘이 아니다... 스테인 알고리즘은 이진 GCD 알고리즘이라고도 불리며, 호제법의 이진버전이라고 생각하면된다. 호제법에서 각 루틴마다. $A \bmod B (A>B)$ 를 수행하지만, 스테인 알고리즘에서는 A와 B를 모두 반으로 나눈다. 2. Approach 다음과 같은 규칙을 따른다. 두 수가 짝수일 때는 2로 나눈다. a 변수를 1증가시킨다. 한 수만 짝수일 때는 그 수를 2로 나눈다. 두 수가 홀수일 때는 큰 수에서 작은 수를 뺀..

1. Introduction 소수는 1과 자기 자신외에는 약수를 가지지 않는 수를 의미한다. 소수를 판별하는 가장 간단한 방법은 2부터 자기자신까지의 수 (효율적으로는 $\sqrt {n}$까지)를 차례로 나눠보는 것이다. 하지만 대량의 소수를 얻어야 할 경우에도 위와 같은 방법을 쓰는 것이 최선일까? 이번 포스팅에서는 대량의 소수를 효율적으로 얻는 에라토스테네스의 체라는 방법을 소개한다. 2. Approach 에라토스테네스의 체의 기본적인 아이디어는 단일 소수판별법처럼 n에 대한 약수로 접근하는 것이 아니라, n의 배수를 기반으로 접근한다. 먼저 1은 소수가 아니므로 제외한다. 2부터 시작해서 소수를 찾으면서 합성수를 제거해 나간다. 2의 배수들은 모두 2를 약수로 가지므로 제외한다. 이제 다음으로 제외..

본격적으로 들어가기 전에 적당히 알고 가야할 것 들과 배경지식에 대해 간략하게 설명. 소프트웨어란? - 쉽게 말해, 문서화된 컴퓨터 프로그램 Software Product - 일반적인 대중을 대상으로 만들어질 수도 있고 (Generic) - 특정분야의 전문가를 대상으로 만들어질 수 있음 (Custom) Software Characteristics (SW 개발이 힘든 이유) - 소프트웨어는 눈에 보이지 않음 (invisibility) - 복잡도가 줄어들지 않음 (complexity) - 완성된 이후에도 계속 진화함 (changeability) ... Software Engineering : 소프트웨어의 개발, 운영, 유지보수, 폐기에 대한 체계적인 접근법 (IEEE의 정의) 전체 개발 비용의 60~80%는..

1. Introduction $a^b \bmod m$형태를 계산하는 방법은 여기에 포스팅했다. 이번 포스팅에서는 이것을 돌리기 위한 코드를 최적화하는 방법을 소개한다. 2. Approach $a^b$의 형태의 자연수에 대한 나머지 계산에 대한 방법들을 소개한다. 2.1 일반적인 방법 def powMod1(base, index, mod): r = 1 for i in range(index): r *= base r %= mod return r 시간복잡도가 $O(b)$이다. r이 $a^b$까지 커지기 때문에 overflow일어나기 매우 쉽다. 2.2 개선된 방법 def powMod2(base, index, mod): if index == 1: return base if index % 2 == 0: r = pow..

1. Introduction 이 포스는 딥 러닝을 이해하기 위한 다음과 같은 배경지식을 소개한다. 딥 러닝에서 사용하는 데이터 셋의 형태 (Dataset) 가정 (Hypothesis) 비용함수 (or 손실함수, Cost Function or Loss Function) 2. Explanation 2.1 Dataset 머신러닝에서 사용하느 데이터 셋은 입력 ($X$)과 출력 ($Y$)으로 이루어져 있다. 입력은 같은 종류 특징을 가지는 원소들의 리스트이다. $X$는 $x_1, x_2, ..., x_n$과 같이 표현되고 각각의 원소들은 특징에 대한 값을 가지고 있다. 예를 들어, 다음과 같이 원소들이 표현된다고 하자. $$x_1 = [1, 2, 3]$$ $$x_2 = [2, 5, 8]$$ $$x_3 = [3,..

1. Introduction 텐서(Tensor)는 연산을 용이하게 하기 위해, 벡터를 모아둔 단위라고 정의하기는 하지만, 컴퓨터 공학에서는 사실상 3차원 행렬로 통용된다. 물론, 3차원 행렬, 2차원 텐서라고 사용되기도 하지만 사용자가 그 의미를 모르는 경우는 거의 없다. 이런 단위는 다음과 같이 정리된다. 0차원 스칼라 (Scalar): 정수 1차원 벡터 (Vector): 리스트 2차원 행렬 (Maxtrix): 2차원 행렬 3차원 텐서 (Tensor): 3차원 행렬 일반적으로 2차원, 3차원 행렬을 가지고 딥러닝을 수행할 때, 이 행렬의 row 크기를 batch size라고 일반적으로 부른다. 2. Practice 2.1 Basic Pytorch에서 텐서를 다루는 방법은 Numpy의 array와 완전히..

1. Introduction Pytorch는 페이스북이 구글의 Tensorflow에 맞서기 위해 개발한 딥러닝 프레임워크이다. 개발 과정에 엔비디아가 참여해서 그런지, 크게 밀어주고 있다고 한다. Pytorch는 딥러닝 프레임워크의 후발 주자로서 다음과 같은 주요 특징을 가지고 있다. Python에 종속적: 이름부터 Pytorch인 만큼, 파이썬에 종속적인 프레임워크다. 파이썬 개념을 Pytorch는 그대로 지원하기 때문에 더 빠르고 효율적이다. Numpy 기반: 요즘의 딥러닝 환경에서 표준이 되는 Numpy를 기반으로 작동한다. 이건 지금에 와서는 당연한 수순. Autograd: 오류를 반영하기 위한 역전파를 backward 메서드로 한번에 실행한다. 이것도 요즘에 와서는 표준이기 때문에 당연히 지원한..