programing/Algorithm
-
[Algorithm] 정렬 알고리즘에 대하여 2programing/Algorithm 2019. 6. 27. 17:56
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다. 이번에는 포스트에서는 분할정복 기법을 이용하는 병합정렬과 퀵정렬에 대해 포스트하겠습니다. 이전 포스트는 하단의 링크를 참고해주세요. 2019/06/26 - [programing/Algorithm] - [Algorithm] 정렬 알고리즘에 대하여 1 분할 정복(divide & qonquer) 분할 : 문제를 작은 문제로 분할한다. (큰 문제와 작은 문제는 동일한 문제이며, 범위만 다르다.) 정복 : 작게 분할된 문제의 해를 구한다. 합병 : 작게 분할된 문제의 해를 합쳐, 큰 문제의 해를 구한다. 대표적인 정렬 알고리즘 퀵 정렬(quick sort) 코드 void quickSort(int[] arr, int stat, int end..
-
[Algorithm] 정렬 알고리즘에 대하여 1programing/Algorithm 2019. 6. 26. 21:53
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다.) 이번 포스트에서는 기본적인 정렬 알고리즘에 대해 포스팅하겠습니다. 대표적인 정렬 알고리즘 버블 정렬(bubble sort) 코드 void bubbleSort() { } 맨 앞쪽 두 요소씩 값을 비교하며 정렬해 나간다. 마지막 요소는 최대값이 된다. 모든 요소가 정렬될 때까지 반복한다. 시간 복잡도 두 요소를 비교하는 횟수 : n-1, n-2, ..., 2, 1 두 수를 교환하는 횟수 : 1 * n (교환 여부를 예측할 수 없음) T(n) = (n-1) + (n-2) + ... + 2 + 1 + 1 = n(n-1)/2 = o(n^2) 최악 : o(n^2) 최선 : o(n^2) 평균 : o(n^2) 삽입 정렬(insertion so..
-
[Algorithm] 재귀함수에 대해programing/Algorithm 2019. 6. 21. 19:21
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다.) 이번 포스트에서는 재귀함수에 대해 전체적인 정의와 개념들에 대해서 정리해볼까 합니다. 따라서 비정기적으로 업데이트됩니다. ㅎㅎ 재귀함수의 정의 함수 내에서 자기 자신을 호출하는 함수. 재귀함수의 조건 반드시 재귀호출을 하지 않는 base case가 존재해야 한다. 모든 case는 base case로 수렴해야 한다. 설계 원칙 암시적 변수를 명시적 매개변수로 바꾼다 int sequentialSearch(int[] arr, int index, int target) { for(int i=0; i < index; i++) { if(arr[i] == target) return i; } return -1; } 만약 위와 같이 순차탐색을 하..
-
[Algorithm] 재귀를 이용하여 최대공약수 구하기programing/Algorithm 2019. 6. 8. 15:32
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다.) 오늘은 재귀(recursion)을 이용하여 최대공약수(greatest common divisor)를 구하는 방법을 알아보도록 하겠습니다. 최대공약수와 유클리드 호제 2개 이상의 수의 공약수 중에서 최대인 수이다. 이를 테면, 18의 약수는 1, 2, 3, 6, 9, 18 이고,12의 약수는 1, 2, 3, 4, 6, 12 로서 6이 최대공약수이며, 이것을 (12,18)＝6으로 쓴다. 다른 공약수는 모두 6의 약수이다. 최대공약수를 구하는 방법은, 우선 소인수(素因數)로 분해하여 공통의 수를 택하여 곱해주면 된다. 예를 들면 (12,18)을 구할 경우 12＝22×3, 18＝2×32이므로 (12,18)＝2×3＝6이 된다. 또, 주어..
-
[JS] memoization을 이용한 피보나치 수열 함수 구현programing/Algorithm 2019. 3. 9. 21:32
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다.) 오늘은 재귀함수에서 한번 구해놓은 값을 저장하는 기법인 memoization을 이용하여 피보나치 수열의 n번째 항의 값을 반환하는 함수를 구현해보도록 하겠습니다. (이때 n은 0부터 시작하므로, 사용시 주의해주세요.) const fiboRecMemoized = (() => { // 계산 결과를 저장하는 저장소를 만듭니다. const memo = new Map(); const fiboRec = n => { // 만약에 이전에 같은 인수로 계산한 적이 있다면 // 해당 결과를 바로 반환합니다. let result = memo.get(n); if (result != undefined) return result; result = ( n..
-
[JS] 재귀함수를 이용한 병합정렬programing/Algorithm 2019. 3. 9. 21:24
안녕하세요, Einere입니다.(ADblock을 꺼주시면 감사하겠습니다. 오늘은 Divide and Conquer에서 자주 사용되는 재귀함수를 이용하여 merge sort를 구현해보도록 하겠습니다. function mergeSort(arr) { // 입력된 배열의 길이가 1 이하이면 더 이상 재귀 호출을 하지 않습니다. if (arr.length arr2[j]) { newArr.push(arr2[j]); j++; } else { newArr.push(arr1[i]); i++; } } // 큰 배열을 반환합니다. return newArr; }