기본적으로 모든 파이썬의 객체는 내부에 속성의 이름과 값을 담는 사전 객체를 하나씩 포함한다. 이는 __dict__라는 특별한 속성으로 정해져있다. 따라서 파이썬의 객체는 내부의 사전을 이용하여 속성들을 저장할 수 있고, 사전은 변경가능한(mutable) 키-값 쌍이기 때문에 런타임에 객체 인스턴스에 새로운 속성을 추가하는 것이 가능하다. 더 보기 »(파이썬) 고정 속성 클래스를 통해 메모리 최적화하기
병합정렬은 기초적인 정렬 알고리듬 중에서 널리 알려진 알고리듬 중 하나이며, 대표적인 분정복 알고리듬의 예인 동시에 재귀 알고리듬의 좋은 예이다. 이름에 ‘병합'(merge)이 들어가는 이유는 배열을 2개 혹은 그 이상의 작은 조각으로 나누고 각각의 조각을 정렬한 다음, 각 조각의 앞에서부터 가장 작은 값을 순서대로 골라서 정렬된 결과를 생성하기 때문이다.
원래의 배열을 쪼갠 각각의 조각 역시 똑같은 병합 정렬을 이용해서 정렬하는 재귀적인 동작을 수행한다. 재귀적 알고리듬의 수행 과정을 복잡하고 어렵게 여기는 사람들이 있는데, 입력과 결과에 집중하는 방식으로 바라보면 오히려 더욱 명료하고 간단하다는 것을 알 수 있다.
더 보기 »병합정렬동적 프로그래밍은 세부 계산으로 나뉘어지는 하나의 큰 문제를 세부 계산 결과를 미리 구해서 저장한 후 큰 계산의 결과를 빠르게 도출해내는 문제해결 기법이다.(이름과는 달리 프로그래밍 테크닉은 아니다.) 흔히 피보나치 수열을 계산할 때 memoization도 동적 프로그래밍의 범주로 볼 수 있다. 더 보기 »동적계획법
두 Date 객체를 빼면 그 사이의 밀리세컨드 값이 나온다.
var start = new Date();
/* perform some time-taking work... */
var end = new Date();
console.log(end - start);
사실 이 포스팅은 순열을 만드는 방법에 대한 매우 비효율적인 접근에 대한 글입니다. 효율적인 순열/조합 생성 코드는 이 글을 참고하세요.
순열을 만드는 가장 간단한 방법으로는 특정 원소를 하나씩 뺀 후 배열의 나머지를 순열한 각 결과에 빼냈던 원소를 앞에 붙여준 결과를 모으는 방법이 있다. 대략의 코드는 다음과 같다.
def rec_perm(iterable):
if len(iterable) == 1:
return [list(iterable)]
result = []
for i in range(len(iterable)):
head = iterable[i]
tail = iterable[:i] + iterable[i+1:]
result += [[head] + x for x in rec_perm(tail)]
return result
이 알고리듬의 가장 큰 문제는 한 번에 모든 순열을 다 생성해서 그 리스트를 만환한다는 말이다. 만약 원소가 100개라면?1 메모리 부족으로 컴퓨터가 뻗을 수 있다. 물론 10개 미만의 연속열에 대해서는 나름 나쁘지 않은 성능을 낼 수 있다.
더 보기 »순열생성로직연구서브라임텍스트3에서 작성하던 내용을 개인적으로 사용하는 위키(로컬에서 돌리고 있음)에 전송하는 기능을 서브라임 텍스트 플러그인으로 구현하고, 그 과정을 기록한다.
sublime 패키지가 필요하다. sublime_plugin 패키지에 정의되어 있다. 커스텀 플러그인은 이 클래스를 상속받아 작성하게 된다. self.view 속성을 통해서 접근할 수 있다.애플은 Swift가 파이썬보다 몇 십배 빠르다고 주장하고 있는데, 실질적으로는 파이썬이 더 빠른 것 같이 느껴지는 (심지어 pypy도 아니고) 경우가 너무나 많다. 물론 “어떤 언어가 더 빠르냐”는 질문만큼 바보같은 것도 없긴한데, 개인적으로는 애플이 말하는 것과 반대인 것 같은 체감이 많아서 한 번 확인해보았다. 더 보기 »Swift는 정말 파이썬보다 빠를까?
숫자 924234656를 컴마가 들어가는 형태로 포맷팅하는 함수를 작성하려다가, 정규식으로 할 수 있음을 깨달았다. 더 보기 »정규식으로 숫자에 컴마 넣기
파이썬 기본 모듈인 itertools는 리스트와 같은 반복 가능한 객체에 대한 여러 연산을 위한 함수를 제공하는데, 특정한 원소들로 만들 수 있는 순열이나 조합을 구하는 함수들도 이 모듈에 포함되어 있다. 특정한 원소를 가지고 만들 수 있는 모든 순열은 itertools.permutations() 함수로, 모든 조합은 itertools.combinations() 함수로 만들 수 있다. 그 외에 중복을 포함하는 조합등을 생성하는 함수가 제공된다.
아주아주 예전에는 순열/조합을 생성하는 함수를 구현하는 것이 간단한 작업이 아니었는데, 제너레이터에서 다른 제너레이터로 결과 생성을 위임하는 yield from 문법이 생긴 이후에는 이를 아주 간단히 구현할 수가 있게 되었다. 그래서 오늘은 제너레이터를 이용해서 주어진 리스트나 튜플에서 순열 및 조합을 생성하는 제너레이터를 만드는 방법을 소개하고자 한다.
퀵소트는 정렬과 관련된 내용을 다룰 때 빠지지 않고 등장하는 알고리듬이다. 제자리 정렬로 구현할 수 있는 알고리듬 중에서는 가장 빠른 것으로 알려져 있다. (그래서 이름도 퀵 정렬) 평균적인 성능은 O(nlogn)이 나온다. 퀵소트의 원리는 간단히 말해서 데이터 중에서 기준이 되는 임의의 값 하나를 정하고 이를 보통 pivot이라 한다. 이제 다른 데이터들을 피봇과 비교하여 그보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 옮겨준다.
더 보기 »퀵소트에 대해 알아보자