suyeonme

1. 병합 정렬(Merge Sort)이란? 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬하는 알고리즘 배열 병합의 시간 복잡도는 O(n)이고, 전체 시간 복잡도는 O(n log n)이다. 서로 떨어져있는 요소를 교환하는 경우가 없으므로 안정적인 정렬 방법이다. 2. 동작 방식 int[] arr = { 5,6,4,8,3,7,9,0 }; // 1. 배열을 앞부분과 뒷부분으로 나눈다. 앞부분(a): { 5,6,4,8 } 뒷부분(b): { 3,7,9,0 } // 2. 앞부분과 뒷부분을 재귀를 사용하여 정렬한다. 앞부분(a): { 4,5,6,8 } 뒷부분(b): { 0,3,7,9 } 정렬된 배열(c): {} // 3. 각 배열의 작업에서 선택한 요소의 인덱스는 pa, pb, p..

1. 퀵 정렬(Quick Sort)이란? 찰스 엔터니 리처드 호어(C. A. R. Hoare)가 개발한 알고리즘으로, 일반적으로 폭넓게 사용되고 있는 빠른 정렬 알고리즘이다. 퀵 정렬은 대표적인 분할 정복을 사용한 알고리즘으로, 각 그룹에 대해 피벗(pivot) 설정과 그룹 나눔을 반복하여 정렬을 한다. 평균 시간 복잡도는 O(n log n)이다. 이미 정렬이 된 배열의 경우, 최악 시간 복잡도는 O(n ^2)이다. (이 경우 삽입 정렬 사용) 2. 동작 방식 퀵 정렬을 사용하여 배열을 정렬한다면 아래와 같이 동작한다. 배열은 { 5, 7, 1, 4, 6, 2, 3, 9, 8 }이다. 배열의 첫번째 원소를 피벗(pivot)으로 선택하여 배열을 나눈다. 왼쪽에서 오른쪽으로 스캔하며 피벗보다 큰 값을 선택한..

1. 셸 정렬(Shell Sort)이란? 도날드 셸(D.L.Shell)이 고안한 알고리즘으로, 삽입 정렬(Insert Sort)의 장점을 살리고 단점을 보완하여 좀더 빠르게 정렬한다. 일정한 간격으로 서로 떨어져있는 두 요소를 그룹으로 묶어 대략 정렬을 수행하고 간격을 좁혀 그룹의 수를 줄이면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법이다. 즉 그룹 별로 미리 몇차례 정렬을 하고 삽입 정렬을 실시하여 삽입 정렬의 장점을 이용한다. 셸 정렬 과정에서 수행하는 각각의 정렬을 h-정렬이라고 한다. 멀리 떨어져있는 요소를 교환하므로 안정적이지 않다. 시간 복잡도는 O(n1.25)로 O(n^2)보다 빠르다. 1.1 동작 방법 배열이 { 8, 1, 4, 2, 7, 6, 3, 5 }라고 가정하고 셸 정렬을 수..

1. 선택 정렬(Selection Sort)이란? 가장 작은 요소를 맨 앞으로 이동하고, 두번째 작은 요소는 맨 앞에서 두번째로 이동하는등의 작업을 반복하는 알고리즘이다. 시간 복잡도는 O(n^2)으로 효율이 좋지 않다. (버블 정렬 < 선택 정렬) 서로 떨어져있는 요소를 교환하므로 안정적이지 않다. 즉 중복된 요소가 존재할 경우, 정렬한 후 두 요소의 순서가 뒤바뀐다. 1.1 선택 정렬 구현 public void selectionSort(int[] arr, int n) { for(int i = 0; i < n - 1; i++) { int min = i; // 아직 정렬되지 않은 부분에서 가장 작은 요소의 인덱스 for(int j = i + 1; j < n; j++) { if(arr[j] < arr[mi..

1. 버블 정렬이란? 이웃한 두 요소의 대소 관계를 비교하고 필요에 따라 교환을 반복하는 알고리즘으로 단순 교환 정렬(straight exchange sort)라고도 한다. 시간 복잡도는 O(n^2)로 효율이 좋지 않다. 정렬 과정 1. 배열의 끝에 있는 두 요소부터 비교를 시작한다. 2. 이웃한 두개의 요소를 비교하고 왼쪽 요소가 오른쪽 요소보다 작으면 위치를 교환한다. 3. 위의 과정을 첫번째 요소까지 반복한다. (이 과정을 패스, pass 라고 한다) 2. 버블 정렬 구현 public void swap(int[] arr, int idx1, int idx2) { int t = arr[idx1]; arr[idx1] = idx2; arr[idx2] = t; } public void bubbleSort(i..

1. 재귀란? 어떤 사건이 자기 자신을 포함하고 있거나 또는 자기 자신을 사용하여 정의하고 있을 때 이를 재귀적(recursive)이라고 한다. 1.1 재귀 관련 용어 직접 재귀(direct recursion): 자신과 동일한 메서드를 호출하는 구조 간접 재귀(indirect recursion): 메서드 a가 메서드 b를 호출하고 다시 메서드 b가 메서드 a를 호출하는 구조 순수(genuinely) 재귀: 재귀 호출을 여러번 실행하는 메서드 꼬리 재귀(tail recursion): 재귀의 호출이 끝난 후 현재 함수에서 추가적인 연산을 요구하지 않도록 구현한 재귀 1.2 재귀 사용시 유의 사항 재귀 함수는 반복적으로 호출된다. 하나의 함수의 실행이 끝나지 않았음에도 함수를 연속적으로 호출하기때문에 각각의 ..

1. 선형 검색(Linear Search) 배열에서 원하는 키값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색한다. 복잡도는 O(n)이다. static int seqSearch(int[] arr, int n, int key) { int i = 0; while(true) { if(i == n) { return -1; } if(arr[i] == key) { return i; } i++; } } 1.1 보초법(Sentinel Method) 위의 선형 검색은 반복할 때마다 종료 조건 1과 2를 모두 판단한다. 보초법을 사용하여 반복문에서 종료 판단 횟수를 2회에서 1회로 줄일 수 있다. 순서) 1. 검색할 값을 보초로 arr[n]에 대입한다. 2. 배열 요소를 순서대로 스캔한다. static int..

소수(Prime Number): 1보다 크고 자기 자신과 1 이외에 어떤 정수로도 나누어떨어지지 않는 정수 합성수(Composite Number): 나누어떨어지는 정수가 하나 이상 존재하는 수 해결 1) i가 2 또는 3으로 나누어떨어지지 않으면 4, 6으로도 나누어떨어지지 않는다. 즉 2부터 n-1까지의 어떤 소수로도 나누어지지 않는다는 조건을 만족하는지 조사하여, 불필요한 나눗셈을 줄일 수 있다. (7이 소수인지 여부는 7보다 작은 소수 2,5,3으로 나눗셈을 하여 구한다.) public ArrayList getPrimeNumbers(int num) { ArrayList primeNumbers = new ArrayList(); for(int i = 2; i