- 유클리드 호제법 ( Euclidean algorithm) - GCD(24,16) = GCD(16,8) = GCD(8,0) = 8 #include int target; int a[100]; int gcd(int x, int y){ if(y==0){ return x; }else{ return gcd(y,x%y); } } int main(void) { int a,b; scanf("%d %d", &a, &b); int result = gcd(a,b); printf("%d\n",result); return 0; } 반복문으로 구현 int gcd(int x, int y){ while(y != 0){ int r = x%y; x = y; y = r; } return x; }
삽입정렬 개념 삽입정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽) 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘 이다. 장점 : 레코드가 이미 정렬되어 있는 경우 매우 효율적이다. 단점 : 비교적 많은 레코드들의 이동을 포함하고 레코드의 수가 클 경우 적합하지 않다. 시간복잡도 : Best T(n) = O(n) , Worst T(n) = O(n^2) 참고 URL : https://www.w3resource.com/csharp-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-6.php 소스 #include using namespace std; ..
퀵정렬 | 퀵 정렬이란 ? 분할정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 분할 정복(Divide and conquer)방법 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 분할 정복은 대개 순환 호출을 이용하여 구현한다. 하나의 리스트를 피벗(Pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트르 정렬한 다음, 두개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법 퀵 정렬의 단계 분할(Divide) : 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열로 분할 한다 (왼쪽 : 피벗보다 작은 요소, 오른쪽 : 피벗보다 큰 요소) 정복(Conquer) : 부분 배열을..
메모제이션을 활용한 피보나치 수열 이미 계산한 내용들을 저장해 두고, 연산할 필요없이 저장된 데이터를 불러오는 것이다. 메모제이셔늘 쓰게 되면 기존 O(2^N)에서 O(N)으로 급격하게 줄어든다. 더보기 data[1] = fibo(1) data[2] = fibo(2) data[3] = data[1] + data[2] = fibo(3) data[4] = data[2] + data[3] = fibo(4) data[5] = data[3] + data[4] = fibo(5) 소스 package org.kyh.codeup; import java.util.Scanner; public class p1905 { static int[] data; //static int sum = 2; public static void ..