통계, IT, AI

1. 개요 문제는 이곳에서 확인할 수 있다. 숫자를 삼각형으로 쌓아놓고 위 층으로부터 한가지 길을 선택해 내려가면서 누적합을 구하되 가장 큰 값을 구하는 것이 목표이다. 단, 길 선택은 두 갈래 중의 하나만 가능하다. 예를 들면, 아래의 숫자 더미에서 최대값은 3 + 7 + 4 + 9 = 23이다. 2. Ver 2.0모든 경우의 수를 찾는 것은 간단한 방법이지만 숫자더미가 커질수록 비효율적인 방법이다. 층수가 충분히 많으면 내가 눈을 감을 때까지도 답을 찾지 못할 수도 있다. 그래서 1주일 가량 다른 방법을 생각해봤지만 결국 답을 찾지 못하고 구글링을 하였다. 방법은 생각보다 훨씬 간단했다. 요는 위에서부터 내려가는 것이 아니라, 밑에서부터 올라가면서 최대값을 찾는 것 이었다. 즉, $l$번째 층의 ..

1. 개요 문제는 이곳에서 확인할 수 있다. 1부터 1000까지 영어로 세고 각 알파벳의 수를 더하면 된다. 몇가지 예외만 고려하면 쉽게 해결할 수 있다. 2. Ver 1.0 # -*- coding: utf-8 -*- data = dict() data[0] = "" data[1] = "ONE" data[2] = "TWO" data[3] = "THREE" data[4] = "FOUR" data[5] = "FIVE" data[6] = "SIX" data[7] = "SEVEN" data[8] = "EIGHT" data[9] = "NINE" data[10] = "TEN" data[11] = "ELEVEN" data[12] = "TWELVE" data[13] = "THIRTEEN" data[14] = "FOURT..

1. 개요 워낙 풀이가 간단하여 두개의 문제의 한개의 포스팅에 올린다. 15번 문제는 이곳에서 확인할 수 있고, 16번 문제는 이곳에서 확인할 수 있다. 15번 문제는 격자무늬에서 찾을 수 있는 길을 찾는 것이 목표인데, 조합을 이용하면 쉽게 해결할 수 있다. 즉, ${}_{40}{\mathrm{C}}_{20}$을 계산하면 된다.16번 문제는 2의 1000승을 구한 후 각 자리의 숫자를 더하면 된다. 2. Ver 1.0 파이선을 사용하여 쉽게 답을 구하자. # -*- coding: utf-8 -*- import math as m # 15. Lattice paths f = m.factorial print(f(40)/(f(20)**2)) # 16. Power digit sum print(sum([int..

