CS/Algorithm

[알고리즘] 삽입 정렬 Insertion Sort (자바/Java)

목차 삽입 정렬 0번째부터 i번째까지 정렬된 배열의 크기를 증가시키며 정렬하는 알고리즘 이미 정렬된 i개짜리 배열에 하나의 원소를 더하여 정렬된 i+1개짜리 배열 만들기! 시간 복잡도: $O(n^2)$ 과정 i번째 원소를 정렬할 차례 i-1번째까지의 원소들은 정렬되어 있음 i-1부터 0까지의 원소들과 i번째 원소(key)를 비교하며, i번째 원소보다 작은 원소를 만나면 break, i번째 원소보다 크다면 해당 원소를 오른쪽으로 한 칸씩 shift break한 원소 다음 자리에 i번째 원소를 삽입 1부터 마지막 원소까지 반복 1 0번째 원소는 정렬된 상태 i=1, 10 10..

[알고리즘] 카운팅 정렬(Counting Sort) (자바/Java)

목차 카운팅 정렬 데이터끼리 비교 없이 데이터의 개수를 세어 정렬하는 알고리즘 제한 정수나 정수로 표현할 수 있는 자료에 대해서만 한정 데이터의 입력 범위가 제한적인 경우에 효율적 데이터의 수는 적지만, 데이터 값의 범위가 큰 경우(ex. 1~10억) count 배열이 메모리를 과다하게 사용하여 비효율적! 시간복잡도 O(n+k) n: 배열의 길이 k: 정수의 최대값 과정 정렬할 배열에서 가장 큰 정수를 크기로 하는 count 배열을 선언한다.. 데이터 값이 i인 경우, count[i]를 1씩 증가시킨다. count가 모두 끝나면, 앞에서부터 누적합하여 count배열을 수정한다. 기존 배열의 맨 마지막 index부터 정렬을 시작한다. arr[n-1]이 k일 경우, count[k]의 값을 찾아, 그 값을 1..

[알고리즘] 완전 검색, Baby-Gin (자바/Java)

목차 완전 검색 가능한 모든 경우의 수를 확인하는 기법 Brute-force, Generate-and-Test 기법 경우의 수가 작을 때 유용함 정확성은 높지만, 경우의 수가 커진다면 비효율적일 수 있음 Baby-Gin 임의의 숫자 6개를 뽑아 run과 triplet으로만 구성된 카드 = baby-gin run: 3장의 카드가 연속적인 번호를 갖는 경우 triplet: 3장의 카드가 동일한 번호를 갖는 경우 모든 경우의 수 구하기 (순열) 6개의 숫자는 6!개의 순열이 가능 먼저 6개 숫자에서 가능한 세 자리 순열(6P3)을 구하여 run 또는 triplet에 해당하는지 검사 true를 반환한다면, 다시 남은 3가지 수 중에서 순열을 구하여 run 또는 triplet에 해당하는지 검사 for (int i..

[알고리즘] 검색 Search - 순차 검색, 이진 검색 (자바/Java)

목차 검색 자료에서 원하는 항목을 찾는 작업 종류 순차 검색 이진 검색 인덱싱 순차 검색 일렬로 되어 있는 자료를 순서대로 검색 장점: 배열, 연결 리스트 등에서 유용 단점: 자료의 크기가 큰 경우에 비효율적 정렬X 첫 번째 원소부터 마지막 원소까지 키 값이 같은 원소가 있는지 검색 동일한 원소를 찾으면 검색을 중지하고 그 인덱스를 반환 마지막 원소까지 키를 찾지 못하면 실패 시간 복잡도: O(n) 정렬O 첫 번째 원소부터 키 값보다 큰 원소가 나올 때까지 검색 동일한 원소를 찾으면 반환, 키 값보다 큰 원소가 나왔는데 찾지 못하면 검색 실패 시간 복잡도: O(n) 그러나 정렬되지 않았을 때보다 평균 비교 횟수가 절반으로 줄어든다. 이진 검색 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위..

[알고리즘] 정렬 - 선택 정렬(Selection Sort) (자바/Java)

목차 선택 정렬 개념 주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식으로 정렬하는 알고리즘 시간 복잡도: O(n^2) 정렬 과정 첫 번째 원소를 두 번째부터 마지막 원소까지 비교하여 가장 작은 값과 자리 교환 2가 가장 작은 원소이고, 그 값의 index는 2이므로 arr[0]과 arr[1] 교환, arr[0]은 가장 작은 값으로 정렬 완료 두 번째, 세 번째 … 끝에서 두 번째 원소까지 같은 과정을 반복함 코드 package sort; import java.util.Arrays; public class SelectionSort { public static void main(String[] args) { int[] arr = { 30, 15, 2, 8, 21, 7 }; ..

[알고리즘] 정렬 - 버블 정렬(Bubble Sort) (자바/Java)

목차 버블 정렬 개념 인접한 두 개의 원소를 비교하며 정렬하는 알고리즘 정렬 과정 배열이 {30, 15, 2, 8, 21, 7}일 때를 가정한다. 원소는 자신의 오른쪽 값과 비교하기 때문에, 첫 사이클에서 비교할 마지막 index는 n-2이다. n-1(마지막 원소)와 비교를 하면 한 사이클이 끝나기 때문이다. 그렇게 한 사이클이 지나면 가장 큰 값이 배열의 오른쪽에 위치하여 다음 사이클에서는 비교 대상에서 제외된다. 두 번째는 30을 제외하고 다섯개의 원소만 비교하며 같은 과정을 반복한다. 이 사이클이 끝나면 두 번째로 큰 원소인 21이 자신의 위치를 찾아간다. 이렇게 반복하다보면 i가 1일때, 두 번째로 작은 원소인 7이 정렬되고, 자동으로 가장 작은 원소인 2는 비교 대상이 없기 때문에 모든 정렬이 ..