셸 정렬 (Shell Sort)

셸 정렬은 정렬 방법의 원리로만 보자면 “분할 증분 정렬”(diminishing incremental sort)이라고도 불리는 방법이며, 굉장히 오래된 정렬 알고리듬 중 하나이다. 이 정렬 방법은 삽입 정렬을 근간으로 하면서 삽입 정렬의 성능을 간단한 아이디어로부터 크게 증가시키는 방법이다.

삽입 정렬은 왼쪽에 있는 원소부터, 그 원소가 이동할 수 있는 ‘가장 왼쪽 자리’에 그 값을 삽입하여 정렬해 나가는 방식이다. 이 때 ‘삽입’을 위한 공간을 만들기 위해 원래자리부터 삽입될 자리 사이의 값들이 하나씩 오른쪽으로 이동해야 한다. 따라서 삽입 정렬은 어떤 원소가 이동해야 할 거리가 크면 클수록 효율이 떨어지며 배열이 반대로 정렬되어 있는 경우가 이에 해당할 것이다.

셸 정렬 (Shell Sort) 더보기

병합정렬

병합정렬은 기초적인 정렬 알고리듬 중에서 널리 알려진 알고리듬 중 하나이며, 대표적인 분정복 알고리듬의 예인 동시에 재귀 알고리듬의 좋은 예이다. 이름에 ‘병합'(merge)이 들어가는 이유는 배열을 2개 혹은 그 이상의 작은 조각으로 나누고 각각의 조각을 정렬한 다음, 각 조각의 앞에서부터 가장 작은 값을 순서대로 골라서 정렬된 결과를 생성하기 때문이다.

원래의 배열을 쪼갠 각각의 조각 역시 똑같은 병합 정렬을 이용해서 정렬하는 재귀적인 동작을 수행한다. 재귀적 알고리듬의 수행 과정을 복잡하고 어렵게 여기는 사람들이 있는데, 입력과 결과에 집중하는 방식으로 바라보면 오히려 더욱 명료하고 간단하다는 것을 알 수 있다.

병합정렬 더보기

동적계획법

동적 프로그래밍

동적 프로그래밍은 세부 계산으로 나뉘어지는 하나의 큰 문제를 세부 계산 결과를 미리 구해서 저장한 후 큰 계산의 결과를 빠르게 도출해내는 문제해결 기법이다.(이름과는 달리 프로그래밍 테크닉은 아니다.) 흔히 피보나치 수열을 계산할 때 memoization도 동적 프로그래밍의 범주로 볼 수 있다. 동적계획법 더보기

순열생성로직연구

순열생성로직

순열을 만드는 가장 간단한 방법으로는 특정 원소를 하나씩 뺀 후 배열의 나머지를 순열한 각 결과에 빼냈던 원소를 앞에 붙여준 결과를 모으는 방법이 있다. 대략의 코드는 다음과 같다.

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개 미만의 연속열에 대해서는 나름 나쁘지 않은 성능을 낼 수 있다. 순열생성로직연구 더보기

삽입정렬

삽입정렬(insertion sort)은 기본적인 제자리 정렬 알고리듬 중 하나로, 배열 내의 어떤 위치의 원소를 해당 배열의 가능한 가장 왼쪽 자리에 ‘삽입’하는 동작을 통해 정렬을 수행한다. 삽입 정렬의 이론적인 성능은 O_{(n^2)}이지만, 데이터가 정렬된 상태에 가깝다면 삽입 동작이 그 만큼 적게 일어나므로 더 빨라질 수 있다. 현실 세계의 데이터는 완전히 랜덤하기보다는 약간은 정렬된 경향을 가지므로 같은 O_{(n^2)}인 버블정렬 알고리듬보다는 더 빠르게 동작하는 것으로 알려져 있다.

삽입정렬 더보기