콘텐츠로 건너뛰기
Home » Development » Python » Page 15

Python

데코레이터를 통한 memoization

파이썬 데코레이터를 통한 memoization

피보나치 수열은 재귀 알고리듬의 대표적인 문제인데, 간단히 memoization을 통해서 성능을 개선하는 방법을 찾아보자. 테스트는 파이썬 3.4에서 진행했다.

def fib(n):
    if n in (1, 2):
        return 1
    return fib(n - 1) + fib(n - 2)

위 코드는 피보나치 수열의 정의를 그대로 따르는 코드이다. 이 코드를 사용하여 피보나치 수열의 64번째 항을 구하면… 얼마나 걸릴지는 모르겠다. 실행해놓고 이 글을 다 쓸 때까지도 결과가 나오지 않았다. fib(64)는 재귀 호출을 18,446,744,073,709,551,615 회나 해야하기 때문이다. (\( 2^{64} – 1 \)번을 계산해야 한다) 36번째 항을 계산하는데만해도 14초가 넘게 걸렸다. 이 알고리듬은 매우 간결하고 깔끔한 코드로 보이지만, 불필요한 중복 계산을 너무 많이 한다. 64번째 항을 구하기 위해서는 63번째와 62번째 항을 구하는데 그럼 62번째는 2번 계산된다. 즉 1에 가까워질수록 중복 계산횟수가 기하급수적으로 늘어나는 것이다.
더 보기 »데코레이터를 통한 memoization

Parse Tree

이진트리 애플리케이션

파스 트리

트리 데이터 구조를 구현하는 방법을 알게 되면 이제 이 자료구조를 사용하여 실제 문제를 풀 수 있는 사용처에 대해서 살펴보자. 트리는 부분 요소로 나눠지는 데이터를 표현하기에 좋으므로 파싱과 관련된 작업에 많이 사용된다. 이럴 때 사용되는 트리를 파스 트리(Parse Tree)라 하는데, 파스 트리는 실제 문장이나 수학식을 표현하는데 사용될 수 있다.
http://interactivepython.org/runestone/static/pythonds/_images/nlParse.png
다음은 간단한 수학식을 트리로 표현한 것이다.

             *
           /   \
          +     -
         / \   / \
        7   3  5  2
> ( 7 + 3) * ( 5 - 2 )

더 보기 »Parse Tree

웹서버란 무엇인가

What is a web server?

웹서버는 많은 웹개발자들에게는 블랙박스나 마법의 상자 같은 물건인데, 실상 그것은 하나의 프로그램이다. 이 프로그램은 80번 포트에 소켓을 열고 이 포트를 통해 들어오는 HTTP 요청을 받아, 다시 응답을 보내주는 프로그램이다. 요즘의 웹서버들은 이런 기본적인 기능에 덧붙여 여러가지 부가기능들을 제공한다. 하지만 이러한 기능들은 모두 부가적인 것이며, 웹 서버의 본질은 HTTP 응답을 내보배는 것이다. 만약 에코서버를 작성해본 경험이 있다면 웹서버 역시 이러한 에코 서버와 크게 다르지 않다. 단지 들어오는 입력에 대해 좀 더 많은 손질을 해서 내보내는 것일 뿐이다. 더 보기 »웹서버란 무엇인가

우선순위 큐 혹은 최소/최대힙

우선순위 큐 (priority queue)는 큐와 비슷하게 뒤쪽으로 원소를 삽입하고 앞쪽으로 꺼낼 수 있는 자료 구조이다. 하지만 각 원소는 내부적으로 논리적인 우선순위 값을 가지고 있고, 따라서 선입선출(FIFO)의 규칙에 의해서 나오는 것이 아니라, 큐 내부에서는 높은 우선순위를 갖는 원소가 앞쪽으로 오게 된다. 즉, 큐와 마찬가지로 원소를 꺼낼 때는 앞에서부터 꺼내게 되는데, 이 순서가 큐 내부에서의 우선순위 순과 일치하게 되는 것이다. 일종의 자동으로 정렬되는 큐라고 생각하면 된다. 언어나 알고리듬 책에 따라서는 이를 최소/최대힙(min/max heap) 혹은 힙큐(heap queue)라고 부르기도 한다.더 보기 »우선순위 큐 혹은 최소/최대힙

후위식 변환

중위식과 후위식

B * C와 같은 수식에서 그 형태는 보는 사람에게 정보를 전달하여 이를 정확하게 해석할 수 있게 한다. 이 식에서 계산 방법은 두 수 B, C 사이에 있는 연산자에 의해서 결정되며 여기서는 두 수를 곱하는 계산을 표현하고 있다.

더 보기 »후위식 변환

