본문 바로가기
반응형

자릿수 합2

56. 프로젝트 오일러 #56 : 제곱수의 자릿수 합 이 문제는 난이도 5% 문제이지만, BigInt 모듈이 없는 언어 사용자는 해당 모듈을 구해야 하는 어려움이 있습니다. 파이썬 등을 이용하면 간단하게 해결할 수 있습니다. 문제는 간단합니다. a, b < 100 안에서 a의 b제곱한 결과를 10진수로 표현할 때, 모든 자릿수의 합 중 최대값을 찾으라는 것입니다. 최소값은 1인 것은 당연하고요. 좀 더 좋은 알고리즘을 찾는다는 것은 어려울 것 같습니다. 그냥 무식한 방법으로 풀어보았습니다. #include #include #include "NxBigInt.h" void solve1() { int v = 9, a, b; for( int i = 2 ; i < 100 ; i++ ) { NxBigInt m = i; for( int j = 2 ; j < 100 ; .. 2016. 6. 13.
20. 프로젝트 오일러 #20 : 100!의 모든 자릿수 합 구하기 알고리즘에서 가장 큰 알고리즘을 분류하는 것 중에, 기하급수보다 더 큰 것이 있다면, 모든 경우의 수를 조사하는 팩토리얼(factorial)일겁니다. 뭐 이것보다 더 큰 것도 있을 수 있는데요. 예를 들면, 연제곱승(제곱승에 제곱승이 이어나가는)이 있지만, 이런 알고리즘은 거의 보기 힘듭니다. 연제곱승과 반대되는 것으로는 연로그(로그 안에 로그가 있는 형태)이거나, 연로그가 일정한 값이 되는 로그의 갯수 등입니다. 정확한 용어는 제가 모르지만, 힙정렬에서 힙을 만드는 과정에 이런 개념이 나옵니다. 사실 정렬에서 우리는 일반적으로 이라고 알고 있지만요. 사실 더 본격적으로 들어가면, n개가 배열될 수 있는 경우의 수를 매번 2가지 경우로 나누어져서 찾아서 정렬하는 방법이기 때문에, 최적의 정렬 알고리즘의 .. 2015. 1. 17.
728x90