길찾기 알고리즘 지금까지 동적프로그래밍이란 재귀 + 메모제이션 이라고 알고 있었다. 재귀의 단점을 발전시킨 것이 메모제이션이고 이는 Top-Down 방식으로 진행된다. 동적프로그래밍은 초기화 된 처음 값을 쌓아가는 방식으로 Bottom-Up 방식으로 진행된다. 둘다 아이디어는 같다. 부분 문제들의 값을 다른 메모리 배열에 저장하여 반복계산하지 않는다. 주로 선호되는 방식은 메모제이션이다. 점화식 # 점화식 if ( map[i][j] == 0 ) MEMO[i][j] = 0; if ( map[i][j] == 1 ){ i==0, j==0 이면 MEMO[0][0] = 1; i > 0, j==0 이면 MEMO[i][j] = MEMO[i-1][j]; i==0, j > 0 이면 MEMO[i][j] = MEMO[i][..
소스 구현 (정렬된 수에서 32를 찾기) package org.kyhslam.algo; public class binarySearch { static int a[] = {12,23,32,57,65,81,89,99}; public static void main(String[] args) { viewArray(a); int target = 32; System.out.println(); binary(target); } //반복문 static public void binary(int target){ int left = 0; int right= a.length-1; // 7 while(left target){ right = mid -1; }else if(a[mid] < target){ left = mid +1; ..
선택정렬 개념 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘 최솟값 또는 최댓값을 찾고 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것이 선택정렬의 핵심이다. 첫번째 순서에는 첫번째 위치에 가장 최솟값을 넣는다. 두번째 순서에는 두번째 위치에 남은 값 중에서의 최솟값을 넣는다. 선택정렬 특징 장점 자료의 이동횟수가 미리 결정된다. 단점 시간 복잡도가 n제곱이라 효율적이지 않아코딩 테스트에서는 많이 사용하지 않는다. 안정성을 만족하지 않는다. 즉, 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다. 선택정렬 예제 선택정렬 구현 코드 package org.kyhslam.algo; public class selectSort { public s..
| 병합정렬(Merge Sort) 대표적인 분할정복 방법을 채택한 알고리즘 이다. 퀵 정렬과 동일하게 O(N * logN)의 시간 복잡도를 가진다. 병합정렬은 정확히 반씩 나눈다는 점에서 최악의 경우에도 O(N * logN)을 보장한다. 하나씩 나누고 합쳐지면서 정렬을 수행한다. 즉, 합쳐지는 순간에 정렬을 수행한다. 왼쪽 집합의 i와 두번째 집합의 j를 증가시키면서 비교연산을 통해 비어있는 새로운 배열에 넣어준다. 병합정렬을 구현할 때 중요한 부분은 반드시 정렬에 사용되는 배열을 전역변수로 선언해야 한다는 것이다. 기존의 데이터를 담을 추가적인 배열공간이 필요하다는 점에서 메모리 활용이 비효율적이라는 문제가 있다. 구현 소스 package org.kyh.algorithm; public class mer..
- 유클리드 호제법 ( 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 ..