싸드의 DEVELOPER

선택정렬이란? 선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.주어진 리스트 중에 최솟값을 찾는다.그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다.출처 - 위키 출처는 위키가 최고다. 그럼 이제 자바로 구현해보자 public static void main(String[] arg){ int[] arr = {3,1,2,10,3,99, 19};selectionSort(arr);System.out.println(Arrays.toString..

이번엔 가장 빠르다는 퀵퀵소트에 대해 알아보자. 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다. 그리고 퀵 정렬은 정렬을 위해 O(log n)만큼의 memory를 필요로한다. 또한 퀵 정렬은 불안정 정렬에 속한다. 퀵 정렬은 분할 정..

MergeSort란?합병 정렬은 다음과 같이 작동한다.리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.출처 - 위키 뭐 설명은 여기저기서 다 보면 이해 가능할거라 생각한다. 그럼 자바로 한번 구현해보자. public static void main(String[] args) { int[] arr = {3,2,9,5,10,15,40,1,22,2,99}; mergeSort(arr); System.out.println("arr: " + Arrays.toString(arr));} // 배열들을 크..

삽입정렬이란?삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 한마디로 배열의 1번째부터 마지막까지 반복문을 사용하여 Key로 선택해서 앞 배열들과 비교 후 자리를 바꿔주는 정렬이다.그럼 자바로 구현해 보겠다. 항상 티스토리에서 직접 코드를 작성하기 때문에 오타는 있을 수 있다. public static void main(String[] args) {int[] arr = {6,12,3,2,1,3,99,323,3821,129,1}; insertionSort(arr);System.out.println("arr : " + Arrays.toString(arr));} p..

버블 정렬이란? 거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 {\displaystyle O(n^{2}))}로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 자, 그럼 자바로 버블정렬 구현 해보자. public static void main(String[] args) {int[] arr = {6,8,1,3,5,10,13,7,1,4}; bubbleSort(arr);System.out.println("arr : " + Arrays.toString(arr));} public static void bubbleSort(int arr[]) { // 인접한 배열을 다 돌려면..

이진탐색이란?정렬된 배열에서 검색하고 싶은 키가 몇번째인지 확인 하는 탐색 알고리즘. ( 꼭 정렬이 되어 있어야 찾을 수 있다. ) 이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.-- 출처 https://ko.wikipedia.org/wik..

public class Factorial { public static void main(String[] args) {/* 팩토리얼을 구해보자. 기본적 공식 5! = 5*4*3*2*1 N!은 N부터 1까지 모두 곱한 값 3! 을 구해보자 3! = 3*2*1*/ int factorialNum = getFactiorial(5);System.out.println("factirialNum :" + factorialNum);} private static int getFactiorial(int num) {if( num == 1) return 1;// 1일땐 1을 리턴해준다 return getFactiorial(num-1) * num;/* 설명은 할 것도 없지만... 만약 5가들어올경우 5*4*3*2*1 이되야함맨 처..