삽입정렬
삽입정렬(insertion sort)은 기본적인 제자리 정렬 알고리듬 중 하나로, 배열 내의 어떤 위치의 원소를 해당 배열의 가능한 가장 왼쪽 자리에 ‘삽입’하는 동작을 통해 정렬을 수행한다. 삽입 정렬의 이론적인 성능은 
버블 정렬 (Bubble Sort)
버블정렬은 정렬 중에서 가장 기본적이고 쉬운 알고리듬이다. 버블정렬은 배열의 앞에서부터 큰 원소를 뒤쪽으로 보내는 작업을 반복적으로 시행하여 배열 전체를 정렬한다. 이 때 큰 값들이 물속에서 거품이 떠오르는 것처럼 움직이기 때문에 ‘버블’이라는 이름이 붙었다.
간단한 예를 통해서 버블 정렬이 어떻게 작동하는지 살펴보자. 아래와 같은 배열이 있다고 가정하자.
더 보기 »버블 정렬 (Bubble Sort)파이썬 소켓서버 예제
간단한 소켓서버 구현예제. 여기서 send 하는 내용을 HTTP 규격에 맞춰서 보내면 웹 브라우저로 접속해서 볼 수 있게 된다. 웹서버를 직접 구현해보고자 한다면 출발점은 소켓서버 구현 -> HTTP 프로토콜 이해 -> 소켓서버를 웹서버로 확장하는 방식으로 발전시켜 나갈 수 있다. 하지만 파이썬에서는 이미 HTTP 서버 모듈도 존재하고 이는 꽤 쓸만하므로 따로 만드는 건 삽질이다. (뭐 좋은 경험은 될 수 있겠지만…) 더 보기 »파이썬 소켓서버 예제
[Python] knight tour 문제
Knight Tour Problem
체스판에서 나이트(Knight)가 임의의 한 위치에서 출발하여 체스판의 모든 지점을 한 번씩 방문하는 것을 Knight Tour 문제라고 한다. 엄청나게 많은 경로의 가지수가 있지만, 여기서는 한 종류의 패스를 완성하는 문제를 생각해보자.
더 보기 »[Python] knight tour 문제
이진탐색트리 (Binary Search Tree) 구현하기 – python
Binary Search Tree
이진 탐색 트리는 이진 트리 구조 속에 이진 탐색 알고리듬을 이용하여 키-값 쌍을 저장하는, 어찌보면 맵(혹은 사전이라고도 하는) 구조와 유사한 형태이다. 이진 탐색 자체가 데이터가 정렬된 상태를 전제하기 때문에, 구조 내에 자료를 삽입/삭제하는 과정이 단순하지는 않지만, 어떤 정렬된 상태의 키를 기준으로 데이터를 찾는데는 매우 유리한 구조이다.
이진 탐색 트리는 특정 노드가 어디에 위치하는데에는 크게 관심이 없다. 단지 이를 사용하여 효율적인 탐색을 할 수 있게 한다. 보면 알겠지만 해시테이블이 메모리 공간을 더 사용하고 반대급부로 성능을 얻는 것과는 달리, 이진 탐색 트리는 트리 구조 자체의 특성을 사용하므로 부가적인 메모리 공간의 낭비는 적다고 볼 수 있다.
더 보기 »이진탐색트리 (Binary Search Tree) 구현하기 – 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 )
웹서버란 무엇인가
What is a web server?
웹서버는 많은 웹개발자들에게는 블랙박스나 마법의 상자 같은 물건인데, 실상 그것은 하나의 프로그램이다. 이 프로그램은 80번 포트에 소켓을 열고 이 포트를 통해 들어오는 HTTP 요청을 받아, 다시 응답을 보내주는 프로그램이다. 요즘의 웹서버들은 이런 기본적인 기능에 덧붙여 여러가지 부가기능들을 제공한다. 하지만 이러한 기능들은 모두 부가적인 것이며, 웹 서버의 본질은 HTTP 응답을 내보배는 것이다. 만약 에코서버를 작성해본 경험이 있다면 웹서버 역시 이러한 에코 서버와 크게 다르지 않다. 단지 들어오는 입력에 대해 좀 더 많은 손질을 해서 내보내는 것일 뿐이다. 더 보기 »웹서버란 무엇인가
우선순위 큐 혹은 최소/최대힙
우선순위 큐 (priority queue)는 큐와 비슷하게 뒤쪽으로 원소를 삽입하고 앞쪽으로 꺼낼 수 있는 자료 구조이다. 하지만 각 원소는 내부적으로 논리적인 우선순위 값을 가지고 있고, 따라서 선입선출(FIFO)의 규칙에 의해서 나오는 것이 아니라, 큐 내부에서는 높은 우선순위를 갖는 원소가 앞쪽으로 오게 된다. 즉, 큐와 마찬가지로 원소를 꺼낼 때는 앞에서부터 꺼내게 되는데, 이 순서가 큐 내부에서의 우선순위 순과 일치하게 되는 것이다. 일종의 자동으로 정렬되는 큐라고 생각하면 된다. 언어나 알고리듬 책에 따라서는 이를 최소/최대힙(min/max heap) 혹은 힙큐(heap queue)라고 부르기도 한다.더 보기 »우선순위 큐 혹은 최소/최대힙
후위식 변환
중위식과 후위식
B * C와 같은 수식에서 그 형태는 보는 사람에게 정보를 전달하여 이를 정확하게 해석할 수 있게 한다. 이 식에서 계산 방법은 두 수 B, C 사이에 있는 연산자에 의해서 결정되며 여기서는 두 수를 곱하는 계산을 표현하고 있다.