Project Euler21 Problem 8 - Largest product in a series 이 문제는 주어진 엄청나게 긴 숫자열(1000개 숫자)에서 연속으로 13개의 숫자의 곱 중 가장큰 숫자를 찾는 문제입니다. 일직선으로 생각하면 되고, 대각선이나 세로가 아닌 horizental로 생각하고 해결하면 됩니다. 가장 처음으로 생각할 부분은 이 문제를 가장 원초적으로 어떻게 풀 것인지를 생각하고, 차차 난이도가 있는 제약이 들어올 것을 고려하여 최적화하는 단계로 진화를 시키면 되겠습니다. 우선 원초적으로 어떻게 풀면 될까요?? 뭐... 그냥... 첫번째 ~ 13번째 수까지의 곱을 구하고 두번째 ~ 14번째 수까지의 곱을 구하고 ................... ................... 천번째-12번째 ~ 천번째 수까지의 곱을 구해서 가장큰 수를 뽑으면 되겠습니다. 1. 원초적으로 풀.. 2019. 12. 8. Problem 7 - 10001st prime 말 그대로 10001번째 소수를 구하라!! 소수란 자연수 중 1과 자기자신으로만 나누어지는 수를 말합니다. 따지고 보면 결국 모든 자연수는 소수의 집합으로 이루어 지는데... 그 논리는 소인수분해에서 설명이 되지요. 참 이런걸 발견한 수학자들은 대단한 것 같습니다. 소수를 나열해 보면, 2 3 5 7 11 13... 이렇게 나가고 5번째 소수는 11이 되는 것 입니다. 그럼 10001번째 소수는 무엇일까요?? 만번째를 어떻게 구해... 너무나 오랜 시간이 걸리는거 아니냐... 우리에겐 컴퓨터가 있고 알고리즘이 있는데 무엇이 문제겠습니까?? ㅎㅎ 역시나 Test Case가 많이 들어오는 것을 기준으로 생각을 해보겠습니다. (기준은 Test Case가 1000개, 목표 번째 소수는 최대 10001) 이렇게 .. 2019. 12. 3. Problem 6 - Sum square difference 이번 문제는 왠지 간단한 것 같지만, 제약조건을 두자면 한없이 어려워지는 문제인거 같습니다. 우선 아직까지는 basic한 방식으로만 생각이 나서 해당 방법으로 우선 통과를 하고, 제약조건을 두어 Time Limit에 영향이 없도록 고려해서 한번더 올려보도록 하겠습니다. 주어진 조건만 만족하도록, 100까지의 Sum square difference 구하기 제약조건을 두어 Test case가 10000개의 Test case에 최대 10000까지 구하기 (time out 발생가능) 1. Basic 그냥 단도직입 적으로 구합니다. 단 python을 이용하니... 이 언어에서 가능한 편한 방식으로 구현해 보겠습니다. python에는 배열을 신규로 생성할때, 내부 함수를 통해서 새로운 배열의 생성이 가능합니다. 또.. 2019. 11. 26. Problem 5 - Smallest multiple 이번 문제는 일정 숫자가 주어지면, 1 부터 해당 숫자까지 순차적으로 나누었을때 모든 경우에 나머지가 0인 가장 작은 숫자를 구하는 문제입니다. 느낌적인 느낌을 보자면, 해당 문제는 1 부터 해당 숫자까지의 최소공배수를 구하는 문제입니다. 저는 그렇다면 아래의 절차로 풀어보겠습니다. 최대공약수를 구하는 method 생성 최소공배수를 구하는 method 생성 (해당 method에서는 최대공약수 method호출) main에는 1부터 숫자까지 loop를 돌면서 최대공약수 method 호출 1. 최대공약수를 구하는 method 생성 최대공약수를 구하는 Algorithm은 많이 존재하지만, 제가 알고있는 가장 빠른 방법은... 주어진 2개의 수가 있다면, 큰 수를 기준으로 작은수로 mod를 구합니다. 그리고 난 .. 2019. 11. 25. 이전 1 2 3 4 5 6 다음