(파이썬) 약한 참조 사용하기

파이썬과 C를 비교하면서 차이점을 이야기하는 사람 중에는 “파이썬은 별도의 메모리 관리가 필요없다”는 이야기를 하는 사람들이 있다. 실제로 프로그램이 실행되는 동안 객체를 위한 메모리는 파이썬에 의해 자동으로 할당받게 되고, 객체의 파괴 역시 대부분 파이썬이 자동으로 처리한다. 따라서 파이썬 코드에서는 malloc()이나 free() 같은 메모리 관리를 위한 코드가 존재하지 않는 것은 사실이다.

파이썬에서 메모리 관리에 있어 가장 주요한 개념은 참조수인데, 참조수는 어떤 객체 외부에서 그 객체를 참조하는 지점의 개수이다. 즉 어떤 객체를 누군가 참조한다는 것은, 외부의 누군가가 그 객체가 계속 살아있기를 원한다는 의미이므로 그 수명을 유지하게 하며, 반대로 이러한 참조점이 없는 객체는 사용할 수 없는 객체가 되기 때문에 파괴되어도 상관없다는 의미가 된다.

파이썬의 모든 것은 객체이고, 모든 파이썬 변수는 객체에 붙는 이름이다. 즉 객체에 어떤 이름이 붙었다는 것은 이 객체를 참조하는 곳이 한 군데 생겼다는 뜻이다. 그 외에 객체가 다른 객체의 속성으로 바인딩되는 것도 참조수를 늘리는 것이며, 리스트나 사전과 같은 컨테이너에 포함되는 것도 참조수가 증가하는 효과를 갖는다.

만약 그 이름이 다른 객체를 가리키도록 바뀌게 되면, 파이썬은 내부적으로 참조수를 1 떨어뜨린다. 그리하여 참조수가 0이된 객체는 그냥 그 자리에서 즉시 파괴되는 식이다. 그러니, 별도로 사용하지 않는 객체를 명시적으로 파괴하는 코드를 호출할 필요가 없는 것이다. 하지만 세상 일이란게 단순해보이더라도 그게 늘 마음처럼 한결같지는 않은 법이다. 이러한 참조수에 의한 메모리 관리가 실패할 수 있는 경우와, 그럼 문제를 어떻게 해결할 수 있는지를 살펴보도록 하자.

더 보기 »(파이썬) 약한 참조 사용하기

마크 다운을 PDF 문서로 변환하기

마크 다운을 HTML 문서로 변환하고, 다시 HTML 문서를 PDF로 변환하는 과정을 거치면 PDF 파일을 얻을 수 있다. HTML 파일을 PDF로 만드는 데는 파이썬으로 제작된 xhtml2pdf라는 패키지가 있긴 하지만 동작이 좀 불안정하거나 한글이 제대로 렌더링 되지 않는 (한글을 제대로 랜더링하는 방법은 있는데, 이 경우 CSS가 제대로 적용되지 않는다.) 등의 문제가 있어서 웹킷 엔진으로 렌더링하는 것과 같은 결과를 얻을 수 있는 PhantomJS를 사용하기로 결정했다.
더 보기 »마크 다운을 PDF 문서로 변환하기

오일러 프로젝트 31

영국의 화폐 단위는 파운드(£)와 펜스(p)이고, 동전의 종류는 아래와 같습니다.

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), £2 (200p)

이 동전들을 가지고 2파운드를 만드는 방법들은 다양할 것입니다. 예를 하나 들면 이렇습니다.

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

2파운드를 만드는 서로 다른 방법은 모두 몇 가지나 있습니까?

https://euler.synap.co.kr/problem=31
더 보기 »오일러 프로젝트 31

GIL

GIL CPython은 Global Interpreter Lock, 즉 GIL이라는 것을 사용한다. GIL은 일종의 뮤텍스로 복수의 네이티브 파이썬 스레드가 동시에 바이트코드를 실행하지 못하도록 하는 것이다. CPython의 메모리 관리 방식은 스레드-안전하지 못하기 때문에 이러한 방식의 락이 필요하다. 반대로 GIL을 도입하면서부터 다른 기능들은 GIL이 강제하는 부수효과에 의존하기 시작하기도 한다. GIL은 양면성을 가지는데, 멀티스레드로 디자인된 CPython 프로그램이 멀티프로세서 시스템의 장점을 제대로 살리지 못하게 한다는 약점을 가지고 있다. (덕분에 파이썬 커뮤니티는 GIL을 강제하는 것 때문에 까이고 있다.) 하지만 다행히다 I/O나 이미지처리, NumPy등을 사용하는 고도의 수학계산과 같은 부분들은… 더 보기 »GIL