back-tracking
예전에 LiveScript를 사용해서 스도쿠 문제를 푸는 코드를 소개한 적이 있었는데, 세상 쓸데없는 글이었습니다. LiveScript는 별로 알려지지도 않았고, 심지어 제가 처음 관심을 갖고 익혀본 그 즈음부터는 아예 개발도 중단된 상태로 방치되고 있는 언어거든요. 게다가 언어 자체가 함수형 언어식 표현을 적극적으로 도입하고 있고, 가독성하고는 크게 관련이 없다보니 코드 하나하나가 지금 읽어봐도 뭔지
051
두자리 숫자 ▯3 의 첫번째 자리를 여러가지로 바꿨을 때 가능한 아홉가지의 결과 중에서 13, 23, 43, 53, 73, 83의 여섯개는 소수입니다. 56▯▯3의 세 번째와 4번째 자리를 동일한 숫자로 바꿔서 만들어지는 10개의 다섯자리 숫자 중에는 아래에서 보듯이 7개가 소수가 되며, 이것은 이런 식으로 7개의 소수가 만들어지는 첫번째 경우입니다. 이 소수
algorithm
배열의 연속된 부분집합의 최대합 정수 배열이 주어질 때 배열내의 연속된 원소를 더한 부분합의 최대값을 구하는 문제이다. 구간이 아닌 최대값 자체를 구하면 되는 문제이다. 간단히 생각하면 0부터 1, 2, 3 … n 까지의 합 중 최대인 값, 그 다음은 1부터 2, 3, 4 .. n 까지의 값 중 최대인값 이렇게 비교해나갈 수 있는데
exercise
벽과 폭탄 각 테스트 케이스마다 ‘W’, ‘B’로 이루어진 문자열이 입력된다. B는 폭탄을, W는 벽을 의미하는데, 폭탄이 하나 터지면 폭탄을 중심으로 반경 2칸 이내의 벽이 모두 폭파된다. 이 때 폭탄이 일시에 터졌을 때 폭파되는 벽의 개수를 출력하라. (https://www.hackerearth.com/problem/algorithm/bob-and-bombs-cake-walk/description/) BWW, BW, WB, WWB에 해당하는
algorithm
큰 N에 대해서 N번째 피보나치 수를 구하기 피보나치 수열의 일반항을 구하는 함수에 대해서 오일러 프로젝트 관련 글에서 한 번 언급한 적이 있는데, 점화식을 그대로 정직하게 코드로 옮겨놓은 경우, 극히 작은 일부 n에 대해서만 실용성이 있을 정도로 비효율적이다. 35 정도를 넘기면 느려지기 시작하는데 40정도만 되어도 처참한 성능을 보여준다. def fib_1(
algorithm
가장 빠른 알고리듬 현재까지 순수 파이썬으로 작성된 알고리듬 중 가장 빠른 것으로 알려진 것은 @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,
algorithm
셸 정렬은 정렬 방법의 원리로만 보자면 “분할 증분 정렬”(diminishing incremental sort)이라고도 불리는 방법이며, 굉장히 오래된 정렬 알고리듬 중 하나이다. 이 정렬 방법은 삽입 정렬을 근간으로 하면서 삽입 정렬의 성능을 간단한 아이디어로부터 크게 증가시키는 방법이다. 삽입 정렬은 왼쪽에 있는 원소부터, 그 원소가 이동할 수 있는 ‘가장 왼쪽 자리’에
algorithm
병합정렬은 기초적인 정렬 알고리듬 중에서 널리 알려진 알고리듬 중 하나이며, 대표적인 분정복 알고리듬의 예인 동시에 재귀 알고리듬의 좋은 예이다. 이름에 ‘병합'(merge)이 들어가는 이유는 배열을 2개 혹은 그 이상의 작은 조각으로 나누고 각각의 조각을 정렬한 다음, 각 조각의 앞에서부터 가장 작은 값을 순서대로 골라서 정렬된 결과를 생성하기 때문이다.
algorithm
동적 프로그래밍 동적 프로그래밍은 세부 계산으로 나뉘어지는 하나의 큰 문제를 세부 계산 결과를 미리 구해서 저장한 후 큰 계산의 결과를 빠르게 도출해내는 문제해결 기법이다.(이름과는 달리 프로그래밍 테크닉은 아니다.) 흔히 피보나치 수열을 계산할 때 memoization도 동적 프로그래밍의 범주로 볼 수 있다. 피보나치 수열은 자연수 n에 대해서 다음과 같이 정의된다. a(
algorithm
사실 이 포스팅은 순열을 만드는 방법에 대한 매우 비효율적인 접근에 대한 글입니다. 효율적인 순열/조합 생성 코드는 이 글을 참고하세요. 순열을 만드는 가장 간단한 방법으로는 특정 원소를 하나씩 뺀 후 배열의 나머지를 순열한 각 결과에 빼냈던 원소를 앞에 붙여준 결과를 모으는 방법이 있다. 대략의 코드는 다음과 같다. def rec_perm(
algrithm
삽입정렬(insertion sort)은 기본적인 제자리 정렬 알고리듬 중 하나로, 배열 내의 어떤 위치의 원소를 해당 배열의 가능한 가장 왼쪽 자리에 ‘삽입’하는 동작을 통해 정렬을 수행한다. 삽입 정렬의 이론적인 성능은 이지만, 데이터가 정렬된 상태에 가깝다면 삽입 동작이 그 만큼 적게 일어나므로 더 빨라질 수 있다. 현실 세계의 데이터는 완전히
algorithm
버블정렬은 정렬 중에서 가장 기본적이고 쉬운 알고리듬이다. 버블정렬은 배열의 앞에서부터 큰 원소를 뒤쪽으로 보내는 작업을 반복적으로 시행하여 배열 전체를 정렬한다. 이 때 큰 값들이 물속에서 거품이 떠오르는 것처럼 움직이기 때문에 ‘버블’이라는 이름이 붙었다. 간단한 예를 통해서 버블 정렬이 어떻게 작동하는지 살펴보자. 아래와 같은 배열이 있다고 가정하자. [45][53][26]