Algorithm 개념 및 문제풀이/Euler Project5 17번 string 과 map 을 사용해서 품 p.s 40은 영어로 fourty 가 아니라 forty 다 (영어 20년 넘게 쓰면서 처음 앎) 2018. 9. 3. 오일러 16번 2^1000 값의 자리수들을 모두 더한 값을 구하는 문제이다. 2^1000 을 display 할 수 없으므로 c 언어로는 풀기가 까다로운 면이 있다. 머리를 많이 굴려봤지만 별수가 떠오르지 않았다..한가지 떠오른 건 13번 문제처럼 숫자를 문자로 치환하면 큰 값들을 처리할 수 있고 풀 수 있지 않을까라고 생각했다. 정답을 찾아 제출하고 다른 사람들이 푼 방법들을 봤는데 문자열을 이용해 풀고 동적할당하는 방식이 가장 이상적으로 보여 아래와 같이 풀었다. 1. 이중 for문을 사용하는데 바깥 for문은 2를 1000번 곱하는 큰 과정이고 내부 for문은 각 자리수들을 처리하기 위한 for문이다, 내부 for문의 횟수는 문자열 배열의 크기만큼 반복을 하게 된다. 2. digit, temp[j], carry 라.. 2018. 8. 14. 오일러 15번 단순한 dynamic pr 문제라고 생각했는데, 수학적인 지식을 요구하는 문제였다(euler 문제들이 전부 그렇지만!) 또 조합으로도 풀 수 있는 문제이다. dynamic 문제 유형과 유사하여 기억을 되살려 풀려고 했지만 실빼.. 검색을 해보면서 다른 분들은 어떻게 풀었는지 참고를 하였다. 그 중 dynamic 으로 푼 블로거 분이 계셔서 이를 참조하였는데 정답이 long long int로 꽤 큰 값이 나왔음에도 빠른 시간안에 수행이 되었다. 이 후 코드리뷰를 진행하는데, for (int i = 0; i < N+1; i++) { arr[N][i] = 1; arr[i][N] = 1; } 위 부분이 이해가 되지 않았다..검색을 좀 더 해보니 아래 블로그가 top으로 떠 참고를 해보았다 아래 블로그가 원본 코.. 2018. 8. 8. Problem 12 이전에 올렸던 글에서 그 다음으로 어려웠던..약수의 갯수가 500이 넘는 최소 값을 찾는 문제 삼각수를 구하는 방식에 약수를 구하는 반복문을 같이 쓰니 시간이 엄청 오래 걸려 값을 구하지 못했다. 좀 더 빠른 시간내에 구할 수 있는 방법은 소인수 분해를 사용하는 것이다, 그리고 삼각수를 구하는 공식을 매크로 함수를 이용해 하는 것도 좋다 이렇게 하면 컴퓨터가 연산하는 시간을 줄이는 데 도움을 준다. 소인수 분해를 통해 약수를 구하는 공식은 다음과 같다. 이를 코드로 옮기는 과정을 적어보았다. 1. 먼저 삼각수를 소인수 분해해주는 함수로 넘겨준다. 2. i=2부터 삼각수의 크기만큼 반복해 약수가 있는지 판별한다. 3. 약수라면 그 때의 i로 n을 나눠주고 지수 값을 증가시켜준다. 4. 증가시킨 지수 값에 .. 2018. 8. 1. Problem 10 문제출처 : http://euler.synap.co.kr/prob_detail.php?id=10 첨으로 오일러 문제들 중 정리하게 된 문제 이백만 이하의 소수들을 모두 더해 출력하는 문제이다 브루트 포스로 풀게 될 경우 약 14분 이라는 시간을 잡아먹게 되므로 시간적으로 비효율적인 방법이다. 이를 수학적으로 접근하게 되면 빨리 풀 수 있게 되는데 에라토스테네스의 체라는 방법을 이용할 수 있다. 기본적으로 그 방법에 대해 알고는 있지만 제대로 사용해본 적이 없어서 다른 블로그의 글을 통해서 제대로 이해할 수 있었다. https://m.blog.naver.com/PostView.nhn?blogId=leejuesong&logNo=220398206365&proxyReferer=https%3A%2F%2Fwww.g.. 2018. 7. 25. 이전 1 다음
