버블 정렬 (Bubble Sort)✐ 개념인접한 2개의 레코드를 비교하여 순서가 맞지 않으면 서로 교환하는 비교-교환 과정을리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행하는 방식으로 정렬하는 방법 (제자리 정렬, 안정적 정렬) ✐ 시간 복잡도 : T(n) = (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n^2) ✐ Java 코드12345678910111213public static void bubbleSort(int[] data) { int temp; for(int i = data.length-1; i > 0; i--) { for(int j = 0; j data[j+1]) { temp = data[j]; data[j] = data[j+1]; data[j+1] = temp; }..
선택 정렬 (Selection Sort)✐ 개념최솟값을 찾아서 앞에 위치한 값과 교체하는 방법1. 주어진 데이터에서 최솟값을 탐색한다.2. 탐색한 최솟값을 인덱스 첫 번째 위치한 값과 교체한다.3. 첫 번째 위치한 값을 제외하고 나머지 데이터에서 최솟값을 다시 탐색 후 두 번째 위치한 값과 교체한다.4. 마지막 데이터가 정렬될 때까지 위의 방법을 반복한다. ✐ 시간 복잡도: T(n) = (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n^2) ✐ Java 코드1234567891011121314151617public static void selectionSort(int[] data) { int minData, temp; for(int i = 0; i data[1]) 결과 값이 (2 <..
이진 탐색 (Binary Search) ✐ 개념정렬된 데이터에서 특정한 값을 찾아내는 방법1. 정렬된 데이터의 중간에 위치한 값(Y)을 선택 후, 찾고자 하는 값(X)과 비교2. 찾고자 하는 값(X)이 선택한 값(Y)보다 작을 경우, 선택한 값(Y)의 좌측 데이터를 탐색3. 찾고자 하는 값(X)이 선택한 값(Y)보다 클 경우, 선택한 값(Y)의 우측 데이터를 탐색4. 찾고자 하는 값(X)을 찾기까지 2, 3번의 과정을 계속해서 반복한다. ✐ 시간 복잡도 : T(n) = O(logn) ✐ Java 코드 123456789101112131415public static int binarySearch(int[] data, int target, int low, int high) { if(low > high) ret..
순차 탐색 (Liner Search)✐ 개념데이터를 순차적으로 하나씩 검색하여 찾는 방법 (선형 탐색) ✐ 시간 복잡도 : T(n) = O(n) ✐ Java 코드 12345678910public static int linerSearch(int[] data, int n, int target) { if(n
알고리즘 분석 (Algorithm analysis) 시간 복잡도 분석 (Time complexity analysis) ✐ 알고리즘의 실행 시간 효율성 분석 ✓ 알고리즘의 실제 수행시간을 측정하는 방법 : 실행환경의 영향이 크다. ✓ 시간복잡도 분석은 명령문의 실행 횟수를 분석한다. ✐ 실행시간은 입력(Input)에 따라 달라진다. ✓ 입력크기가 클수록 증가한다. ✓ 동일한 입력 크기라도 입력 사례에 따라 달라질 수 있다. ✐ 입력 크기(Input size) : n으로 표시한다. ✓ 검색 혹은 정렬 문제 : 배열에 속한 원소(Element)의 수 ✓ 피보나치 수열 혹은 팩토리얼 계산 : 입력을 부호화하는데 필요한 비트 수 = logN + 1 ✐ 시간복잡도 분석은 입력 크기에 따른 실행시간을 중요, 연산의 ..
