분류 전체보기 (317) # 미사용 재귀 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. https://github.com/AeroCodeX/ 재귀 알고리즘(Iterative)의 개념하나의 큰 문제를 똑같은 형태를 갖는 여러개의 부분문제로 나누어 푸는 것.sum(n) // 1부터 n까지의 합. sum(10) = 10 + sum(9);sum(9) = 9 + sum(8);...sum(n) = n + sum(n-1);또 다른 자신이 구했던 이전 값을 활용하여 정답을 계산하며,비순차적으로 계산이 이루어지는 방식. 여기서 순차적이란 용어는 처음부터 정답까지 모든 경우를 차례대로 계산한다는 의미로 사용되었다.N=10인 경우의 정답을 구하기 위해 N=0, .. ,9인 경우의 정답까지 전부 구해놓는다는 의미이다.N=10와 전혀 상관없는 케이스의 정.. 2018. 11. 11. 07:06 # 미사용 순회 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. https://github.com/AeroCodeX/ 순회 알고리즘(Iterative)의 개념자신이 직접 구했던 이전 값을 기반으로 정답을 계산하며.순차적으로 계산이 이루어지는 방식. 여기서 순차적이란 용어는 처음부터 정답까지 모든 경우를 차례대로 계산한다는 의미로 사용되었다.N=10인 경우의 정답을 구하기 위해 N=0, .. ,9인 경우의 정답까지 전부 구해놓는다는 의미이다.N=10와 전혀 상관없는 케이스의 정답도 전부 구해놓는다. 또한 각 케이스의 결과는 순차적으로 구해지나, 중간결과로써 병렬적으로 계산될 수 있다.N=0의 결과가 N=1, ..., N 을 계산하는데 필요하다면, 각 공간에 중간값으로써 저장해놓는 것 이다. 아래는 순차적으로 구.. 2018. 11. 11. 06:53 # 미사용 무차별 대입 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. https://github.com/AeroCodeX/ 부르트 포스(Brute Force) 개념가능한 모든 경우의 수를 검사하는 것.많은 자원을 소모하지만 가장 확실한 방법이고,무엇보다 다른 사람이 이해하기 쉬운 코드를 만들어낸다. 러닝타임은 꽤 걸리겠지만, 구현하기 쉽고. 이해하기 쉽다. 점진적 성능향상을 이용한 알고리즘 풀이순진하게 부르트 포스를 적용했다간, 굉장히 높은 확률로 시간제한에 걸린다.확실하게 답이 아닌 영역을 배제함으로써 성능을 향상시켜야 한다. 다음은 부르트-포스의 중요한 특징이다.첫 아이디어가 굉장히 단순하다. (구현하기 쉽다.)조금씩 성능을 개선해나갈 수 있다. 충분히 성능을 개선해나가면, 부르트-포스로도 빠른 문제풀이가 가능.. 2018. 11. 11. 05:57 # Foundation/기초수학 급수 알고리즘 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. https://github.com/AeroCodeX/ 급수(Series)의 정의수열 An이 주어졌을 때, 수열(Sequence)에 속해있는 모든 원소의 합. 끝이 존재하는 수열의 급수를 유한급수라고 하며,끝이 존재하지 않는 수열의 급수를 무한급수라고 한다. 급수 알고리즘 개요 사실 알고리즘도 아니다.급수 공식을 활용하면 대부분 상수 시간내에 수열의 합을 계산할 수 있다. Function Information series_arth(a0, d, n) 순회를 이용하여 산술급수를 구한다. series_arth_formla(a0, d, n) 급수공식을 이용하여 산술급수를 구한다. series_geo(a0, r, n) 순회를 이용하여 기하급수를 구한다. s.. 2018. 11. 5. 16:11 # Foundation/기초수학 파도반 수열 알고리즘 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. https://github.com/AeroCodeX/ 파도반 수열(Padovan Sequence)의 정의현재항의 값이 2, 3번째 이전의 항의 합으로 계산되는 수열.여기서는 인덱스가 0이고 초기값인 {1, 1, 1}인 수열을 사용한다.아래는 인덱스가 0이고 초기값이 {1, 0, 0}인 파도반 수열의 리스트이다.{1, 1, 1} 으로 시작하는 부분부터 위 그림의 점화식을 따른다. 출처 : OEIS_A000931 파도반 수열 알고리즘 개요파도반 수열과 피보나치 수열의 점화식은 매우 유사하다.따라서 파도반 수열을 구하는 알고리즘도 피보나치와 고만고만하다. Function Information pado_recursion(n) 재귀를 이용하여 n번째 피보.. 2018. 11. 4. 18:53 # Foundation/기초수학 피보나치 수열 알고리즘 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. https://github.com/AeroCodeX/ 피보나치 수열(Fibonacci Sequence)의 정의현재항의 값이 이전 2개 항의 합으로 계산되는 수열. 컴퓨터 과학에서는 주로 0번째 항이 0인 피보나치 수열을 사용한다. ( 0, 1, 1, 2, ... )아래는 200번째 인덱스까지의 피보나치 수열 테이블이다. 출처 : OEIS_A000045 피보나치 수열 알고리즘 개요N번째 피보나치수를 알고 싶다면, 정의에 따라 N-1, N-2번째 피보나치 수를 알고 있어야 한다.정리하자면, 얼마나 효율적으로 N-1, N-2를 가져오느냐가 전체 성능을 좌우한다. 아래는 피보나치 수열을 만들때 사용하는 방법들이다. Function Information .. 2018. 11. 3. 17:02 # Foundation/기초수학 소수 알고리즘 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. https://github.com/AeroCodeX/ 소수(Prime-Number)의 정의 1과 자기 자신만을 약수로 갖는 수. 소수가 아닌 수를 합성수(composite)라고 한다.그림에서 보듯이 소수는 1과 자신을 제외한 m x n 형태로 표현할 수 없다. 아래는 인덱스가 1,000,000 이하의 소수 테이블이다. 출처 : OEIS_A000040 소수 판별 알고리즘 개요정확히는 소수 판별(Prime Testing)이 아닌 소수 생성(Prime Generation)알고리즘이다. N이 소수인지 알고 싶다면 N까지 소수 테이블을 만들고나서 확인해야 한다.수학적 의미의 판별(Testing)은 완벽한 결과를 보장할 수 없거나 확률론을 기반으로 하기 때.. 2018. 10. 26. 23:11 # Foundation/기초수학 최대 공약수와 최소 공배수의 관계 이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. https://github.com/AeroCodeX/ 두 정수의 최대공약수와 최소공배수의 관계두 정수 a, b에 대하여, 이것의 최대공약수와 최소공배수를 각각 hcf, lcm이라 하면 아래와 같은 등식이 성립된다. HCF (Highest Common Factor) : 최대 공약수 GCD (Greatest Common Divisor) : 최대 공약수 LCM (Lowest Common Multiple) : 최소 공배수 증명은 다음과 같다. 숫자가 여러개일 때, 최대공약수와 최소공배수의 관계 숫자가 3개 또는 4개 이상일 때도 비슷하게 흘러간다. 2018. 10. 24. 01:04 이전 1 ··· 24 25 26 27 28 29 30 ··· 40 다음
