정규 표현식의 조건절
흔히 쓰이는 경우는 아니지만 정규 표현식에도 조건절을 사용할 수 있다. 참고로 모든 정규식 엔진이 조건절을 지원하는 것은 아니다. (javascript 정규식은 조건절을 지원하지 않는다.) 만약 현재 사용하는 편집기나 언어의 정규식 엔진에서 조건절을 지원한다면, 조건절을 사용해서 보다 정교한 매칭을 하는 것이 가능하다. 오늘은 정규표현식의 조건절 사용법에 대해 살펴보도록 하겠다.
더 보기 »정규 표현식의 조건절
Home » Development » Python »
Python
소인수분해 구현하기
소인수분해(prime fatorization)는 어떤 합성수를 소인수의 곱으로 표현하는 것을 의미한다. 12는 합성수이며, 1, 2, 3, 4, 6, 12 로 나눠질 수 있다. 이렇게 어떤 합성 수를 인수의 곱으로 표시하는 방법은 다양하지만, 소수들의 곱으로 표현하는 방법은 (순서를 무시하면) 하나의 방법만 존재한다. 12 = 2 * 2 * 3 으로 표시할 수 있다.
소인수 분해를 사용하면 약수의 개수나 모든 약수의 합을 좀 더 쉽게 계산할 수 있다. 물론 이것은 연필과 종이를 사용할 때에 적용될 것 같은 이야기이다. 컴퓨터를 사용하는 소인수 분해의 경우, “소수인 인수를 정하는 것”에 제법 시간이 소요될 수 있기 때문에 실제로 그리 크지 않은 범위의 수에 대해서는 무식하게 루프를 돌면서 나눠보는 것으로 약수를 세거나 더하는 방법이 더 빠를 수 있다.
더 보기 »소인수분해 구현하기Task, Future, Coroutine
코루틴과 Task에 대한 내용을 발행했었는데 이 부분은 사실 asyncio에 대한 총정리 글에 포함되는 내용이었던 관계로, asyncio 에서 사용되는 세 가지 대기 가능 객체인 Task, Future, Coroutine 의 차이에 대해서 설명하는 내용으로 수정합니다.
asyncio는 비동기 처리를 위해 비동기 코루틴을 만들고 이를 스케줄링하여 실행하는 기능을 중심으로 구성되어 있다. 그런데 관련 함수를 찾아보면 어떤 것은 코루틴, 또 어떤 것은 Task나 Future로 표현하며 섞어 쓰는 것 같기도 해서 혼란스러운 점이 있다. 이 글에서는 코루틴과 asyncio.Task, asyncio.Future 가 각각 어떻게 다른지 살펴보도록 하겠다.
더 보기 »Task, Future, Coroutine사전식 순열의 다음 항 구하기 (파이썬)
참고 : http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order 사전식 순열 생성 함수 어떤 원소들의 순열을 구하는 많은 알고리듬이 있다. 파이썬의 itertools 모듈은 순열, 조합 생성을 하는 permutations(), combinations() 등의 함수를 제공한다. 이 블로그에서도 이 외에 특정한 집합에 대해 N 번째 순열을 구하는 문제도 다뤄본 적이 있다. 오늘은 특정한 수열이 주어졌을 때, 해당 수열의 원소들로 구성되는 사전식 순열에서 다음 번 순열을 구하는 문제를 생각해보자. 사전식 순열이란 특정 집합의 원소들로 이루어진 모든 순열을 정렬하여 순차적으로 나타내는 순열을 말하는 것이다. 예를 들어 [1,2,3,4]는 오름차순으로 정리되어 있으므로 사전식 순열에서는… 더 보기 »사전식 순열의 다음 항 구하기 (파이썬)
셸 정렬 (Shell Sort)
셸 정렬은 정렬 방법의 원리로만 보자면 “분할 증분 정렬”(diminishing incremental sort)이라고도 불리는 방법이며, 굉장히 오래된 정렬 알고리듬 중 하나이다. 이 정렬 방법은 삽입 정렬을 근간으로 하면서 삽입 정렬의 성능을 간단한 아이디어로부터 크게 증가시키는 방법이다.
삽입 정렬은 왼쪽에 있는 원소부터, 그 원소가 이동할 수 있는 ‘가장 왼쪽 자리’에 그 값을 삽입하여 정렬해 나가는 방식이다. 이 때 ‘삽입’을 위한 공간을 만들기 위해 원래자리부터 삽입될 자리 사이의 값들이 하나씩 오른쪽으로 이동해야 한다. 따라서 삽입 정렬은 어떤 원소가 이동해야 할 거리가 크면 클수록 효율이 떨어지며 배열이 반대로 정렬되어 있는 경우가 이에 해당할 것이다.
더 보기 »셸 정렬 (Shell Sort)(파이썬) 고정 속성 클래스를 통해 메모리 최적화하기
기본적으로 모든 파이썬의 객체는 내부에 속성의 이름과 값을 담는 사전 객체를 하나씩 포함한다. 이는 __dict__라는 특별한 속성으로 정해져있다. 따라서 파이썬의 객체는 내부의 사전을 이용하여 속성들을 저장할 수 있고, 사전은 변경가능한(mutable) 키-값 쌍이기 때문에 런타임에 객체 인스턴스에 새로운 속성을 추가하는 것이 가능하다. 더 보기 »(파이썬) 고정 속성 클래스를 통해 메모리 최적화하기
병합정렬
병합정렬은 기초적인 정렬 알고리듬 중에서 널리 알려진 알고리듬 중 하나이며, 대표적인 분정복 알고리듬의 예인 동시에 재귀 알고리듬의 좋은 예이다. 이름에 ‘병합'(merge)이 들어가는 이유는 배열을 2개 혹은 그 이상의 작은 조각으로 나누고 각각의 조각을 정렬한 다음, 각 조각의 앞에서부터 가장 작은 값을 순서대로 골라서 정렬된 결과를 생성하기 때문이다.
원래의 배열을 쪼갠 각각의 조각 역시 똑같은 병합 정렬을 이용해서 정렬하는 재귀적인 동작을 수행한다. 재귀적 알고리듬의 수행 과정을 복잡하고 어렵게 여기는 사람들이 있는데, 입력과 결과에 집중하는 방식으로 바라보면 오히려 더욱 명료하고 간단하다는 것을 알 수 있다.
더 보기 »병합정렬동적계획법
동적 프로그래밍
동적 프로그래밍은 세부 계산으로 나뉘어지는 하나의 큰 문제를 세부 계산 결과를 미리 구해서 저장한 후 큰 계산의 결과를 빠르게 도출해내는 문제해결 기법이다.(이름과는 달리 프로그래밍 테크닉은 아니다.) 흔히 피보나치 수열을 계산할 때 memoization도 동적 프로그래밍의 범주로 볼 수 있다. 더 보기 »동적계획법
날짜 계산 레시피
아주 짧은 기간 사이의 차이를 계산하는 법
Javascript
두 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개 미만의 연속열에 대해서는 나름 나쁘지 않은 성능을 낼 수 있다.
더 보기 »순열생성로직연구