소인수분해로직

소인수분해1하기에 관한 알고리듬. 예전에는 클래스를 하나 만들어서 n보다 작은 소수의 리스트를 먼저 구해서 이를 사용했지만, 아래 알고리듬이 훨씬 빠르기 때문에 오일러프로젝트 문제 풀이에 매우 유용하다. 특히 나눌 수 있는 최소의 숫자를 찾는 함수에서 2, 3, 5로 먼저 나눠본 후 7에서 시작해서 4, 2를 번갈아 가면서 더하는 로직을 눈여겨보자. 이를 통해 3의 배수로 나눠보는 케이스를 최소화할 수 있다. def factor(n): “”” 주어진 수를 소인수 분해한다. >>> factor(786456) [(2,3), (3,3), (11,1), (331,1)] “”” #### 2보다 큰 양수에 대해서만 유효하다. if n in

사전식 순열생성

http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order 사전식 순열 생성 함수 주어진 수열에 대해 모든 순열을 생성하는 방법에는 많은 종류가 있다. 그 중 한가지 고전적인 알고리듬은 사전식 순서에 의한 다음 순열을 찾는 방법이다. 이 방식을 사용할 수 있다면 (중복된 원소가 있더라도) 각각 고유한 순열들의 멀티셋을 한 번에 하나씩 생성할 수 있다. 먼저 수열을 오름차순으로 정렬한다. (이는 사전식 순열의 맨 첫째 순열에 해당한다.) 그런다음 현재 순열보다 큰 바로 다음 순열을 찾아나간다. 그리고 더 이상 큰 순열을 찾을 수 없다면 종료하면 된다. 이 방식은 14세기 인도의 나라야나 판디타에

Shell 정렬

Shell 정렬 Shell 정렬은 “분할 증분 정렬”(diminishing Incremental Sort)이라고도 불리는 방법으로 삽입정렬을 원래 리스트를 더 작은 서브리스트들로 나눠서 정렬함으로써 성능을 향상시키는 방법이다. 즉 리스트를 더 작은 조각들로 나눈다음 각각을 삽입정렬을 사용하여 정렬한다. 이 때 서브리스트들을 나누는 기준을 정하는 방법이 독특한데, 연속된 원소들로 구성된 서브리스트를 나누는게 아니라 i개씩 건너뛰고 원소들을 선택하여 서브리스트를 만든다. 이 때 i는 gap이라고도 불리운다.

병합정렬

Merge Sort Shell 정렬은 보통의 삽입정렬을 리스트를 쪼개는 방식으로 성능을 향상시킨 예이다. 이러한 분할정복방식을 검색에 도입한 알고리듬이 여럿 있는데, 병합정렬(merge sort)도 그 중 하나이다. 병합정렬은 리스트를 재귀적으로 절반으로 나누어 처리하는 방식이다. 만약 리스트가 비어있거나 원소가 하나만 있다면 그 자체로 정렬되어 있다고 보고, 그것이 베이스 케이스1가 된다.

동적계획법

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