Home » algorithm

algorithm

(Swift) – 힙(Heap) – 자료구조에 대해

heap은 일종의 바이너리 트리를 단일 배열을 이용해서 구현한 구조로,  부모 자식 간의 직접적인 참조를 갖지 않고 배열의 인덱스에 의해서 위치 관계를 파악한다. 특히 내부 배열의 상태는 부분적으로 정렬되는 것과 비슷한데, 항상 “맨 앞의 원소를 꺼내었을 때 그 값이 최대 혹은 최소가 된다”는 특성을 가진다. 힙은 흔히 최대힙과 최소힙으로 구분하는데 이는 동일한 것이며 단지 정렬 순서만 다르다. 주로 자료 구조에서는 최대/최소 힙, 바이너리 힙, 힙 큐 혹은 우선순위 큐와 같은 이름으로 불린다.

참고로 이 자료 구조의 파이썬 구현은 [우선순위 큐 혹은 최소/최대힙]에서 한 번 설명한 바 있다.

힙으로 할 수 있는 일은 다음과 같다.

  1. 우선순위 큐를 만든다.
  2. 힙 정렬 수행
  3. 변경가능한 집합의 최소값(혹은 최대값)을 빈번히 계산해야 할 때 유용하다. (특히 최단거리 탐색 시)

더 보기 »(Swift) – 힙(Heap) – 자료구조에 대해

정수 배열의 최대 부분합 (연습문제)

배열의 연속된 부분집합의 최대합 정수 배열이 주어질 때 배열내의 연속된 원소를 더한 부분합의 최대값을 구하는 문제이다. 구간이 아닌 최대값 자체를 구하면 되는 문제이다. 간단히 생각하면 0부터 1, 2, 3 … n 까지의 합 중 최대인 값, 그 다음은 1부터 2, 3, 4 .. n 까지의 값 중 최대인값 이렇게 비교해나갈 수 있는데 그러면 반복계산이 너무 많다. 따라서 DP를 이용한다. 0번 인덱스까지의 최대합은 0번 값 그 자체이다. i번 인덱스까지의 최대 부분합은, (i-1) 번 까지의 최대 부분합과 i번 값의 합이다. 이 때… 더 보기 »정수 배열의 최대 부분합 (연습문제)

오일러프로젝트78

동전 100개를 나누는 방법 이 문제는 오일러 프로젝트 76번 문제와 같은 문제로 볼 수 있는데…. 처음 작성한 시점부터 너무 오래된 글이라, 진도를 기다리지 못하고 미리 발행한다. 5개의 동전이 있다.  이 동전들을 나누는 방법을 생각해 보자. 동전 5개는 아래와 같이 총 7가지 방법으로 나눌 수 있다. ooooo # 5개짜리 그룹 1개 oooo o # 4개 + 1개 ooo oo # 3개 + 2개 ooo o o # 3개 + 1개 + 1개 oo oo o # 2개 + 2개 + 1개… 더 보기 »오일러프로젝트78

Fast Fibonacci Transform

빠른 피보나치 항 구하기 피보나치 수열은 0, 1, 1, 2, 3, 5, 8,… 과 같이 앞의 두 항의 합이 그 앞의 항이 되는 수열이다. 피보나츼 수열의 n 항을 구하는 함수는 보통 이렇게 많이 작성한다. def fib(n): if n < 3: return (0, 1)[n] return fib(n-1) + fib(n-2) 하지만 이 함수는 지극히 비효율적이라 %time fib(35) Wall time: 7.05 s Out[7]: 9227465 이런 처참한 성능이 나온다. 이는 한 번 계산했던 값을 계속 재계산하기 때문인데, 이런 문제를 피하기위해서는 메모이제인션이라는 캐싱 기법을 쓴다. #… 더 보기 »Fast Fibonacci Transform

체를 사용하여 소수 집합 구하기

가장 빠른 알고리듬 현재까지 순수 파이썬으로 작성된 알고리듬 중 가장 빠른 것으로 알려진 것은 @Robert William Hanks가 개발한 아래 알고리듬이다. def primes(n): """Return a list of primes under n""" sieve = [True] * (n/2) for i in xrange(3, int(n**0.5)+1, 2): if sieve[i/2]: sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1) return [2] + [2*i+1 for i in xrange(1, n/2) if sieve[i]]

소인수분해 구현하기

소인수분해(prime fatorization)는 어떤 합성수를 소인수의 곱으로 표현하는 것을 의미한다. 12는 합성수이며, 1, 2, 3, 4, 6, 12 로 나눠질 수 있다. 이렇게 어떤 합성 수를 인수의 곱으로 표시하는 방법은 다양하지만, 소수들의 곱으로 표현하는 방법은 (순서를 무시하면) 하나의 방법만 존재한다. 12 = 2 * 2 * 3 으로 표시할 수 있다.

소인수 분해를 사용하면 약수의 개수나 모든 약수의 합을 좀 더 쉽게 계산할 수 있다. 물론 이것은 연필과 종이를 사용할 때에 적용될 것 같은 이야기이다. 컴퓨터를 사용하는 소인수 분해의 경우, “소수인 인수를 정하는 것”에 제법 시간이 소요될 수 있기 때문에 실제로 그리 크지 않은 범위의 수에 대해서는 무식하게 루프를 돌면서 나눠보는 것으로 약수를 세거나 더하는 방법이 더 빠를 수 있다.

더 보기 »소인수분해 구현하기

사전식 순열의 다음 항 구하기 (파이썬)

참고 : 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)

병합정렬

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

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

더 보기 »병합정렬