1. 개요 문제는 이곳에서 확인할 수 있다.어떤 수열 $a_n$이 아래와 같은 일반항을 가진다고 하자. $$a_{n+1}=\{\begin{array}{ll}{a}_n/2,& \text{if }n\text{ is even}\\ 3a_n+1,& \text{if }n\text{ is odd}\end{array}$$예를 들어 $a_1=13$인 경우 다음과 같이 항의 길이가 10인 수열을 얻는다.$$13\to 40\to 20\to 10\to 5\to 16\to 8\to 4\to 2\to 1$$증명되진 않았지만 모든 양의 정수인 $a_1$은 반드시 1로 끝난다고 알려져 있다...

1. 개요 문제는 이곳에서 확인할 수 있다. 50자리수 100개를 더한 뒤 처음 10자리의 숫자를 찾는 것이 목표이다. 2. Ver 1.0 어떤 언어를 사용하느냐에 따라서 구현의 복잡성이 달라질 수 있다. 여기서는 간단하게 파이선을 이용하도록 하자. 파이선으로는 자료 입력 부분을 제외하면 단 한줄로 답을 구할 수 있다. # -*- coding: utf-8 -*- data = """37107287533902102798797998220837590246510135740250 46376937677490009712648124896970078050417018260538 74324986199524741059474233309513058123726617309629 9194221336357416157252243056330..

1. 개요 문제는 이곳에서 확인할 수 있다. 먼저 $n$번째 triangular number는 1부터 정수 $n$까지의 합으로 정의된다. 예를 들어 3번째 triangular number는 $1+2+3=6$이다. 문제의 목표는, 처음으로 500개가 넘는 제수(divisor)를 가지는 triangular number를 찾는 것이다. 문제를 풀고나니 더 좋은 방법이 있었기 때문에 이를 비교하기 위하여 각 풀이마다 시간을 잰다. 2. Ver 1.0 가장 간단한 방법은 어떤 triangular number를 그 숫자의 제곱근보다 작거나 같은 자연수로 나누어 가면서 제수의 수를 세는 것이다. using System; using System.Diagnostics; class ProjectEuler { s..

1. 들어가며 얼마전에 모표준편차를 추정하기 위하여 표본의 범위와 표본의 표준편차 중 무엇을 사용하는 것이 더 나은지 포스팅한 적이 있다. 그것을 밝히기 위해서 여러가지 공식을 증명했었지만 내용과 관련이 없는 것은 적지 않았다. 그렇게 증명한 것 중에 버리기 아까운 것을 적는다. 어떤 확률 변수 $X$와 $Y$의 결합누적분포함수(Joint Cumulative Distribution Function; Joint CDF)를 $F_{XY}(x,y)$라 하고 $X$와 $Y$의 CDF를 각각 $F_X(x)$, $F_Y(y)$라고 하면 $X$와 $Y$의 공분산(Covariance)과 CDF는 아래와 같은 관계를 갖는다. $$Cov(X,Y)=\int _{R \times R}F_{XY}..

1. 개요 문제는 이곳에서 확인할 수 있다. 어떤 숫자더미에서 상하좌우 및 대각선 방향으로 숫자 4개를 곱하여 가장 큰 값을 구하는 것이 목표이다. 2. Ver 1.0 인덱스를 맞추는 것은 귀찮은 일이므로 상하좌우 및 대각선 방향으로 4개의 숫자를 찾되 IndexOutOfRangeException이 발생하면 바로 다음의 경우를 찾는 식으로 구현한다. using System; using System.Collections.Generic; using System.Linq; class ProjectEuler { static void Main(string[] args) { string str_data = @"08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08..

1. 개요 문제는 이곳에서 확인할 수 있다. 200만보다 작은 소수의 합을 구하는 것이 목표이다. 소수를 찾는 데에는 에라토스테네스의 체를 이용한다. 예를 들어 2 이상 120 이하의 소수를 찾는다고 하자. 먼저 2를 남기고 2의 배수를 모두 지운다. 이후 3을 남기고 3의 배수를 모두 지운다. 다음 수인 4는 이미 지워졌으므로 5를 남기고 5의 배수를 모두 지운다. 이것을 120의 양의 제곱근보다 작은 정수 중 가장 큰 정수까지 반복하면 된다. 아래 그림은 이 방법에 대한 일러스트레이션이다. 2. Ver 1.0 using System; using System.Collections.Generic; using System.Linq; class ProjectEuler { static void Main(str..

1. 개요 문제는 이곳에서 확인할 수 있다. 합이 1000인 서로 다른 3개의 자연수 가운데, 가장 큰 수의 제곱이 나머지 두 수의 제곱의 합과 같은 자연수를 찾고 그것의 곱을 구하는 것이 목표이다. 2. Ver 1.0 가장 작은 자연수를 $a$라고 하자. $a$는 1이상, 332이하이다. 332보다 크다면 문제의 조건을 충족시킬 수 없기 때문이다. 같은 이유에서 두번째로 큰 자연수 $b$는 $a+1$이상, $(1000-a)/2-1$이하이다. 이 조건을 이용하여 코딩한다. using System; class ProjectEuler { static void Main(string[] args) { for(int a=1; a